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\u2019m especially found of:<\/p>\n
QuickCheck<\/a> for a quick testing of the correctness of my code, by letting me specify the properties<\/em> I want to check, and taking care of generating random test-cases.<\/p>\n<\/li>\n Criterion<\/a> for checking the time performance of my code in a statistical sound manner. Taking care of dealing with the garbage collector and such like.<\/p>\n<\/li>\n<\/ul>\n In this post I give a quick tour of how to use these libraries.<\/p>\n Our first step is to install QuickCheck and Criterion:<\/p>\n Now we are ready to go.<\/p>\n The standard list-based implementation of quicksort that you so often see, seems ripe for some optimisations:<\/p>\n One obvious optimisation could be to only traverse The basic usage of QuickCheck is to specify the properties you care about as ordinary Haskell functions, and then you use the The first property we want to check is that The next properties that we want to check could be that For Now we can use the The type constraints on all the properties are necessary, because that is what makes overloading works, so that Before we can use QuickCheck with the Now, we can check the 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.<\/p>\n In the following I use 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 When we have something benchmarkable, we use the When we have a list of benchmark we can hand it over to In the helper function If you want to find out if Compile it with the command-line<\/p>\n 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\u2019m especially found of: QuickCheck for a quick testing of the correctness of my code, […]<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,17],"tags":[],"class_list":["post-101","post","type-post","status-publish","format-standard","hentry","category-coding","category-haskell"],"_links":{"self":[{"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/posts\/101","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/comments?post=101"}],"version-history":[{"count":10,"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/posts\/101\/revisions"}],"predecessor-version":[{"id":110,"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/posts\/101\/revisions\/110"}],"wp:attachment":[{"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/media?parent=101"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/categories?post=101"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/ken.friislarsen.net\/blog\/wp-json\/wp\/v2\/tags?post=101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}Getting the libraries<\/h3>\n
$ cabal install criterion quickcheck\r\n<\/code><\/pre>\nBackstory<\/h3>\n
quicksort :: Ord a => [a] -> [a]\r\nquicksort [] = []\r\nquicksort (p:xs) = quicksort lesser ++ [p] ++ quicksort greater\r\n where\r\n lesser = [ x | x <- xs, x < p]\r\n greater = [ x | x <- xs, x >= p]\r\n<\/code><\/pre>\nxs<\/code> once, when partitioning the elements into lesser and greater (and equal) than p<\/code>. Here is one implementation that uses foldl'<\/code> for maximum performance (we hope):<\/p>\nkquicksort :: Ord a => [a] -> [a]\r\nkquicksort [] = []\r\nkquicksort (p:xs) = kquicksort lesser ++ equal ++ kquicksort greater\r\n where\r\n (lesser,equal,greater) = foldl' part ([],[p],[]) xs\r\n part (l,e,g) x =\r\n case compare x p of\r\n LT -> (x : l, e, g)\r\n GT -> (l, e, x : g)\r\n EQ -> (l, x : e, g)\r\n<\/code><\/pre>\nChecking some properties<\/h3>\n
quickCheck<\/code> function to check the properties. In the following I use QC<\/code> as the qualified name for values from the QuickCheck library.<\/p>\nkquicksort<\/code> returns a sorted result. To check this property we also define a helper predicate sorted<\/code> that checks that a list is sorted:<\/p>\nsorted :: Ord a => [a] -> Bool\r\nsorted (x1:x2:xs) = x1 <= x2 && (sorted $ x2:xs) \r\nsorted _ = True\r\n\r\nprop_sorted :: Ord a => [a] -> Bool\r\nprop_sorted xs = sorted $ kquicksort xs\r\n<\/code><\/pre>\nkquicksort<\/code> is idempotent and if it is given an ordered argument it doesn\u2019t mess it up:<\/p>\nprop_idempotent :: Ord a => [a] -> Bool\r\nprop_idempotent xs = kquicksort xs == (kquicksort $ kquicksort xs)\r\n\r\nprop_ordered :: Ord a => QC.OrderedList a -> Bool\r\nprop_ordered (QC.Ordered xs) = xs == kquicksort xs\r\n<\/code><\/pre>\nprop_ordered<\/code> we use the type class OrderedList<\/code> to specify that this property should only hold for arguments that are sorted.<\/p>\nquickCheck<\/code> function to check all our properties:<\/p>\ncheckAll = do\r\n QC.quickCheck (prop_sorted :: [Int] -> Bool)\r\n QC.quickCheck (prop_idempotent :: [Int] -> Bool)\r\n QC.quickCheck (prop_ordered :: QC.OrderedList Int -> Bool)\r\n<\/code><\/pre>\nquickCheck<\/code> 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<\/code>:<\/p>\ndata Colour = Red | Green | Blue\r\n deriving (Eq, Show, Ord)\r\n<\/code><\/pre>\nColour<\/code> type, we need to specify how to generate random values of this type. That is, make it an instance of the Arbitrary<\/code> type class:<\/p>\ninstance QC.Arbitrary Colour where\r\n arbitrary = QC.elements [Red, Green, Blue]\r\n<\/code><\/pre>\nprop_sorted<\/code> property by adding a simple type constraint:<\/p>\nQC.quickCheck (prop_sorted :: [Colour] -> Bool)\r\n<\/code><\/pre>\nChecking the performance<\/h3>\n
C<\/code> as the qualified name for values from the Criterion library.<\/p>\nkquicksort<\/code> on the list [20, 10, 30]<\/code> and get a fully evaluated result, we first use the nf<\/code> (for normal form) function from Criterion to get something Benchmarkable<\/code>:<\/p>\nC.nf kquicksort [20, 10, 30]\r\n<\/code><\/pre>\nbench<\/code> function to label it and turn it into a Benchmark<\/code><\/p>\nC.bench "kquickcheck on short list" $ C.nf kquicksort [20, 10, 30]\r\n<\/code><\/pre>\ndefaultMain<\/code> which makes an excellent main<\/code> body for us that will allow us to configure our benchmark from the command-line without recompiling the program. Without further ado:<\/p>\nmakeList :: Int -> [Int]\r\nmakeList n = QC.unGen (QC.vector n) (R.mkStdGen 42) 25\r\n\r\nmain :: IO()\r\nmain = do\r\n checkAll\r\n let sizes = [ 10000, 20000, 50000, 75000\r\n , 100000, 250000, 500000, 1000000]\r\n let inputs = [(n, makeList n) | n <- sizes]\r\n let benchmarks = [ C.bench (name ++ show n) $ C.nf sort ns \r\n | (n, ns) <- inputs,\r\n (name, sort) <- [("quicksort ", quicksort),\r\n ("kquicksort ", kquicksort)]]\r\n C.defaultMain benchmarks\r\n<\/code><\/pre>\nmakeList<\/code> 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.<\/p>\nThe complete program<\/h3>\n
kquicksort<\/code> really is faster than quicksort<\/code> is here the complete program.<\/p>\nimport qualified Criterion.Main as C\r\nimport qualified Test.QuickCheck as QC\r\nimport qualified Test.QuickCheck.Gen as QC\r\n\r\nimport Data.List(foldl')\r\nimport qualified System.Random as R\r\n\r\nquicksort :: Ord a => [a] -> [a]\r\nquicksort [] = []\r\nquicksort (p:xs) = quicksort lesser ++ [p] ++ quicksort greater\r\n where\r\n lesser = [ x | x <- xs, x < p]\r\n greater = [ x | x <- xs, x >= p]\r\n\r\nkquicksort :: Ord a => [a] -> [a]\r\nkquicksort [] = []\r\nkquicksort (p:xs) = kquicksort lesser ++ equal ++ kquicksort greater\r\n where\r\n (lesser,equal,greater) = foldl' part ([],[p],[]) xs\r\n part (l,e,g) x =\r\n case compare x p of\r\n LT -> (x : l, e, g)\r\n GT -> (l, e, x : g)\r\n EQ -> (l, x : e, g)\r\n\r\nsorted :: Ord a => [a] -> Bool\r\nsorted (x1:x2:xs) = x1 <= x2 && (sorted $ x2:xs) \r\nsorted _ = True\r\n\r\nprop_sorted :: Ord a => [a] -> Bool\r\nprop_sorted xs = sorted $ kquicksort xs\r\n\r\nprop_idempotent :: Ord a => [a] -> Bool\r\nprop_idempotent xs = kquicksort xs == (kquicksort $ kquicksort xs)\r\n\r\nprop_ordered :: Ord a => QC.OrderedList a -> Bool\r\nprop_ordered (QC.Ordered xs) = xs == kquicksort xs\r\n\r\ndata Colour = Red | Green | Blue\r\n deriving (Eq, Show, Ord)\r\n\r\ninstance QC.Arbitrary Colour where\r\n arbitrary = QC.elements [Red, Green, Blue]\r\n\r\ncheckAll = do\r\n QC.quickCheck (prop_sorted :: [Int] -> Bool)\r\n QC.quickCheck (prop_sorted :: [Colour] -> Bool)\r\n QC.quickCheck (prop_idempotent :: [Int] -> Bool)\r\n QC.quickCheck (prop_ordered :: QC.OrderedList Int -> Bool)\r\n\r\nmakeList :: Int -> [Int]\r\nmakeList n = QC.unGen (QC.vector n) (R.mkStdGen 42) 25\r\n\r\nmain :: IO()\r\nmain = do\r\n checkAll\r\n let sizes = [ 10000, 20000, 50000, 75000\r\n , 100000, 250000, 500000, 1000000]\r\n let inputs = [(n, makeList n) | n <- sizes]\r\n let benchmarks = [ C.bench (name ++ show n) $ C.nf sort ns \r\n | (n, ns) <- inputs,\r\n (name, sort) <- [("quicksort ", quicksort),\r\n ("kquicksort ", kquicksort)]]\r\n C.defaultMain benchmarks\r\n<\/code><\/pre>\n$ ghc -O3 -W --make Quicksort.hs -o Quicksort\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"