测试递归数据结构

Question

ScalaCheck：权威指南解释了如何为递归数据结构创建生成器。

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

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的原因。

但是，生成器中是否可以StackOverflowError Gen[MyList[A]]代码？

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

Answer 1

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

我

发现我可以使用权重来获得我想要的深度的树木。我相信我和frequency()一起玩是为了获得正确的重量。

Answer 2

在您的列表示例中，堆栈溢出的可能性非常低 - 如果存在的话。原因 - 以及与树示例的不同 - 是你一次只包含一个元素。

假设您的堆栈在 1000 个元素后会爆炸，发生这种情况的概率约为 1/(2^1000(，这是一个非常小的数字。