Arbitrary[Recursive]

84 views
Skip to first unread message

Tony Morris

unread,
Sep 21, 2010, 4:43:28 AM9/21/10
to scala...@googlegroups.com
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Is it possible to define an Arbitrary implicit for a recursive data
type? I have tried using the sample code below along with
experimentation using Gen.lzy however, I continually run into a
StackOverflowError. Is it possible to repair this code?

http://paste.pocoo.org/show/265222/

sealed trait Recursive {
def isValue = this match {
case ValueRecursive(_) => true
case BranchRecursive(_) => false
}

def isBranch = this match {
case ValueRecursive(_) => false
case BranchRecursive(_) => true
}
}
case class ValueRecursive(n: Int) extends Recursive
case class BranchRecursive(b: List[Recursive]) extends Recursive

// scalacheck_2.8.0-1.8-SNAPSHOT.jar
import org.scalacheck._
import org.scalacheck.Arbitrary._
import org.scalacheck.Gen._
import org.scalacheck.Prop._

object ArbRecursive {
// java.lang.StackOverflowError
implicit def AR: Arbitrary[Recursive] = {
def n = arbitrary[Int] map (ValueRecursive(_))
def b = arbitrary[List[Recursive]] map (BranchRecursive(_))

Arbitrary(oneOf(n, b))
}

def main(args: Array[String]) {
val p = forAll((r: Recursive) => r.isValue != r.isBranch)

p.check
}
}


- --
Tony Morris
http://tmorris.net/

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAkyYcDAACgkQmnpgrYe6r61RnQCeNvOuWgThRojJYZW5cW0vmYJv
eVgAoICe2CK0JAMPdDZFzL/Lfr1lDGCT
=93Q+
-----END PGP SIGNATURE-----

Rickard Nilsson

unread,
Sep 21, 2010, 6:18:35 AM9/21/10
to scala...@googlegroups.com
Hi,

On Tue, 21 Sep 2010 18:43:28 +1000, Tony Morris <tmo...@tmorris.net>
wrote:

The problem is that the number of branches will explode, since
arbitrary[List[...]] will generate lists of lengths between 0
and 100 by default. And since you're using oneOf(n,b), values and
branches will be generated with the same probability.

The following seems to work fine:

implicit def AR: Arbitrary[Recursive] = {

val n = arbitrary[Int] map (ValueRecursive(_))

val b = choose(0,10) flatMap { n =>
listOfN(n, arbitrary[Recursive]) map (BranchRecursive(_))
}

Arbitrary(frequency((4,n), (1,b)))
}

Note, you didn't have to use lzy here, since the choose(0,10).flatMap
will make b lazy automatically. It wont evaluate the flatMap body
until necessary.

You could probably also make the distribution of values and
branches depend on the size parameter (using Gen.sized), and
negate the effect of large lists without restricting the
list size. In that case you probably need to wrap b with Gen.lzy.


Best regards,
Rickard Nilsson

Tony Morris

unread,
Sep 21, 2010, 6:30:54 PM9/21/10
to scalacheck
Cheers Rickard, that got it going.

On Sep 21, 8:18 pm, Rickard Nilsson <rickyn...@gmail.com> wrote:
> Hi,
>
> On Tue, 21 Sep 2010 18:43:28 +1000, Tony Morris <tmor...@tmorris.net>
> > Comment: Using GnuPG with Mozilla -http://enigmail.mozdev.org/
Reply all
Reply to author
Forward
0 new messages