scalacheck 任意隐式和递归生成器

Question

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

这个程序失败了 StackOverflowError在 scalacheck 接管之前，同时构建 Arbitrary值(value)。请注意 Tree类型和生成器 Tree s 逐字取自 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
}

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

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

更奇怪的是，如果你改变二叉树结构以便将值存储在 Node 上。 s 而不是在 Leaf s，并更改 leafs和 nodes定义为:

  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)

然后它也可以正常工作。

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

为什么我上面的表达式不是 oneOf(0, 1)完全等同于原始 oneOf(leafs, nodes) ?

Answer 1

问题是当 Scala 计算 trees 时，它以无休止的递归结束，因为 trees是根据自身定义的(通过 nodes )。但是，当您输入除 trees 之外的其他表达式时作为 nodes 中 for 表达式的第一部分, Scala 将延迟 for 表达式的其余部分的计算(包含在 map 和 flatMap 调用链中)，并且不会发生无限递归。

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

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