basic-sop- Basic examples and functions for generics-sop

Safe HaskellNone




Generic generation of random test cases.

This module contains a generic version of arbitrary from the Test.Quickcheck library, using generics-sop.



garbitrary :: forall a. (Generic a, All2 Arbitrary (Code a)) => Gen aSource

Generic generation of random test cases.

This function is a proof-of-concept implementation of a generic arbitrary that can be used to instantiate the Arbitrary class in QuickCheck.

If you want to use it on a datatype T for which you have a Generic instance, you can say:

 instance Arbitrary T where
   arbitrary = garbitrary

Note that currently no attempts are being made to generate arbitrary values of a particular size, and it is possible that this function diverges for recursive structures.


class Arbitrary a where

Random generation and shrinking of values.


arbitrary :: Gen a

A generator for values of the given type.

shrink :: a -> [a]

Produces a (possibly) empty list of all the possible immediate shrinks of the given value. The default implementation returns the empty list, so will not try to shrink the value.

Most implementations of shrink should try at least three things:

  1. Shrink a term to any of its immediate subterms.
  2. Recursively apply shrink to all immediate subterms.
  3. Type-specific shrinkings such as replacing a constructor by a simpler constructor.

For example, suppose we have the following implementation of binary trees:

 data Tree a = Nil | Branch a (Tree a) (Tree a)

We can then define shrink as follows:

 shrink Nil = []
 shrink (Branch x l r) =
   -- shrink Branch to Nil
   [Nil] ++
   -- shrink to subterms
   [l, r] ++
   -- recursively shrink subterms
   [Branch x' l' r' | (x', l', r') <- shrink (x, l, r)]

There are a couple of subtleties here:

  • QuickCheck tries the shrinking candidates in the order they appear in the list, so we put more aggressive shrinking steps (such as replacing the whole tree by Nil) before smaller ones (such as recursively shrinking the subtrees).
  • It is tempting to write the last line as [Branch x' l' r' | x' <- shrink x, l' <- shrink l, r' <- shrink r] but this is the wrong thing! It will force QuickCheck to shrink x, l and r in tandem, and shrinking will stop once one of the three is fully shrunk.

There is a fair bit of boilerplate in the code above. We can avoid it with the help of some generic functions; note that these only work on GHC 7.2 and above. The function genericShrink tries shrinking a term to all of its subterms and, failing that, recursively shrinks the subterms. Using it, we can define shrink as:

 shrink x = shrinkToNil x ++ genericShrink x
     shrinkToNil Nil = []
     shrinkToNil (Branch _ l r) = [Nil]

genericShrink is a combination of subterms, which shrinks a term to any of its subterms, and recursivelyShrink, which shrinks all subterms of a term. These may be useful if you need a bit more control over shrinking than genericShrink gives you.

A final gotcha: we cannot define shrink as simply shrink x = Nil:genericShrink x as this shrinks Nil to Nil, and shrinking will go into an infinite loop.

If all this leaves you bewildered, you might try shrink = genericShrink to begin with, after deriving Generic and Typeable for your type. However, if your data type has any special invariants, you will need to check that genericShrink can't break those invariants.