High-Order ScalaCheck

Question

Consider the following definition of a category:

trait Category[~>[_, _]] {
  def id[A]: A ~> A
  def compose[A, B, C](f: A ~> B)(g: B ~> C): A ~> C
}

Here's an instance for unary functions:

object Category {
  implicit def fCat = new Category[Function1] {
    def id[A] = identity
    def compose[A, B, C](f: A => B)(g: B => C) = g.compose(f)
  }
}

Now, categories are subject to some laws. Relating composition (.) and identity (id):

forall f: categoryArrow -> id . f == f . id == f

I want to test this with ScalaCheck. Let's try for functions over integers:

"Categories" should {
  import Category._

  val intG  = { (_ : Int) - 5 }

  "left identity" ! check {
    forAll { (a: Int) => fCat.compose(fCat.id[Int])(intG)(a) == intG(a) }      
  }

  "right identity" ! check {
    forAll { (a: Int) => fCat.compose(intG)(fCat.id)(a) == intG(a) }      
  }
}

But these are quantified over (i) a specific type (Int), and (ii) a specific function (intG). So here's my question: how far can I go in terms of generalizing the above tests, and how? Or, in other words, would it be possible to create a generator of arbitrary A => B functions, and provide those to ScalaCheck?

Answer 1

Not knowing exactly with Hilbert's epsilon is, I would take a more fundamental approach and use ScalaCheck's Arbitrary and Gen to select functions to use.

First, define a base class for the functions you are going to generate. In general, it's possible to generate functions that have undefined results (such as divide by zero), so we'll use PartialFunction as our base class.

trait Fn[A, B] extends PartialFunction[A, B] {
  def isDefinedAt(a: A) = true
}

Now you can provide some implementations. Override toString so ScalaCheck's error messages are intelligible.

object Identity extends Fn[Int, Int] {
  def apply(a: Int) = a
  override def toString = "a"
}
object Square extends Fn[Int, Int] {
  def apply(a: Int) = a * a
  override def toString = "a * a"
}
// etc.

I've chosen to generate unary functions from binary functions using case classes, passing additional arguments to the constructor. Not the only way to do it, but I find it the most straightforward.

case class Summation(b: Int) extends Fn[Int, Int] {
  def apply(a: Int) = a + b
  override def toString = "a + %d".format(b)
}
case class Quotient(b: Int) extends Fn[Int, Int] {
  def apply(a: Int) = a / b
  override def isDefinedAt(a: Int) = b != 0
  override def toString = "a / %d".format(b)
}
// etc.

Now you need to create a generator of Fn[Int, Int], and define that as the implicit Arbitrary[Fn[Int, Int]]. You can keep adding generators until you're blue in the face (polynomials, composing complicated functions from the simple ones, etc).

val funcs = for {
  b <- arbitrary[Int]
  factory <- Gen.oneOf[Int => Fn[Int, Int]](
    Summation(_), Difference(_), Product(_), Sum(_), Quotient(_),
    InvDifference(_), InvQuotient(_), (_: Int) => Square, (_: Int) => Identity)
} yield factory(b)

implicit def arbFunc: Arbitrary[Fn[Int, Int]] = Arbitrary(funcs)

Now you can define your properties. Use intG.isDefinedAt(a) to avoid undefined results.

property("left identity simple funcs") = forAll { (a: Int, intG: Fn[Int, Int]) =>
  intG.isDefinedAt(a) ==> (fCat.compose(fCat.id[Int])(intG)(a) == intG(a))
}

property("right identity simple funcs") =  forAll { (a: Int, intG: Fn[Int, Int]) =>
  intG.isDefinedAt(a) ==> (fCat.compose(intG)(fCat.id)(a) == intG(a))
}

While what I've shown only generalizes the function tested, hopefully this will give you an idea on how to use advanced type system trickery to generalize over the type.