someOf/pick utilities

[dwijnand]

I developed these in order to port some ScalaCheck code. I think they would be handy to have:

  def someOf[A](xs: List[A]): Gen[List[A]] = for {
    n <- Gen.int(Range.constant(0, xs.length))
    xs <- pick(n, xs)
  } yield xs

  def pick[A](n: Int, xs: List[A]): Gen[List[A]] = n match {
    case 0 => Gen.constant(Nil)
    case _ => for {
      a <- Gen.elementUnsafe(xs)
      (lhs, rhs) = xs.span(_ != a)
      ys <- pick(n - 1, lhs ::: rhs.drop(1))
    } yield a :: ys
  }

[charleso]

@dwijnand That would definitely be useful! I already added pick to sbt quite a while ago.

https://github.com/sbt/sbt/blob/30e4c02c9c74db093dec21b31b5f8ae30a2ef6ff/main/src/test/scala/sbt/internal/TestBuild.scala#L388-L400

  def pick[A](n: Int, as: Seq[A]): Gen[Seq[A]] = {
    if (n >= as.length) {
      Gen.constant(as)
    } else {
      def go(m: Int, bs: Set[Int], cs: Set[Int]): Gen[Set[Int]] =
        if (m == 0)
          Gen.constant(cs)
        else
          Gen.element(bs.head, bs.tail.toList).flatMap(a => go(m - 1, bs - a, cs + a))
      go(n, as.indices.toSet, Set())
        .map(is => as.zipWithIndex.flatMap(a => if (is(a._2)) Seq(a._1) else Seq()))
    }
  }

Just on your version, I would definitely avoid relying on value equality, seems like a source of strange bugs and I think you can/should avoid. Definitely take my version with scepticism, there might be a much better/cleaner way.

[charleso]

The other consideration if the shrinking, it's one of those functions that the library version could possibly do a better job than what you get, but that requires a little more thought.

[charleso]

Looking at it again/now, the heavy use of flatMap is a bit of a smell (it might not shrink well, but I'm not sure). It might be possible to generate a list of exactly n booleans, "shuffle" (not implemented in scala, but is in haskell), map and zip and then take the true elements.

def pick[A](n: Int, as: Seq[A]): Gen[Seq[A]] = {
  Gen.shuffle(List.fill(n, true) ++ List.fill(as.length - n, false)).map(bs =>
    as.zip(bs).flatMap { case (a, b) => if (b) List(a) else Nil }
  )

https://github.com/hedgehogqa/haskell-hedgehog/blob/master/hedgehog/src/Hedgehog/Internal/Gen.hs#L1622

[dwijnand]

Having noticed it was missing, I implemented it forgetting the a :: prepend (😳) causing someOf to always return Nil... 😄 So I reckoned it's worth having something reasonably correct out the box.

(I also noticed there's no support for recursive definitions, IIRC. If I find the workaround I put together I'll open a separate issue on it.)