再帰的なデータ構造のテスト

Question

ScalaCheck: The Definitive Guideは、再帰的なデータ構造のためのジェネレータの作成方法を説明しています。

まず、それはデータ構造を定義：

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) 

私の理解では、listOfのGen[Tree[A]]の使用量がStackOverflowErrorに責任があるということです。

ただし、Gen[MyList[A]]コードの発電機でStackOverflowErrorが可能ですか？

genListが十分に返ってきたら、Consが返ってきていると思いますが、わかりません。

Answer 1

ジェネレータが再帰的であるため、スタックオーバーフローエラーが発生する可能性があります。問題は実際にはoneOf()が探索するパスをランダムに選択していることです。乱数ジェネレータがツリー展開を駆動します。

私は、私が望む深みの木を得るために重み付けを使うことができることを発見しました。私はfrequency()と一緒に遊んで、正しい体重が機能すると信じています。