# Testing

By far the most widely used style of testing today is unit testing.

• Invent a "state of the world".

• Run the unit we're testing (e.g. a function).

• Check the modified state of the world to see if it looks like it should.

• Profit!

# Shameless Wikipedia pillaging

If you're used to unit testing, this may look reasonable.

``public class TestAdder {    public void testSum() {        Adder adder = new AdderImpl();        assert(adder.add(1, 1) == 2);        assert(adder.add(1, 2) == 3);        assert(adder.add(2, 2) == 4);        assert(adder.add(0, 0) == 0);        assert(adder.add(-1, -2) == -3);        assert(adder.add(-1, 1) == 0);        assert(adder.add(1234, 988) == 2222);    }}``

The "real world" adds tons of cruft: mock objects, preprocessor abuse to expose "test seams", etc.

# Problem: unit testing is only as good as your patience

The example from the previous slide contains 7 tests.

It's not hard to imagine a world in which we lose the will to continue inventing new unit tests long before we've exhausted our search of the space of possible bugs.

# Let's sort a list

``mergeSort :: (a -> a -> Bool) -> [a] -> [a]mergeSort pred = go  where    go []  = []    go [x] = [x]    go xs  = merge (go xs1) (go xs2)      where (xs1,xs2) = split xs    merge xs [] = xs    merge [] ys = ys    merge (x:xs) (y:ys)      | pred x y  = x : merge xs (y:ys)      | otherwise = y : merge (x:xs) ys``

# The split function

The purpose of splitting is to produce two sublists of roughly equal length, so that they can be merged (where the sorting occurs).

``split :: [a] -> ([a],[a])split []       = ([],[])split [x]      = ([x],[])split (x:y:zs) = (x:xs,y:ys)  where (xs,ys) = split zs``

# Sorting: a unit test perspective

``````sort [1,2,3,4] == [1,2,3,4]
sort [4,3,2,1] == [1,2,3,4]
sort [1,4,2,3] == [1,2,3,4]
...
``````

This gets a little dull.

A property is nothing more than a predicate that should always hold.

What's an obvious property for sorts?

``t_idempotent = sort . sort == sort``

We can't define this, since we can't compare functions for equality.

However, we can cheat:

``t_idempotent xs =     sort (sort xs) == sort xs``

# Why don't we do it in the interpreter

``t_idempotent [3,2,1]``

Okay! Let's mechanize some exhaustive testing.

To exhaustively test over all lists containing the above elements, we need some help.

``import Data.List (permutations)t_permute :: ([a] -> Bool) -> [a] -> Boolt_permute prop = all prop . permutations``

Over what list sizes is this practical?

# Exhausted testing?

Clearly, exhaustive testing is impractical for most interesting purposes.

The insight of QuickCheck:

• Combine property-based testing with randomly generated data.

• This obviously can't give us the same assurance as exhaustive testing, but it's practical.

• We can choose the amount of data to throw at our properties.

• This lets us tune the tradeoff between degree of assurance and cost.

# Let's give it a try

At the `ghci` prompt:

``````>> import Test.QuickCheck
>> quickCheck (t_idempotent compare)
+++ OK, passed 100 tests.
``````

As the output suggests, QuickCheck generated 100 random lists, and tested our property over them.

Yay!

# Something funky is going on

The type of `compare` is polymorphic:

``````>> :type t_idempotent compare
t_idempotent compare :: Ord a => [a] -> Bool
``````

So how are we able to generate a list?

# Type defaulting - a recap

Haskell's usual defaulting rules take each group of constraints `(C1 a, C2 a, ..., Cn a)` for each type variable `a`, and defaults the type variable if all of the following conditions hold:

• The type variable `a` appears in no other constraints.

• All the classes `Ci` are standard.

• At least one of the classes `Ci` is numeric.

# That's not enough for us lazy programmers!

To reduce the number of types we're forced to specify by hand, `ghci` relaxes the standard rules (changes in italics):

• The type variable `a` appears in no other constraints. Unchanged.

• All the classes `Ci` are standard, and all are single-parameter type classes.

• At least one of the classes `Ci` is numeric, or is `Show`, `Eq`, or `Ord`.

It also adds another critical step when defaulting:

• The type `()` becomes the first of the the standard list of types tried when doing type defaulting.

# Peek inside

We can use the `verboseCheck` function to see all the test data that QuickCheck is generating for us.

``````>> verboseCheck (t_idempotent compare)
``````

Notice that we have endless lists of `()`?

Our supposedly reassuring test isn't very useful!

# Polymorphic testing

When we're testing a polymorphic property, we need to specify which concrete type we're testing at.

``````>> import Data.Word (Word8)
>> verboseCheck (t_idempotent (compare :: Word8 -> Word8 -> Ordering))
``````

That's verbose and unhappy-making, right?

# Enter the type synonym

Here's one approach to reducing our work:

``type Cmp a = a -> a -> Ordering``

Trying this at the `ghci` prompt:

``````>> import Data.Word (Word8)
>> verboseCheck (t_idempotent (compare :: Cmp Word8))
``````

# Witness the fitness

Here's an alternative approach:

``````t_witnessed p a xs = mergeSort p (mergeSort p xs) == mergeSort p xs
where _witness = a < head xs
``````

What's that `_witness` variable for?

• It's a type witness, a value that exists to express a constraint between several types (it "witnesses" the constraint).

• Thanks to the use of `<`, this witness forces the type of `a` and the type of the elements of `xs` to be the same.

(We prefix the name with an underscore to tell GHC that it's an unused wild card.)

# Instantiating our new polymorphic test

We can supply a value for `a` of the appropriate type to test over:

``````>> verboseCheck (t_witnessed compare 'a')
``````

Of course, the value of `a` is never used.

As a result, we don't even need to supply a working value, provided the type of what we supply is correct:

``````>> verboseCheck (t_witnessed compare (undefined::Double))
``````

# Where do random values come from?

To generate random values of some type, we must write an `Arbitrary` instance for it.

``class Arbitrary a where  arbitrary :: Gen a``

Here's an example, making use of the fact that this unknown type `Gen` is an instance of `Monad`:

``data Point = Point Int Intinstance Arbitrary Point where    arbitrary = do      x <- arbitrary      y <- arbitrary      return (Point x y)``

# Lifting

We're hopefully by now familiar with the `Functor` class:

``class Functor f  where    fmap :: (a -> b) -> f a -> f b``

This takes a pure function and "lifts" it into the functor `f`.

In general, "lifting" takes a concept and transforms it to work in a different (sometimes more general) setting.

For instance, we can define lifting of functions with the `Monad` class too:

``liftM :: (Monad m) => (a -> b) -> m a -> m bliftM f action = do  b <- action  return (f b)``

# fmap and liftM

Notice the similarities between the type signatures:

``fmap  :: (Functor f) => (a -> b) -> f a -> f bliftM :: (Monad m)   => (a -> b) -> m a -> m b``

All instances of `Monad` can possibly be instances of `Functor`. Ideally, they'd be defined in terms of each other:

``class (Functor m) => Monad m where    {- blah blah -}``

For historical reasons, the two classes are separate, so we write separate instances for them and just reuse the code:

``instance Monad MyThingy where    {- whatever -}instance Functor MyThingy where    fmap = liftM``

# Why the apparent digression?

It turns out that lifting pure functions into monads is really common.

So common, in fact, that `Control.Monad` defines a bunch of extra combinators for us.

``liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m bliftM2 f act1 act2 = do  a <- act1  b <- act2  return (f a b)``

These combinators go all the way up to `liftM5`.

Look familiar? Useful?

# A tighter Arbitrary instance

Before:

``instance Arbitrary Point where    arbitrary = do      x <- arbitrary      y <- arbitrary      return (Point x y)``

After:

``import Control.Monad (liftM2)instance Arbitrary Point where    arbitrary = liftM2 Point arbitrary arbitrary``

# Trying something else

Suppose we want to verify that the sum of two odd integers is always even.

Here's a quick and obvious property:

``p_sum_odd a b    | odd a && odd b = even (a + b)    | otherwise      = True``

This looks a little crufty, though.

• We're returning `True` even in instances where the property really isn't defined.

# Conditional properties

It would be nice if we could express the idea "check this property only if the inputs satisfy these constraints".

In fact, there's a combinator for that: `==>`

``p_sum_odd1 a b =    odd a && odd b ==>     even (a+b)``

This specifies that the property on the right should hold whenever the `Bool`-valued test on the left succeeds.

QuickCheck will discard inputs for which the test fails.

# Limits on conditional properties

Suppose we try to test this property:

``p_odd3 a b c = odd a && odd b && odd c ==> odd (a+b+c)``

We'll get a strange error from QuickCheck:

``````>> quickCheck p_odd
*** Gave up! Passed only 79 tests.
``````

None of our tests failed, but QuickCheck puts an upper limit on the number of test cases it will generate.

• This avoids an infinite loop if the condition before the property never holds.

• Here, we hit the limit because almost 90% of our inputs are discarded. Why are they discarded?

# Correctness by construction

Instead of filtering out data that isn't right for us, it's better to generate only data that is right.

``````newtype Odd a = Odd a
deriving (Show)

instance (Integral a, Arbitrary a) => Arbitrary (Odd a) where
arbitrary = do
a <- arbitrary
return \$! Odd (if even a then a + 1 else a)
``````

It's clear from inspection that the `Arbitrary` instance for `Odd a` will only generate odd-valued integers.

# Can I get a witness?

We no longer need a conditional property now, since all of our property's parameters must by necessity be odd:

``p_odd1 x (Odd a) (Odd b) (Odd c) = odd (a+b+c)  where _witness = x == a``

Let's run it:

``````>> quickCheck \$ p_odd1 (1::Int)
+++ OK, passed 100 tests.
``````

Sweet! We saved ourselves from generating a ton of useless data, made the testing process faster, and cleaned up the property some too.

# Sizing a test

Test data generators have an implicit size parameter, hidden inside the `Gen` type.

QuickCheck starts by generating small test cases; it increases the size as testing progresses.

The meaning of "size" is specific to the needs of an `Arbitrary` instance.

• The `Arbitrary` instance for lists interprets it as "the maximum length of a list of arbitrary values".

We can find the current size using the `sized` function, and modify it locally using `resize`:

``sized  :: (Int -> Gen a) -> Gen aresize ::  Int -> Gen a  -> Gen a``

# Testing a recursive data type

Suppose we have a tree type:

``data Tree a = Node (Tree a) (Tree a)            | Leaf a              deriving (Show)``

Here's an obvious `Arbitrary` instance:

``instance (Arbitrary a) => Arbitrary (Tree a) where    arbitrary = oneof [                  liftM Leaf arbitrary                , liftM2 Node arbitrary arbitrary                ]``

The `oneof` combinator chooses a generator at random.

``oneof :: [Gen a] -> Gen a``

# What's up, Doc?

Potential trouble:

• This generator may not terminate at all!

• It's likely to produce huge trees.

We can use the `sample` function to generate and print some arbitrary data.

``sample :: (Show a) => Gen a -> IO ()``

This helps us to explore what's going on.

# A safer instance

Here's where the sizing mechanism comes to the rescue.

``instance (Arbitrary a) => Arbitrary (Tree a) where    arbitrary = sized treetree :: (Arbitrary a) => Int -> Gen (Tree a)tree 0 = liftM Leaf arbitrarytree n = oneof [           liftM  Leaf arbitrary         , liftM2 Node subtree subtree         ]  where subtree = tree (n `div` 2)``

# Sorting revisited

A very desirable property of a sorting algorithm is stability.

The built-in `sort` and `sortBy` functions are designed to be stable.

What about our `mergeSort`? Let's find out.

``import Data.Function (on)import Data.List (sortBy)import Data.Word (Word8)p_stable xs = merged == sorted  where merged = mergeSort (compare `on` fst) xs        sorted = sortBy    (compare `on` fst) xs        _witness = xs :: [(Word8, Word8)]``

That `on` function is pretty neat:

``on :: (b -> b -> c) -> (a -> b) -> a -> a -> c(*) `on` f = \x y -> f x * f y``