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:

- emptyProduct -- which returns a Shrink instance for a 0-ary product
- emptyCoproduct -- which returns a Shrink instance for a 0-ary coproduct
- product -- which returns a Shrink instance for an HList (A :: B :: Nil)
- coproduct -- which returns a Shrink instance for a Coproduct (A :+: B )
- project -- given an Shrink[B], a A=>B and a B=>A, create a Shrink[A]. This is so that if we can convert value of some type A to a Coproduct of Products, from which we can derive a typeclass instance using the above 4 methods, we can then create a typeclass instance for A

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.