How to use SmallCheck in Haskell?

Question

I am trying to use SmallCheck to test a Haskell program, but I cannot understand how to use the library to test my own data types. Apparently, I need to use the Test.SmallCheck.Series. However, I find the documentation for it extremely confusing. I am interested in both cookbook-style solutions and an understandable explanation of the logical (monadic?) structure. Here are some questions I have (all related):

• If I have a data type data Person = SnowWhite | Dwarf Integer, how do I explain to smallCheck that the valid values are Dwarf 1 through Dwarf 7 (or SnowWhite)? What if I have a complicated FairyTale data structure and a constructor makeTale :: [Person] -> FairyTale, and I want smallCheck to make FairyTale-s from lists of Person-s using the constructor?

  I managed to make quickCheck work like this without getting my hands too dirty by using judicious applications of Control.Monad.liftM to functions like makeTale. I couldn't figure out a way to do this with smallCheck (please explain it to me!).

• What is the relationship between the types Serial, Series, etc.?

• (optional) What is the point of coSeries? How do I use the Positive type from SmallCheck.Series?

• (optional) Any elucidation of what is the logic behind what should be a monadic expression, and what is just a regular function, in the context of smallCheck, would be appreciated.

If there is there any intro/tutorial to using smallCheck, I'd appreciate a link. Thank you very much!

UPDATE: I should add that the most useful and readable documentation I found for smallCheck is this paper (PDF). I could not find the answer to my questions there on the first look; it is more of a persuasive advertisement than a tutorial.

UPDATE 2: I moved my question about the weird Identity that shows up in the type of Test.SmallCheck.list and other places to a separate question.

Answer 1

NOTE: This answer describes pre-1.0 versions of SmallCheck. See this blog post for the important differences between SmallCheck 0.6 and 1.0.

SmallCheck is like QuickCheck in that it tests a property over some part of the space of possible types. The difference is that it tries to exhaustively enumerate a series all of the "small" values instead of an arbitrary subset of smallish values.

As I hinted, SmallCheck's Serial is like QuickCheck's Arbitrary.

Now Serial is pretty simple: a Serial type a has a way (series) to generate a Series type which is just a function from Depth -> [a]. Or, to unpack that, Serial objects are objects we know how to enumerate some "small" values of. We are also given a Depth parameter which controls how many small values we should generate, but let's ignore it for a minute.

instance Serial Bool where series _ = [False, True]
instance Serial Char where series _ = "abcdefghijklmnopqrstuvwxyz"
instance Serial a => Serial (Maybe a) where
  series d = Nothing : map Just (series d)

In these cases we're doing nothing more than ignoring the Depth parameter and then enumerating "all" possible values for each type. We can even do this automatically for some types

instance (Enum a, Bounded a) => Serial a where series _ = [minBound .. maxBound]

This is a really simple way of testing properties exhaustively—literally test every single possible input! Obviously there are at least two major pitfalls, though: (1) infinite data types will lead to infinite loops when testing and (2) nested types lead to exponentially larger spaces of examples to look through. In both cases, SmallCheck gets really large really quickly.

So that's the point of the Depth parameter—it lets the system ask us to keep our Series small. From the documentation, Depth is the

Maximum depth of generated test values

For data values, it is the depth of nested constructor applications.

For functional values, it is both the depth of nested case analysis and the depth of results.

so let's rework our examples to keep them Small.

instance Serial Bool where 
  series 0 = []
  series 1 = [False]
  series _ = [False, True]
instance Serial Char where 
  series d = take d "abcdefghijklmnopqrstuvwxyz"
instance Serial a => Serial (Maybe a) where
  -- we shrink d by one since we're adding Nothing
  series d = Nothing : map Just (series (d-1))

instance (Enum a, Bounded a) => Serial a where series d = take d [minBound .. maxBound]

Much better.

---

So what's coseries? Like coarbitrary in the Arbitrary typeclass of QuickCheck, it lets us build a series of "small" functions. Note that we're writing the instance over the input type---the result type is handed to us in another Serial argument (that I'm below calling results).

instance Serial Bool where
  coseries results d = [\cond -> if cond then r1 else r2 | 
                        r1 <- results d
                        r2 <- results d]

these take a little more ingenuity to write and I'll actually refer you to use the alts methods which I'll describe briefly below.

---

So how can we make some Series of Persons? This part is easy

instance Series Person where
  series           d = SnowWhite : take (d-1) (map Dwarf [1..7])
  ...

But our coseries function needs to generate every possible function from Persons to something else. This can be done using the altsN series of functions provided by SmallCheck. Here's one way to write it

 coseries results d = [\person -> 
                         case person of
                           SnowWhite -> f 0
                           Dwarf n   -> f n
                       | f <- alts1 results d ]

The basic idea is that altsN results generates a Series of N-ary function from N values with Serial instances to the Serial instance of Results. So we use it to create a function from [0..7], a previously defined Serial value, to whatever we need, then we map our Persons to numbers and pass 'em in.

---

So now that we have a Serial instance for Person, we can use it to build more complex nested Serial instances. For "instance", if FairyTale is a list of Persons, we can use the Serial a => Serial [a] instance alongside our Serial Person instance to easily create a Serial FairyTale:

instance Serial FairyTale where
  series = map makeFairyTale . series
  coseries results = map (makeFairyTale .) . coseries results

(the (makeFairyTale .) composes makeFairyTale with each function coseries generates, which is a little confusing)