3

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的，但我不确定。

4

2 回答 2

2

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

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

于 2017-03-15T16:52:26.493 回答
0

在您的列表示例中，堆栈溢出的概率非常低——如果存在的话。原因——以及与树示例的不同之处——是您一次只使用一个元素。

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

于 2018-03-16T05:58:42.077 回答