# Quality assessment of Haskell programs

One of the greatest things about writing code in Haskell is the wonderful libraries (incidently, one of the worst things about writing code in Haskell is the libraries). In particular the libraries for assessing the quality of your own code. I’m especially found of:

• QuickCheck for a quick testing of the correctness of my code, by letting me specify the properties I want to check, and taking care of generating random test-cases.

• Criterion for checking the time performance of my code in a statistical sound manner. Taking care of dealing with the garbage collector and such like.

In this post I give a quick tour of how to use these libraries.

### Getting the libraries

Our first step is to install QuickCheck and Criterion:

``````\$ cabal install criterion quickcheck
``````

Now we are ready to go.

### Backstory

The standard list-based implementation of quicksort that you so often see, seems ripe for some optimisations:

``````quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort lesser ++ [p] ++ quicksort greater
where
lesser  = [ x | x <- xs, x < p]
greater = [ x | x <- xs, x >= p]
``````

One obvious optimisation could be to only traverse `xs` once, when partitioning the elements into lesser and greater (and equal) than `p`. Here is one implementation that uses `foldl'` for maximum performance (we hope):

``````kquicksort :: Ord a => [a] -> [a]
kquicksort []     = []
kquicksort (p:xs) = kquicksort lesser ++ equal ++ kquicksort greater
where
(lesser,equal,greater) = foldl' part ([],[p],[]) xs
part (l,e,g) x =
case compare x p of
LT -> (x : l, e, g)
GT -> (l, e, x : g)
EQ -> (l, x : e, g)
``````

### Checking some properties

The basic usage of QuickCheck is to specify the properties you care about as ordinary Haskell functions, and then you use the `quickCheck` function to check the properties. In the following I use `QC` as the qualified name for values from the QuickCheck library.

The first property we want to check is that `kquicksort` returns a sorted result. To check this property we also define a helper predicate `sorted` that checks that a list is sorted:

``````sorted :: Ord a => [a] -> Bool
sorted (x1:x2:xs) = x1 <= x2 && (sorted \$ x2:xs)
sorted _          = True

prop_sorted :: Ord a => [a] -> Bool
prop_sorted xs = sorted \$ kquicksort xs
``````

The next properties that we want to check could be that `kquicksort` is idempotent and if it is given an ordered argument it doesn’t mess it up:

``````prop_idempotent :: Ord a => [a] -> Bool
prop_idempotent xs = kquicksort xs == (kquicksort \$ kquicksort xs)

prop_ordered :: Ord a => QC.OrderedList a -> Bool
prop_ordered (QC.Ordered xs) = xs == kquicksort xs
``````

For `prop_ordered` we use the type class `OrderedList` to specify that this property should only hold for arguments that are sorted.

Now we can use the `quickCheck` function to check all our properties:

``````checkAll = do
QC.quickCheck (prop_sorted :: [Int] -> Bool)
QC.quickCheck (prop_idempotent :: [Int] -> Bool)
QC.quickCheck (prop_ordered :: QC.OrderedList Int -> Bool)
``````

The type constraints on all the properties are necessary, because that is what makes overloading works, so that `quickCheck` can generate random test-cases. Alternatively we can give our properties a less general non-polymorphic type. However, by keeping the more general type for our properties we can check them for other types as well. For instance, we might want to check it for a custom type, like the following type `Colour`:

``````data Colour = Red | Green | Blue
deriving (Eq, Show, Ord)
``````

Before we can use QuickCheck with the `Colour` type, we need to specify how to generate random values of this type. That is, make it an instance of the `Arbitrary` type class:

``````instance QC.Arbitrary Colour where
arbitrary = QC.elements [Red, Green, Blue]
``````

Now, we can check the `prop_sorted` property by adding a simple type constraint:

``````QC.quickCheck (prop_sorted :: [Colour] -> Bool)
``````

### Checking the performance

Once we have convinced our-self the code could be correct, we can start worrying about performance. Thus, we turn to Criterion. When doing performance testing there are all sorts of gnarly details that can go wrong and ruin our experiments: we forget to force the lazy evaluation and thus measure the wrong thing, the running time of function we try to measure is to short to get a meaningful reading of with clock resolution on the computer we use, the garbage collector might introduce noise from one sampling into another, we might be using the computer for something while we run the experiments which could introduce noise, and so on.

In the following I use `C` as the qualified name for values from the Criterion library.

Criterion takes care of all these concerns, and just present us with a simple interface where the only thing we need to specify is which functions we want to run, on what data, and how much we want the result to be evaluated. Thus, to benchmark `kquicksort` on the list `[20, 10, 30]` and get a fully evaluated result, we first use the `nf` (for normal form) function from Criterion to get something `Benchmarkable`:

``````C.nf kquicksort [20, 10, 30]
``````

When we have something benchmarkable, we use the `bench` function to label it and turn it into a `Benchmark`

``````C.bench "kquickcheck on short list" \$ C.nf kquicksort [20, 10, 30]
``````

When we have a list of benchmark we can hand it over to `defaultMain` which makes an excellent `main` body for us that will allow us to configure our benchmark from the command-line without recompiling the program. Without further ado:

``````makeList :: Int -> [Int]
makeList n = QC.unGen (QC.vector n) (R.mkStdGen 42) 25

main :: IO()
main = do
checkAll
let sizes = [ 10000, 20000, 50000, 75000
, 100000, 250000, 500000, 1000000]
let inputs = [(n, makeList n) | n <- sizes]
let benchmarks = [ C.bench (name ++ show n) \$ C.nf sort ns
| (n, ns)      <- inputs,
(name, sort) <- [("quicksort ",  quicksort),
("kquicksort ", kquicksort)]]
C.defaultMain benchmarks
``````

In the helper function `makeList` I have reused the generator framework from QuickCheck for generating some random test data for my benchmark. For simple integer lists as we have here it is a bit overkill, but for more complex input it can be nice.

### The complete program

If you want to find out if `kquicksort` really is faster than `quicksort` is here the complete program.

``````import qualified Criterion.Main as C
import qualified Test.QuickCheck as QC
import qualified Test.QuickCheck.Gen as QC

import Data.List(foldl')
import qualified System.Random as R

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort lesser ++ [p] ++ quicksort greater
where
lesser  = [ x | x <- xs, x < p]
greater = [ x | x <- xs, x >= p]

kquicksort :: Ord a => [a] -> [a]
kquicksort []     = []
kquicksort (p:xs) = kquicksort lesser ++ equal ++ kquicksort greater
where
(lesser,equal,greater) = foldl' part ([],[p],[]) xs
part (l,e,g) x =
case compare x p of
LT -> (x : l, e, g)
GT -> (l, e, x : g)
EQ -> (l, x : e, g)

sorted :: Ord a => [a] -> Bool
sorted (x1:x2:xs) = x1 <= x2 && (sorted \$ x2:xs)
sorted _          = True

prop_sorted :: Ord a => [a] -> Bool
prop_sorted xs = sorted \$ kquicksort xs

prop_idempotent :: Ord a => [a] -> Bool
prop_idempotent xs = kquicksort xs == (kquicksort \$ kquicksort xs)

prop_ordered :: Ord a => QC.OrderedList a -> Bool
prop_ordered (QC.Ordered xs) = xs == kquicksort xs

data Colour = Red | Green | Blue
deriving (Eq, Show, Ord)

instance QC.Arbitrary Colour where
arbitrary = QC.elements [Red, Green, Blue]

checkAll = do
QC.quickCheck (prop_sorted :: [Int] -> Bool)
QC.quickCheck (prop_sorted :: [Colour] -> Bool)
QC.quickCheck (prop_idempotent :: [Int] -> Bool)
QC.quickCheck (prop_ordered :: QC.OrderedList Int -> Bool)

makeList :: Int -> [Int]
makeList n = QC.unGen (QC.vector n) (R.mkStdGen 42) 25

main :: IO()
main = do
checkAll
let sizes = [ 10000, 20000, 50000, 75000
, 100000, 250000, 500000, 1000000]
let inputs = [(n, makeList n) | n <- sizes]
let benchmarks = [ C.bench (name ++ show n) \$ C.nf sort ns
| (n, ns)      <- inputs,
(name, sort) <- [("quicksort ",  quicksort),
("kquicksort ", kquicksort)]]
C.defaultMain benchmarks
``````

Compile it with the command-line

``````\$ ghc -O3 -W --make Quicksort.hs -o Quicksort
``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.