scalacheck: define a generator for an infinite stream with some dependence on previous elements

Question

I'm trying to define a Gen[Stream[A]] for an infinite (lazily evaluated) stream of As where each element A can depend on previous elements.

As a minimal case, we can take Gen[Stream[Int]] where the next element is either +1 or +2 of the previous element. For reference here is a haskell implementation:

increasingInts :: Gen [Int]
increasingInts = arbitrary >>= go
  where
    go seed = do
      inc <- choose (1,2)
      let next = seed + inc
      rest <- go next
      return (next : rest)

I have tried Gen.sequence on a Stream[Gen[A]] but got a stackoverflow. I also tried defining the Gen from scratch, but the constructor gen for Gen is private and works with private methods/types.

This attempt also gives a stackoverflow.

  def go(seed: Int): Gen[Stream[Int]] =
    for {
      inc <- Gen.choose(1, 2)
      next = seed + inc
      rest <- Gen.lzy(go(next))
    } yield next #:: rest

  val increasingInts: Gen[Stream[Int]] = go(0)


increasingInts(Gen.Parameters.default, Seed.random()).get foreach println

So I'm stuck. Any ideas?

Answer 1

What you want can be achieved with this:

val increasingInts = {
  val increments = Gen.choose(1, 2)
  val initialSeed = 0
  for {
    stream <- Gen.infiniteStream(increments)
  } yield stream.scanLeft(initialSeed)(_ + _)
}

.scanLeft is like a .foldLeft but retains the intermediate values, thus giving you another Stream.

---

I've written about scanLeft here: https://www.scalawilliam.com/most-important-streaming-abstraction/