scala - 测试递归数据结构

Question

ScalaCheck: The Definitive Guide解释如何为递归数据结构创建生成器。

首先，它定义了数据结构:

trait Tree[T] {
    def size: Int
}
case class Leaf[T](item: T) extends Tree[T] {
    def size = 1
}
case class Node[T] (children: List[Tree[T]]) extends Tree[T] {
    def size = children.map(_.size).sum
}

接下来，它显示了 Gen[Tree[A]] 代码:

import org.scalacheck.Gen
import org.scalacheck.Gen.{oneOf, listOf, lzy}

def genTree[T](genT: Gen[T]): Gen[Tree[T]] = lzy {
    oneOf(genLeaf(genT), genNode(genT))
}

def genLeaf[T](genT: Gen[T]): Gen[Leaf[T]] =
    genT.map(Leaf(_))

def genNode[T](genT: Gen[T]): Gen[Node[T]] = for {
    children <listOf(
    genTree(genT))
} yield Node(children)

对于上面的生成器，本书进行了演示，调用它会导致 StackOverflowError:

scala> genIntTree.sample
res0: Option[Tree[Int]] = Some(Leaf(2147483648))

scala> genIntTree.sample
res1: Option[Tree[Int]] = Some(Leaf(0))

scala> genIntTree.sample
java.lang.StackOverflowError
     at org.scalacheck.Gen$$anonfun$1$$anonfun$apply...

给定以下 MyList 数据结构:

sealed abstract class MyList[+A]
case class Cons[+A](elem: A, rest: MyList[A]) extends MyList[A]
case object Empty                             extends MyList[Nothing]

以及以下生成器:

def genList[A](gen: Gen[A]): Gen[MyList[A]] =
    lzy { oneOf(genCons(gen), Gen.const(Empty)) } 

def genCons[A](gen: Gen[A]): Gen[MyList[A]] = for {
    list <- genList(gen)
    a    <- gen
} yield Cons(a, list)

我的理解是 Gen[Tree[A]] 对 listOf 的使用导致了 StackOverflowError。

但是，Gen[MyList[A]] 代码的生成器中是否可能出现 StackOverflowError？

我猜测如果足够的 genList 返回足够的 Cons，但我不确定。

Answer 1

由于生成器是递归的，很可能会导致栈溢出错误。问题实际上是 oneOf() 在选择探索路径时是随机的；您的随机数生成器驱动树扩展。

我发现我可以使用权重来获得我想要的深度的树。我相信我使用了 frequency() 来获得正确的权重。