Screencast demonstrating Shrink instances in scalacheck

I recently recorded myself live-coding some examples of using scalacheck for some property based testing, with a concentration of how to use the Shrink functionality of scalacheck which will minimize failed test cases.

In the video I also demonstrate how one can use the automatic TypeClass derivation for both Arbitrary and Shrink which now exist in the shapeless-contrib. I only added the typeclass derivation for Shrink to shapeless-contrib very recently, so as of this writing, I don't believe it has yet made it into a released version of shapeless-contrib, which is why you'll see my using a -SNAPSHOT version in this video.

The typeclass derivation stuff is very very cool. The idea is that if you can describe how to construct an arbitrary typeclass given either an arbitrary Product (in the form of an HList), or an arbitrary Coproduct, then shapeless will do the work of translating providing typeclass instances for any type it can convert into a combination of Products and Coproducts. So perhaps it makes sense for me here to take a short amount of space in order to butcher a rough definition of what a Product and a Coproduct are...

Products

I'll write a product using the fancy ∏ (N-ARY PRODUCT) symbol, because I'm fancy like that. When you see it, think of the word "and". So a product: String ∏ Int you can think of as "A String and an Int". Think of String ∏ Int ∏ Int as "A String and an Int and another Int". Here are some scala type which are isomorphic to (the same shape as) String ∏ Int ∏ Int:

    (String,Int,Int) // aka Tuple3[String,Int,Int]
    case class Person(name: String, age: Int, height: Int)

In shapeless, Product types are represented as HLists, and example HList might have the type String :: Int :: Int :: HNil

Coproducts

I'll write a coproduct using the fancy ∐ symbol (N-ARY COPRODUCT), since I'M STILL THAT FANCY. When you see it, you can think of the work "or", so String ∐ Int can be read as "A String OR an Int". A scala type which is isomorphic to String ∐ Int would be:

    sealed trait StringOrInteger
    case class S(str: String) extends StringOrInt
    case class I(int: Int) extends StringOrInt

The shapeless encoding of a coproduct is this:

    sealed trait Coproduct
    sealed trait :+:[+H, +T <: Coproduct] extends Coproduct
    final case class Inl[+H, +T <: Coproduct](head : H) extends :+:[H, T]
    final case class Inr[+H, +T <: Coproduct](tail : T) extends :+:[H, T]

So the type of a coproduct would be something like String :+: Int, and a value of that type would either be an Inl(string) or an Inr(int). These can be combined into larger coproducts. We can have a String :+: Int :+: Float which be any of a Inl(String) or an Inr(Inl(Int)) or an Inr(Inr(Float)).

Algebraic Data Types

Products and Coproducts can be combined to create more general Algebraic Data Types. Here is a type in scala:

    sealed trait Thing
    case class Person(name: String, age: Int) extends Thing
    case class Place(name: String, lat: Double, long: Double) extends Thing
    case class ContainerOfBeer(firkins: Float) extends Thing

And this type Thing is isomorphic to the coproduct of products: (String ∏ Int) ∐ (String ∏ Double ∏ Int) ∐ (Float). Or in shapeless types, (String :: Int :: HNil) :+: (String :: Double :: Int :: HNil) :+: (Float)

Typeclass derivation

So now that we know what a product and coproduct are, let's have a look at how the automatic typeclass derivation in shapeless-contrib is actually put together. As a review from the video above, what a Shrink instance is, is a way of taking some value, and returning a stream of "smaller" values of that same type. So for a String value, such as "asdf", "smaller" values might be "asd", "sdf", "adf", "as", "af", "", etc.

Now, in order to create arbitrary Shrink instances, we need to implement 5 methods:

The first two we can implement trivially, by returning a Shrink which just emits an empty Stream

    def emptyProduct = Shrink(_ => Stream.empty)
    def emptyCoproduct: Shrink[CNil] = Shrink(_ => Stream.empty)

The next easiest to implement is Coproduct. For this, we are given an A or a B, we just have to see which we have, then shrink it:

    def coproduct[L, R <: Coproduct](sl: => Shrink[L], sr: => Shrink[R]) = Shrink { lr =>
      lr match {
        case Inl(l) => sl.shrink(l).map(Inl.apply)  // if it is a left, shrink the left, put the results back on the left
        case Inr(r) => sr.shrink(r).map(Inr.apply)  // if it is a right, shrink the right, put the results back on the right
      }
    }

For product, given a way to Shrink As and a way to Shrink Bs we can implement a way to Shrink (A ∏ B ) by getting a stream of shrunken As and appending to it a stream of shrunken Bs

    def product[F, T <: HList](f: Shrink[F], t: Shrink[T]) = Shrink { case a :: b =>
      f.shrink(a).map( _ :: b) append  // shrink the As, leave the Bs alone
      t.shrink(b).map(a :: _)          // shrink the Bs, leave the As alone
    }

for project, we convert our value into the shapeless equivalent, shrink that using the automatically derived shrink instance, then convert the result values back to the 'goal' type

    def project[A, B](bshrinker: => Shrink[B],  // automatically derived from above 4 methods
                      ab: A => B,               // a way to convert from A a shapeless representation
             ba: B => A) =             // a way to convert back to As
      Shrink { a =>                             // given an A
        val bvalue = ab(a)                      // convert the A that needs to be shrunk to a B which we know how to shrink
        val shrunkenB: Stream[B] = b.shrink(bvalue) // shrink the b
        val shrunkenA: Stream[A] = shrunkenB map ba // convert the shrunken Bs to As
        shrunkenA
      }

And that's it, Now, anywhere we import shapeless.scalacheck._, we will have implicit[Shrink[A]] instances in scope for any A for which shapeless can convert the type into a coproduct of products, which I believe is tuples, case classes and sealed traits of case classes. You can see the full source for Shrink derivation here here. I'm looking forward to seeing more of these automatically derived typeclasses become available in the future.