gistfile1.txt

object Generators {

  /** Given as an example of how to combine 2 generators. */
  val pairs: Generator[(Int, Int)] = for {
    x <- integers
    y <- integers
  } yield (x, y)

  val pairDesugared: Generator[(Int, Int)] = integers flatMap {
    x => integers map { y => (x, y) }
  }

  /** Used as an example to show how generators are used. */
  def test[T](numTimes: Int)(g: Generator[T])(test: T => Boolean) {
    for (i <- 0 until numTimes) {
      val value = g.generate
      assert(test(value), value)
    }
  }

  /** Here we show what the intent is. */
  def main(args: Array[String]) {
    test(10)(trees(-10, 10)) {
      t => println(t); true
    }
  }

  /* from the exercise */

  def emptyLists: Generator[List[Int]] = single(Nil)

  def nonEmptyLists: Generator[List[Int]] = for {
    head <- integers
    tail <- lists
  } yield head :: tail

  def lists: Generator[List[Int]] = for {
    cutoff <- booleans
    list <- if (cutoff) emptyLists else nonEmptyLists
  } yield list

  /* recitation session */

  trait Generator[+T] {
    self =>

    def generate: T

    def map[S](f: T => S): Generator[S] = new Generator[S] {
      def generate = f(self.generate)
    }

    def flatMap[S](f: T => Generator[S]): Generator[S] = new Generator[S] {
      def generate = f(self.generate).generate
    }
  }

  def single[T](x: T): Generator[T] = new Generator[T] {
    def generate = x
  }

  def integers: Generator[Int] = new Generator[Int] {
    def generate = scala.util.Random.nextInt()
  }

  def booleans: Generator[Boolean] = integers.map(_ >= 0)

  def choose(minvalue: Int, maxvalue: Int) = for (v <- integers) yield {
    minvalue + math.abs(v) % (maxvalue - minvalue)
  }

  sealed trait Node

  case object Leaf extends Node

  case class Inner(value: Int, left: Node, right: Node) extends Node

  val leaves: Generator[Node] = single(Leaf)

  def inners(minvalue: Int, maxvalue: Int): Generator[Node] = for {
    value <- choose(minvalue, maxvalue)
    left <- trees(minvalue, value)
    right <- trees(value, maxvalue)
  } yield Inner(value, left, right)

  def trees(minvalue: Int, maxvalue: Int): Generator[Node] = for {
    isInner <- if (minvalue < maxvalue) booleans else single(false)
    node <- if (isInner) inners(minvalue, maxvalue) else leaves
  } yield node

}