14

我看到 scalacheck 似乎是一个非常明显的错误，如果它真的存在，我看不到人们如何将它用于递归数据结构。

该程序StackOverflowError在 scalacheck 接管之前失败，同时构造Arbitrary值。请注意，s 的Tree类型和生成器Tree是从这个 scalacheck 教程中逐字获取的。

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
}

奇怪的是，不应该影响任何事情的更改似乎会改变程序以使其正常工作。例如，如果您将 的定义更改trees为此，它会毫无问题地通过：

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

更奇怪的是，如果您更改二叉树结构，以便将值存储在Nodes 上而不是Leafs 上，并将leafsandnodes定义更改为：

  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)

然后它也可以正常工作。

这里发生了什么？为什么构造Arbitrary值最初会导致堆栈溢出？为什么 scalacheck 生成器似乎对不应该影响生成器控制流的微小变化如此敏感？

为什么我上面的表达与oneOf(0, 1)原来的表达不完全一样oneOf(leafs, nodes)？

4

3 回答 3

12

问题是，当 Scala 评估 时trees，它会以无休止的递归结束，因为trees它是根据自身定义的（通过nodes）。但是，当您将其他表达式放在treesfor 表达式的第一部分中时nodes，Scala 将延迟对 for 表达式的其余部分的求值（包裹在map和flatMap调用链中），并且不会发生无限递归.

正如 pedrofurla 所说，如果oneOf是非严格的，这可能不会发生（因为 Scala 不会立即评估参数）。但是，您可以使用Gen.lzy明确的懒惰。lzy接受任何生成器并延迟对该生成器的评估，直到它真正被使用。因此，以下更改可以解决您的问题：

def trees: Gen[Tree] = Gen.lzy(Gen.oneOf(leafs, nodes))
于 2013-11-07T08:30:57.237 回答
12

即使按照上面Rickard Nilsson的回答摆脱了StackOverflowError程序启动时的常量，一旦我实际要求 scalacheck 检查属性，我仍然会达到StackOverflowError三分之一左右。（我Main在上面更改为运行.check40 次，会看到它成功两次，然后因堆栈溢出而失败，然后成功两次，等等）

最终，我不得不对递归的深度设置一个硬块，这就是我想我将来在递归数据结构上使用 scalacheck 时会做的事情： 

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

  def genNode(level: Int): Gen[Node] = for {
    left <- genTree(level)
    right <- genTree(level)
  } yield Node(left, right)

  def genTree(level: Int): Gen[Tree] = if (level >= 100) {leafs}
                                       else {leafs | genNode(level + 1)}
  lazy val trees: Gen[Tree] = genTree(0)

通过此更改，scalacheck 永远不会遇到StackOverflowError.

于 2013-11-07T14:46:06.243 回答
2

Daniel Martin 自己的回答中对方法的一个轻微概括是使用sized. 类似（未经测试）：

def genTree() = Gen.sized { size => genTree0(size) }

def genTree0(maxDepth: Int) = 
  if (maxDepth == 0) leafs else Gen.oneOf(leafs, genNode(maxDepth))

def genNode(maxDepth: Int) = for {
  depthL <- Gen.choose(0, maxDepth - 1)
  depthR <- Gen.choose(0, maxDepth - 1)
  left <- genTree0(depthL)
  right <- genTree0(depthR)
} yield Node(left, right)

def leafs = for {
  x <- ints
} yield Leaf(x)
于 2016-06-17T18:00:53.923 回答