Coursera Reactive Scala Programming #1 - Quickcheck

QuickCheck.scala

package quickcheck

import common._

import org.scalacheck._
import Arbitrary._
import Gen._
import Prop._
import Math._

abstract class QuickCheckHeap extends Properties("Heap") with IntHeap {

  lazy val genHeap: Gen[H] = for {
    n <- arbitrary[A]
    h <- frequency((1, value(empty)), (9, genHeap))
  } yield insert(n, h)

  property("hint1") = forAll { (n1: A, n2: A) =>
    val h = insert(n1, insert(n2, empty))
    findMin(h) == min(n1, n2)
  }

  property("hint2") = forAll { (n: A) =>
    isEmpty(deleteMin(insert(n, empty)))
  }

  property("hint3") = forAll { (h: H) =>
    def isSorted(h: H): Boolean =
      if (isEmpty(h)) true
      else {
        val m = findMin(h)
        val h2 = deleteMin(h)
        isEmpty(h2) || (m <= findMin(h2) && isSorted(h2))
      }
    isSorted(h)
  }

  property("hint4") = forAll { (h1: H, h2: H) =>
    findMin(meld(h1, h2)) == min(findMin(h1), findMin(h2))
  }

  /* https://class.coursera.org/reactive-001/forum/thread?thread_id=97#post-371 */
  property("meld") = forAll { (h1: H, h2: H) =>
    def heapEqual(h1: H, h2: H): Boolean =
      if (isEmpty(h1) && isEmpty(h2)) true
      else {
        val m1 = findMin(h1)
        val m2 = findMin(h2)
        m1 == m2 && heapEqual(deleteMin(h1), deleteMin(h2))
      }
    heapEqual(meld(h1, h2),
              meld(deleteMin(h1), insert(findMin(h1), h2)))
  }

  implicit lazy val arbHeap: Arbitrary[H] = Arbitrary(genHeap)

}

this came in handy, thanks!

Hi @wh5a, I've tried this gist in Eclipse and the code is not compiling.

The value(empty) in the genHeap function is causing the error.

Any help?

Gen.const(empty) for ScalaCheck 1.12.1

That works @hveiga. Thanks for the help ✌️

One more property is missed for 10/10 Points :)
property("nw1") = forAll { (h1: H, h2: H) =>
val m1 = findMin(h1)
val m2 = findMin(h2)
val min = m1.min(m2)
findMin(meld(deleteMin(h1),insert(min,h2)))==min
}

@hveiga cheers!