재귀 데이터 구조 테스트

Question

ScalaCheck: The Definitive Guide은 재귀 적 데이터 구조에 대한 생성자를 만드는 방법을 설명합니다. 상기 발전기

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 발생할 수 호출 보여

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]] 코드이다 :

첫째, 데이터 구조 정의 :

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()으로 경기를했다고 믿는다.