Scalacheck Произвольные импликации и рекурсивные генераторы

Я вижу, что кажется очень очевидной ошибкой в scalacheck, так что если это действительно так, я не вижу, как люди используют его для рекурсивных структур данных.

Эта программа выходит из строя с StackOverflowError до того, как scalacheck возьмет верх, при построении значения Arbitrary. Обратите внимание, что тип Tree и генератор для Tree принимается стенографически из этого учебника по скаляке.

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, а не на 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)

Он также отлично работает.

Что здесь происходит? Почему создается значение Arbitrary, изначально вызывающее переполнение стека? Почему кажется, что генераторы scalacheck настолько чувствительны к незначительным изменениям, которые не должны влиять на поток управления генераторами?

Почему мое выражение выше с oneOf(0, 1) не эквивалентно оригиналу oneOf(leafs, nodes)?

Ответ 1

Проблема в том, что когда Scala оценивает trees, он заканчивается бесконечной рекурсией, так как trees определяется в терминах самого себя (через nodes). Однако, когда вы помещаете какое-то другое выражение, чем trees в качестве первой части вашего выражения для выражения в nodes, Scala будет задерживать оценку остальной части выражения for (выражение в цепочках map и flatMap), и бесконечная рекурсия не произойдет.

Так же, как говорит педрофурла, если oneOf был нестрогим, это, вероятно, не произойдет (поскольку Scala не будет немедленно оценивать аргументы). Однако вы можете использовать Gen.lzy, чтобы быть явным о лени. lzy принимает любой генератор и задерживает оценку этого генератора, пока он не будет использован. Таким образом, следующее изменение решает вашу проблему:

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

Ответ 2

Несмотря на то, что после ответа Рикарда Нильсона выше, он избавился от константы StackOverflowError при запуске программы, я все равно удалю StackOverflowError примерно один раз из три раза, когда я попросил scalacheck проверить свойства. (Я изменил Main выше, чтобы запустить .check 40 раз, и увидит, что он будет успешным дважды, затем завершится с переполнением стека, затем дважды сработает и т.д.)

В конце концов мне пришлось вложить жесткий блок в глубину рекурсии, и это то, что я предполагаю, что буду делать при использовании 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.

Ответ 3

Небольшое обобщение подхода в собственном ответе Даниэля Мартина использует 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)