# How to write a generator for a hierarchical structure

I’m trying to understand generators and ScalaCheck. I finally stumbled upon scala-excercises which seems to give a pretty easy introduction. But I don’t understand it well enough to write a generator for the structure I need.

I want to generate a node given a positive integer N. I have a function which will generate such a structure. (BTW, I’m using a capital `N` simply so I can pattern match against it. Is this the correct way?)

``````  val rgen = scala.util.Random

def genRandomBdd(N: Int): Bdd = {
def recur(level: Int): Bdd = {
val r = rgen.nextInt(2)    // 0 at 50%  and 1 at 50%
(r, level) match {
case (0, N) => BddTrue
case (1, N) => BddFalse
case (0, _) => recur(level + 1)
case (_, _) => Bdd(level + 1, recur(level + 1), recur(level + 1))
}
}
recur(0)
}
``````

So I can generate a random structure by calling `genRandomBdd(N)`.
Now, how do I write the Gen definition for ScalaCheck? And where does the `N` come from?

Additionally since the structure is exponentially larger as a function of N, (i.e., a Bdd built from `N` is twice as big as the Bdd built from `N-1`) so I would like that when ScalaCheck runs the test that it chose `N-1` twice as often as `N`. I.e., `N=1` is twice as frequent as `N=2`, `N=2` is twice as frequent as `N=3`, etc.

I don’t know ScalaCheck at all well (others might chime in), but the cognate in ScalaTest 3.1 (which has this stuff built in) would be more or less (NB: off the top of my head, forgive errors):

``````val bddGen: Generator[Bdd] = for {
i <- ints
}
yield genRandomBdd(i)
``````

`ints` is the standard Generator for integers (it spits out randomized numbers, with a bit of biased towards the common edge cases), and this is simply transforming that to a Generator of Bdds.

I think it’s roughly similar for ScalaCheck, but can’t swear to that…

When I copy/paste the example from scala-excercises.org my system is not able to resolve the symbol `check`.

``````import org.scalatest.FunSuite
import robdd._

class BddSuite extends FunSuite {

test("bdd with ScalaCheck") {
import org.scalacheck.Gen
import org.scalacheck.Prop.forAll

val intGen: Gen[Int] = for {
i <- Bdd.genNumVars(6)
} yield i

val bddGen: Gen[Bdd] = for {
i <- intGen
}
yield Bdd.genRandomBdd(i)

check {
forAll { b: Bdd => {
b == Not(Not(b))
}
}
}
}
`````` I have added the recommended (from scalacheck.org) line to my `build.sbt` file

``````libraryDependencies += "org.scalacheck" %% "scalacheck" % "1.14.0" % "test"
``````

This indeed allows the compiler to find symbols such as `Gen` and `forAll`, but `check` is still missing.

Any suggestions?

Again, not a ScalaCheck expert, but I think `check` is inappropriate in this situation. Try just removing that, so that the `forAll` stands on its on – that’s what I would normally expect it to look like.

As far as I can tell, `check` is a method on `Properties`. This syntax might be legal if you are building your tests entirely in ScalaCheck, extending Properties instead of FunSuite, but I think it’s inappropriate inside ScalaTest.

Hmm. Ok, I’ll try it, but what is supposed to trigger the properties to get tested?

The `forAll`. You can either go with the ScalaTest way (`forAll`) or the ScalaCheck properties way (`check`).

ScalaTest documentation (both user guide and API docs) is really good - you should find everything there you need.

Best regards,
Patrick

Well the ScalaTest documentation is huge, and it is not obvious how to get started. I have absolutely no doubt that it is very great for the expert, but it is scary for the beginner. That’s why I was drawn by the scala-excercises description. It is just disappointing, that it does not seem to work as the page claims.

So here is an example of something that is completely unobvious to me using scalatest. This is the content of my file. The editor (and I presume also scalar), cannot resolve `Generator` nor `forAll` .

``````import org.scalatest._
import robdd._

class BddSuite2 extends FunSuite {
test("bdd with ScalaCheck") {

val intGen: Generator[Int] = for {
i <- Bdd.genNumVars(6)
} yield i

val bddGen: Generator[Bdd] = for {
i <- intGen
}
yield Bdd.genRandomBdd(i)

forAll { b: Bdd => {
b == Not(Not(b))
}
}
}
}
`````` What should I try to make it work?

You need to home in on one approach - ScalaTest `Generator` != ScalaCheck `Gen`. Furthermore, if you want to go with ScalaCheck, you must import ScalaCheck (ScalaTest only provides integration bindings, not the ScalaCheck API itself) and mix in `GeneratorDrivenPropertyChecks`.

Assume you have this code:

``````sealed trait BoolExp {
def apply(): Boolean
}

case object True extends BoolExp {
override def apply(): Boolean = true
}

case object False extends BoolExp {
override def apply(): Boolean = false
}

case class Not(exp: BoolExp) extends BoolExp {
override def apply(): Boolean = !exp()
}

case class And(a: BoolExp, b: BoolExp) extends BoolExp {
override def apply(): Boolean = a() && b()
}

case class Or(a: BoolExp, b: BoolExp) extends BoolExp {
override def apply(): Boolean = a() || b()
}
``````

Then this code (in the same package in the test folder) should work:

``````import org.scalacheck._
import org.scalatest._
import org.scalatest.prop._

class BoolExpTest
extends FunSuite
with Matchers
with GeneratorDrivenPropertyChecks {

private val boolExpGen: Gen[BoolExp] = {
import Gen._
val exp = lzy(boolExpGen)
Gen.oneOf(
const(True),
const(False),
exp.map(Not),
for(a <- exp; b <- exp) yield And(a, b),
for(a <- exp; b <- exp) yield Or(a, b)
)
}

private implicit val arbitraryBoolExp: Arbitrary[BoolExp] =
Arbitrary(boolExpGen)

test("double negation") {
forAll { exp: BoolExp =>
Not(Not(exp))() should be (exp())
}
}

}
``````

You may want to tweak configuration parameters and/or throw in sized generators later for better control of the tree shape, perhaps.

Best regards,
Patrick

1 Like

Note that this is all a little complex. The above link to “the ScalaTest way” isn’t actually the ScalaTest way – it’s ScalaTest-plus-ScalaCheck. So you are going to need both ScalaTest imports (for the `extends FunSuite` and the test syntax) and ScalaCheck imports (for `Generator` and `forAll` and such).

OTOH, as of ScalaTest 3.1, similar functionality has been built into ScalaTest proper. That will be available as `org.scalatest.prop._` IIRC. But it’s new enough (like, I was working on it in January) that you may not want to get into it right now.

(As @sangamon alludes to, one way to tell the difference between the two is that ScalaCheck uses `Gen`, and the new ScalaTest version uses `Generator`. There are a bunch of little differences like that in the details, but conceptually both systems do the same stuff.)

Yeah, I’m a bit surprised – they tend to be good about this stuff, but appear to have overlooked some details in their introductions in this case.

And yeah, the ScalaTest docs can be a bit overwhelming. We do our best (and I take some pride in the new docs for the `prop` package), but are sorry when it isn’t clear…

Thanks Patrick, I’m trying to re-intepret that helpful piece of code into my application.
Can you explain what `should be` is? Is it commutative? I.e., is `a should be b` the same as `b should be a`?

Also, can you please explain whether the `private` indication is necessary. I’m probably going to eventually want to use Bdd generators in several different classes. Not now, but in the coming weeks.

Is it a problem that I’ve redefined the `equals` method? In my case I have redefined `equals` for the Bdd class to be `eq`. I.e., I want copies of object to be unequal. Is this compatible with the `should be` operator?

``````sealed abstract class Bdd (val ident:Int) {
override def equals(that: Any): Boolean = {
that match {
case b: Bdd => this eq b
case _ => false
}
}
...
``````

Quick summary: ScalaTest is really, really fond of having its own little DSL. There are many dialects of it; which version you have available depends on your imports and/or mixed-in traits. The general buzzword here is “Matchers”, and it’s well worth familiarizing yourself with the Scaladocs for Matchers – I look at that page frequently when using ScalaTest.

So `should be` is basically just a synonym for equality, as an assertion. It produces slightly nicer output on failure than plain `assert()`, but the semantics are largely `assert(a == b)`.

Also back to the original question, because I think I’m getting close to making it work.
I have a function which will generate a random integer with the distribution I want. I.e., given a maximum N, it will return an integer between 1 and N, with 1 being twice as likely as 2, and 2 being twice as likely as 3 etc. And given such an integer I have a function which will generate a random Bdd with that many levels.

``````object Bdd {
...

val rgen = scala.util.Random

def genRandomBdd(N: Int): Bdd = {
def recur(level: Int): Bdd = {
val r = rgen.nextInt(2)
(r, level) match {
case (0, N) => BddTrue
case (1, N) => BddFalse
case (0, _) => recur(level + 1)
case (_, _) => Bdd(level + 1, recur(level + 1), recur(level + 1))
}
}
recur(0)
}

def genNumVars(N:Int):Int = {
// Generate an integer between 1 and N inclusive with a special distribution.
// 1 is twice as likely as 2
// 2 is twice as likely as 3
// k is twice as likely as k+1 for each k>=1
def recur(acc: Int, remaining: Int): Int = {
(rgen.nextInt(2), acc, remaining) match {
case (_, _, 0) => acc
case (1, _, _) => recur(1 + acc, remaining - 1)
case (_, _, _) => recur(acc, remaining - 1)
}
}
recur(0, N)
}
}
``````

So here is what I’ve attempted based on Patrick’s example, but it’s not quite right yet.

``````import org.scalacheck._
import org.scalatest._
import org.scalatest.prop._
import robdd._

class BddSuite2 extends FunSuite
with Matchers
with GeneratorDrivenPropertyChecks {

val intGen: Gen[Int] = for {
i <- Bdd.genNumVars(6)
} yield i

val bddGen: Gen[Bdd] = for {
i <- intGen
} yield Bdd.genRandomBdd(i)

private implicit val arbitraryBdd: Arbitrary[Bdd] = Arbitrary(bddGen)

test("bdd double negation") {
forAll { b: Bdd =>
Not(Not(b)) should be(b)
}
}
}
``````

The compiler error I get is the following.

``````Error:(11, 26) value map is not a member of Int
i <- Bdd.genNumVars(6)
``````

Maybe someone can point out what’s wrong. Or am I completely on the wrong path altogether?

And If I’ve overridden `==` to mean `eq`, the `should be` respects that?

It’s not strictly a problem – folks do that all the time – but note that it is surprisingly dangerous, and tricky to get right. Suffice it to say, in the presence of possible sub-classes, there are a variety of possible traps. (So long as you’re not subclassing `Bdd` it’s probably fine, but I recommend thinking of this as a danger zone.)

Also, it is usually recommended to redefine `hashCode` if you are redefining `equals` – while it’s not strictly required, lots of code assumes that these behave in sync, so it’s easy to get into unobvious trouble if you override one and not the other.

That’s an extremely good question, and I don’t know offhand. I recommend reading through the Matchers section on checking equality.

Can I just replace `Not(Not(b)) should be(b)` with `assert(b == Not(Not(b)))` and dispense with the matchers?

The compiler error is correct, if a bit unhelpful.

The thing is, `Gen` is a Monad – which in squishy Scala terms means that it has definitions for the `map` and `flatMap` functions. Those functions are what allows a type to be used in a `for` comprehension – the `for` literally gets translated into calls to them.

`genNumVars()` returns a plain `Int`. `Int` isn’t a Monad, so it’s illegal to use in `for` because it doesn’t have a concept of `map`. You can’t just take any random value and casually use it as a `Gen` – you have to either start from an existing `Gen`, or use a utility function that turns your value into one.

So I guess the question is, what are you trying to do here? A `Gen` is, as the name suggests, a Generator – it produces a sequence of values of a desired type. `intGen` doesn’t really makes sense: it’s just taking one `Int`, the output of `genNumVars`. Which I think is legal, and there’s probably a utility function to do that in ScalaCheck, but I suspect isn’t what you want.

BTW, I should note that there’s a good (if somewhat out of date) book on ScalaCheck. This comes with a disclaimer that my boss is the publisher, but it’s basically how I learned this stuff.

Likely yes. The failure output won’t be as pretty and informative, but it ought to work.