scalacheck 任意隐式和递归生成器 [英] scalacheck Arbitrary implicits and recursive generators

问题描述

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

I'm seeing what seems to be a very obvious bug with scalacheck, such that if it's really there I can't see how people use it for recursive data structures.

该程序在构建 Arbitrary 值时，在 scalacheck 接管之前失败并显示 StackOverflowError.请注意，Tree 类型和 Tree 的生成器是逐字取自 这个 scalacheck 教程.

This program fails with a StackOverflowError before scalacheck takes over, while constructing the Arbitrary value. Note that the Tree type and the generator for Trees is taken verbatim from 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的定义改成这样，它就毫无问题地通过了:

What's stranger is that changes that shouldn't affect anything seem to alter the program so that it works. For example, if you change the definition of trees to this, it passes without any problem:

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

更奇怪的是，如果你改变二叉树结构，使值存储在 Nodes 而不是 Leafs，并改变 leafs 和 nodes 定义为:

Even stranger, if you alter the binary tree structure so that the value is stored on Nodes and not on Leafs, and alter the leafs and nodes definition to be:

  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 生成器对不应该影响生成器控制流的微小变化如此敏感?

What's going on here? Why is constructing the Arbitrary value initially causing a stack overflow? Why does it seem that scalacheck generators are so sensitive to minor changes that shouldn't affect the control flow of the generators?

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

Why isn't my expression above with the oneOf(0, 1) exactly equivalent to the original oneOf(leafs, nodes) ?

推荐答案

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

The problem is that when Scala evaluates trees, it ends up in an endless recursion since trees is defined in terms of itself (via nodes). However, when you put some other expression than trees as the first part of your for-expression in nodes, Scala will delay the evaluation of the rest of the for-expression (wrapped up in chains of map and flatMap calls), and the infinite recursion will not happen.

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

Just as pedrofurla says, if oneOf was non-strict this would probably not happen (since Scala wouldn't evaluate the arguments immediately). However you can use Gen.lzy to be explicit about the lazyness. lzy takes any generator and delays the evaluation of that generator until it is really used. So the following change solves your problem:

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

这篇关于scalacheck 任意隐式和递归生成器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！