Daniel Martin - 2 months ago 9
Scala Question

# scalacheck Arbitrary implicits and recursive generators

I'm seeing what seems to be a very obvious bug with scalacheck, such that if it's really there I can't see how people use it for recursive data structures.

This program fails with a

`StackOverflowError`
before scalacheck takes over, while constructing the
`Arbitrary`
value. Note that the
`Tree`
type and the generator for
`Tree`
s is taken verbatim from this scalacheck tutorial.

``````package treegen

import org.scalacheck._
import Prop._

class TreeProperties extends Properties("Tree") {

trait Tree
case class Node(left: Tree, right: Tree) extends Tree
case class Leaf(x: Int) extends Tree

val ints = Gen.choose(-100, 100)

def leafs: Gen[Leaf] = for {
x <- ints
} yield Leaf(x)

def nodes: Gen[Node] = for {
left <- trees
right <- trees
} yield Node(left, right)

def trees: Gen[Tree] = Gen.oneOf(leafs, nodes)

implicit lazy val arbTree: Arbitrary[Tree] = Arbitrary(trees)

property("vacuous") = forAll { t: Tree => true }
}

object Main extends App {
(new TreeProperties).check
}
``````

What's stranger is that changes that shouldn't affect anything seem to alter the program so that it works. For example, if you change the definition of
`trees`
to this, it passes without any problem:

``````  def trees: Gen[Tree] = for {
x <- Gen.oneOf(0, 1)
t <- if (x == 0) {leafs} else {nodes}
} yield t
``````

Even stranger, if you alter the binary tree structure so that the value is stored on
`Node`
s and not on
`Leaf`
s, and alter the
`leafs`
and
`nodes`
definition to be:

``````  def leafs: Gen[Leaf] = Gen.value(Leaf())

def nodes: Gen[Node] = for {
x <- ints     // Note: be sure to ask for x first, or it'll StackOverflow later, inside scalacheck code!
left <- trees
right <- trees
} yield Node(left, right, x)
``````

It also then works fine.

What's going on here? Why is constructing the
`Arbitrary`
value initially causing a stack overflow? Why does it seem that scalacheck generators are so sensitive to minor changes that shouldn't affect the control flow of the generators?

Why isn't my expression above with the
`oneOf(0, 1)`
exactly equivalent to the original
`oneOf(leafs, nodes)`
?

The problem is that when Scala evaluates `trees`, it ends up in an endless recursion since `trees` is defined in terms of itself (via `nodes`). However, when you put some other expression than `trees` as the first part of your for-expression in `nodes`, Scala will delay the evaluation of the rest of the for-expression (wrapped up in chains of `map` and `flatMap` calls), and the infinite recursion will not happen.
Just as pedrofurla says, if `oneOf` was non-strict this would probably not happen (since Scala wouldn't evaluate the arguments immediately). However you can use `Gen.lzy` to be explicit about the lazyness. `lzy` takes any generator and delays the evaluation of that generator until it is really used. So the following change solves your problem:
``````def trees: Gen[Tree] = Gen.lzy(Gen.oneOf(leafs, nodes))