## Archive for May, 2012

## Google Maps without any labels/country names

I wanted to get a blank version of Google Maps without any of the country names on for a visualisation I’m working on but I’d been led to believe that this wasn’t actually possible.

In actual fact we do have control over whether the labels are shown via the ‘styles’ option which we can call on the map.

In my case the code looks like this:

var map = new google.maps.Map(document.getElementById("map_canvas"), { zoom: 3, center: new google.maps.LatLng(31.492121, 14.919434), mapTypeId: google.maps.MapTypeId.ROADMAP }); var emptyStyles = [ { featureType: "all", elementType: "labels", stylers: [ { visibility: "off" } ] } ]; map.setOptions({styles: emptyStyles}); |

And this is the result:

## Haskell: Using type classes to generify Project Euler #31

As I mentioned in my previous post I’ve been working on Project Euler #31 and initially wasn’t sure how to write the algorithm.

I came across a post on StackOverflow which explained it in more detail but unfortunately the example used US coins rather than UK ones like in the Project Euler problem.

To start with I created two versions of the function – one for US coins and one for UK coins:

combinations :: Int -> [USCoin] -> [USCoin] -> [[USCoin]] combinations 0 current _ = [current] combinations _ current [] = [] combinations total p (c:cs) = concatMap (\ times -> combinations (total - (times * fromEnum c)) (p ++ replicate times c) cs) [0,1..(total `div` fromEnum c)] |

combinationsUK :: Int -> [UKCoin] -> [UKCoin] -> [[UKCoin]] combinationsUK 0 current _ = [current] combinationsUK _ current [] = [] combinationsUK total p (c:cs) = concatMap (\ times -> combinationsUK (total - (times * fromEnum c)) (p ++ replicate times c) cs) [0,1..(total `div` fromEnum c)] |

As we can see the only difference between the two functions is the type being passed around and they are almost identical as well:

data USCoin = Quarter | Dime | Nickel | Penny deriving (Eq, Show) |

instance Enum USCoin where fromEnum = fromJust . flip lookup usTable toEnum = fromJust . flip lookup (map swap usTable) usTable = [(Quarter, 25), (Dime, 10), (Nickel, 5), (Penny, 1)] |

data UKCoin = OnePence | TwoPence | FivePence | TenPence | TwentyPence | FiftyPence | OnePound | TwoPounds deriving (Eq, Show) |

instance Enum UKCoin where fromEnum = fromJust . flip lookup ukTable toEnum = fromJust . flip lookup (map swap ukTable) ukTable = [(OnePence, 1), (TwoPence, 2), (FivePence, 5), (TenPence, 10), (TwentyPence, 20), (FiftyPence, 50), (OnePound, 100), (TwoPounds, 200)] |

We can run those two functions like this:

> length $ combinations 200 [] (reverse $ map fst usTable) 1463 > length $ combinationsUK 200 [] (reverse $ map fst ukTable) 73682 |

After spending a lot of the past week reading about type classes I figured we could probably make use of one here so I created a ‘Coin’ type class:

class Coin a where value :: a -> Int |

And then implemented that with ‘USCoin’ and ‘UKCoin':

instance Coin USCoin where value coin = fromEnum coin instance Coin UKCoin where value coin = fromEnum coin |

Then we need to make some small adjustments to ‘combinations’ to make it work with ‘Coin’ instead:

combinations :: (Coin a) => Int -> [a] -> [a] -> [[a]] combinations 0 current _ = [current] combinations _ current [] = [] combinations total p (c:cs) = concatMap (\ times -> combinations (total - (times * value c)) (p ++ replicate times c) cs) [0,1..(total `div` value c)] |

Instead of calling ‘fromEnum’ we call ‘value’ and the function can now be used with any types which implement the Coin type class should we wish to do that.

We can actually go even further and get rid of our Enum type class instances and just put that code onto the Coin type class:

class Eq a => Coin a where table :: [(a, Int)] value :: a -> Int value = fromJust . flip lookup table |

instance Coin USCoin where table = [(Quarter, 25), (Dime, 10), (Nickel, 5), (Penny, 1)] instance Coin UKCoin where table = [(OnePence, 1), (TwoPence, 2), (FivePence, 5), (TenPence, 10), (TwentyPence, 20), (FiftyPence, 50), (OnePound, 100), (TwoPounds, 200)] |

We can then call the function with either of those coins:

> length $ combinations 200 [] (reverse $ map fst (table :: [(USCoin, Int)])) 1463 > length $ combinations 200 [] (reverse $ map fst (table :: [(UKCoin, Int)])) 73682 |

## Haskell: Java Style Enums

I’ve been playing around with problem 31 of Project Euler which is defined as follows:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1 £1 + 150p + 220p + 15p + 12p + 31p

How many different ways can £2 be made using any number of coins?

Having coded way too much in Java my first thought was that the coins could be represented as an Enum but I wasn’t sure how to do that in Haskell.

As it turns out the question has been asked on Stack Overflow and there’s an Enum type class we can implement to achieve the same thing.

In this case:

data UKCoin = OnePence | TwoPence | FivePence | TenPence | TwentyPence | FiftyPence | OnePound | TwoPounds deriving (Eq, Show) |

instance Enum UKCoin where fromEnum = fromJust . flip lookup table toEnum = fromJust . flip lookup (map swap table) table = [(OnePence, 1), (TwoPence, 2), (FivePence, 5), (TenPence, 10), (TwentyPence, 20), (FiftyPence, 50), (OnePound, 100), (TwoPounds, 200)] |

If we want to get the monetary value of a coin we use ‘fromEnum':

> fromEnum TwoPounds 200 |

And if we wanted to go back to the enum value we’d do this:

> (toEnum 200) :: UKCoin TwoPounds |

If we want to get a list of all the instances of ‘UKCoin’ we can just do a map over ‘table':

> let ukCoins = map fst table > ukCoins [OnePence,TwoPence,FivePence,TenPence,TwentyPence,FiftyPence,OnePound,TwoPounds] |

## Haskell: Finding the minimum & maximum values of a Foldable in one pass

I recently came across Dan Piponi’s blog post ‘Haskell Monoids & their Uses‘ and towards the end of the post he suggests creating monoids to work out the maximum and minimum values of a Foldable value in one pass.

The Foldable type class provides a generic approach to walking through a datastructure, accumulating values as we go.

The foldMap function applies a function to each element of our structure and then accumulates the return values of each of these applications.

A list is one example of a type which implements the Foldable type class like so:

instance Foldable [] where foldr = Prelude.foldr foldl = Prelude.foldl foldl' = List.foldl' foldr1 = Prelude.foldr1 foldl1 = Prelude.foldl1 |

In this case it delegates all of the Foldable functions to previously defined functions from the Prelude or List modules.

The ‘foldMap’ function mentioned above has the following default implementation:

foldMap :: Monoid m => (a -> m) -> t a -> m foldMap f = foldr (mappend . f) mempty |

Dan shows an example where we use ‘foldMap’ to check whether any values in a Foldable have the value 1 by using the ‘Any’ monoid:

> foldMap (Any . (== 1)) [1..20] Any {getAny = True} |

I couldn’t quite understand how it worked so I expanded the ‘foldMap’ definition which results in the following:

> Data.Foldable.foldr (\x acc -> acc `mappend` (Any . (== 1)) x) mempty [1..20] Any {getAny = True} |

So we’re folding over the list with an initial seed value of ‘Any False’ as that’s what mempty will evaluate to. For each value we’re then calling ‘mappend’ with two ‘Any’ values and passing on the result.

So in this example it would go like this:

Any False `mappend` (Any . (==1)) 20 => Any False `mappend` Any False => Any False Any False `mappend` (Any . (==1)) 19 => Any False `mappend` Any False => Any False ... Any False `mappend` (Any . (==1)) 1 => Any False `mappend` Any True => Any True |

In our case we need to define our own monoids to keep track of the maximum value in a Foldable:

import Data.Monoid import Data.Foldable data MaxSoFar a = MaxSoFar { getMaxSoFar :: a } deriving (Eq, Ord, Read, Show, Bounded) instance (Num a, Ord a, Bounded a) => Monoid (MaxSoFar a) where mempty = MaxSoFar (minBound) MaxSoFar x `mappend` MaxSoFar y = MaxSoFar (max x y) |

We set ‘mempty’ to the minimum possible Int value so that anything Int value compared to it will automatically become the max value when it gets compared to that.

For ‘mappend’ we take the values stored in the two ‘MaxSoFar’ instances and then select the maximum and return a new MaxSoFar.

We call foldMap like so:

> foldMap (MaxSoFar) ([1..20] :: [Int]) MaxSoFar {getMaxSoFar = 20} |

MinSoFar is pretty similar in design:

data MinSoFar a = MinSoFar { getMinSoFar :: a } deriving (Eq, Ord, Read, Show, Bounded) instance (Num a, Ord a, Bounded a) => Monoid (MinSoFar a) where mempty = MinSoFar maxBound MinSoFar x `mappend` MinSoFar y = MinSoFar (min x y) |

And we can then combine them together like this:

> foldMap (\x -> (MaxSoFar x, MinSoFar x)) ([1..20] :: [Int]) (MaxSoFar {getMaxSoFar = 20},MinSoFar {getMinSoFar = 1}) |

This works because we can make use of what Dan calls the ‘Product Monoid’, which is a Monoid instance for a tuple:

instance (Monoid a, Monoid b) => Monoid (a,b) where mempty = (mempty, mempty) (a1,b1) `mappend` (a2,b2) = (a1 `mappend` a2, b1 `mappend` b2) |

So in our example the fold would go like this:

(MaxSoFar -9223372036854775808, MinSoFar 9223372036854775807) `mappend` (MaxSoFar 20, MinSoFar 20) => (MaxSoFar 20, MinSoFar 20) (MaxSoFar 20, MinSoFar 20) `mappend` (MaxSoFar 19, MinSoFar 19) => (MaxSoFar 20, MinSoFar 19) ... (MaxSoFar 20, MinSoFar 2) `mappend` (MaxSoFar 1, MinSoFar 1) => (MaxSoFar 20, MinSoFar 1) |

We could probably achieve the same thing without using monoids but I think this approach is pretty neat.

## Haskell: Debugging code

In my continued attempts to learn QuickCheck, one thing I’ve been doing is comparing the results of my brute force and divide & conquer versions of the closest pairs algorithm.

I started with this property:

let prop_dc_bf xs = (length xs > 2) ==> (fromJust $ bfClosest xs) == dcClosest xs |

And then ran it from GHCI, which resulted in the following error:

> quickCheck (prop_dc_bf :: [(Double, Double)] -> Property) *** Failed! Falsifiable (after 8 tests and 19 shrinks): [(-165.0,8.0),(5.0,47.0),(6.0,0.0),(8.0,0.0),(2.0,1.0),(-129.0,17.0),(-15.0,11.0)] |

I wasn’t really sure where to start to work out what had gone wrong but I eventually came across Debug.Trace which has the ‘trace‘ function which I found quite useful.

trace :: String -> a -> aSource

The trace function outputs the trace message given as its first argument, before returning the second argument as its result.

For example, this returns the value of f x but first outputs the message.

trace (“calling f with x = ” ++ show x) (f x)

The initial divide and conquer algorithm read like this:

dcClosest :: (Ord a, Floating a) => [Point a] -> Pair a dcClosest pairs | length pairs <= 3 = fromJust $ bfClosest pairs | otherwise = foldl (\closest (p1:p2:_) -> minimumBy (compare `on` distance') [closest, Pair p1 p2]) closestPair (windowed 2 pairsWithinMinimumDelta) where sortedByX = sortBy compare pairs (leftByX:rightByX:_) = chunk (length sortedByX `div` 2) sortedByX closestPair = minimumBy (compare `on` distance') [closestLeftPair, closestRightPair] where closestLeftPair = dcClosest leftByX closestRightPair = dcClosest rightByX pairsWithinMinimumDelta = sortBy (compare `on` snd) $ filter withinMinimumDelta sortedByX where withinMinimumDelta (x, _) = abs (xMidPoint - x) <= distance' closestPair where (xMidPoint, _) = last leftByX |

So I put a ‘trace’ before the ‘foldl’ function to see what was being passed to it:

dcClosest :: (Ord a, Floating a) => [Point a] -> Pair a dcClosest pairs | length pairs <= 3 = fromJust $ bfClosest pairs | otherwise = trace ("passed in the following: " ++ show (windowed 2 pairsWithinMinimumDelta)) foldl (\closest (p1:p2:_) -> minimumBy (compare `on` distance') [closest, Pair p1 p2]) closestPair (windowed 2 pairsWithinMinimumDelta) ... |

> dcClosest [(-165.0,8.0),(5.0,47.0),(6.0,0.0),(8.0,0.0),(2.0,1.0),(-129.0,17.0),(-15.0,11.0)] passed in the following: [] (2.0,1.0) (6.0,0.0) |

The function still works the same way but it prints out the trace message as well.

Having run this a few times I realised that I’d made a mistake with the values that I’d passed to ‘foldl’ – I was supposed to pass the combination of all the pairs in ‘pairsWithinMinimumDelta’ but had actually only passed in adjacent ones.

The following change needs to be made to fix that:

dcClosest :: (Ord a, Floating a) => [Point a] -> Pair a dcClosest pairs | length pairs <= 3 = fromJust $ bfClosest pairs | otherwise = foldl (\closest (p1, p2) -> minimumBy (compare `on` distance') [closest, Pair p1 p2]) closestPair (combos pairsWithinMinimumDelta) where sortedByX = sortBy compare pairs (leftByX:rightByX:_) = chunk (length sortedByX `div` 2) sortedByX closestPair = minimumBy (compare `on` distance') [closestLeftPair, closestRightPair] where closestLeftPair = dcClosest leftByX closestRightPair = dcClosest rightByX pairsWithinMinimumDelta = sortBy (compare `on` snd) $ filter withinMinimumDelta sortedByX where withinMinimumDelta (x, _) = abs (xMidPoint - x) <= distance' closestPair where (xMidPoint, _) = last leftByX combos :: [a] -> [(a,a)] combos initial = [(initial !! i, initial !! j) | i <- [0..length initial - 1], j <- [i+1..length initial-1 ], i /= j] |

It’s still not perfect because we end up doing too many comparisons in the ‘foldl’ part of the code.

It does now, however, give the same results as the brute force version.

> quickCheck (prop_dc_bf :: [(Double, Double)] -> Property) +++ OK, passed 100 tests. |

## Haskell: Using monoids when sorting by multiple parameters

On the project I’ve been working on we had a requirement to sort a collection of rows by 4 different criteria such that if two items matched for the first criteria we should consider the second criteria and so on.

If we wrote that code in Haskell it would read a bit like this:

data Row = Row { shortListed :: Bool, cost :: Float, distance1 :: Int, distance2 :: Int } deriving (Show, Eq) |

import Data.Ord import Data.List compareRow :: Row -> Row -> Ordering compareRow x y = if comparing (not . shortListed) x y == EQ then if comparing cost x y == EQ then if comparing distance1 x y == EQ then comparing distance2 x y else comparing distance1 x y else comparing cost x y else comparing (not . shortListed) x y |

We can then sort a list of rows like this:

> let shortListedRow = Row {shortListed = True, cost = 10.0, distance1 = 20, distance2 = 30 } > let nonShortListedRow = Row {shortListed = False, cost = 10.0, distance1 = 20, distance2 = 30 } > sortBy compareRow [nonShortListedRow, shortListedRow] [Row {shortListed = True, cost = 10.0, distance1 = 20, distance2 = 30}, Row {shortListed = False, cost = 10.0, distance1 = 20, distance2 = 30}] |

It works but it’s messy and we couldn’t see what abstraction we should be using to simplify the code.

I was continuing with my reading of Functors, Applicative Functors and Monoids yesterday and got to the section on Monoids which showed an example for simplifying this type of code.

The definition of a Monoid from the Haskell source code is:

Types with an associative binary operation that has an identity

But I prefer Dan Piponi’s definition:

In Haskell, a monoid is a type with a rule for how two elements of that type can be combined to make another element of the same type.

To be a monoid there also needs to be an element that you can think of as representing ‘nothing’ in the sense that when it’s combined with other elements it leaves the other element unchanged.

In our case we have a bunch of things of type ‘Ordering’ and we want to combine them all together and end up with a final ‘Ordering’ which takes them all into account.

For example if we were comparing the following two rows:

> let row1 = Row {shortListed = True, cost = 10.0, distance1 = 1, distance2 = 30 } > let row2 = Row {shortListed = True, cost = 10.0, distance1 = 100, distance2 = 30 } > compareRow row1 row2 LT |

When we compare their shortListed value we get back ‘EQ’, so we compare their cost value and get back ‘EQ’ and finally we compare their distance1 value which gives back ‘LT’ which is our final value.

We can make use of the Ordering Monoid to do this rather than all the nested if statements.

Monoid is a type class defined like so:

class Monoid a where mempty :: a mappend :: a -> a -> a mconcat :: [a] -> a mconcat = foldr mappend mempty |

‘mempty’ represents the identity value for a monoid i.e. the ‘nothing’ in Dan Piponi’s definition. If we combine anything with this then we should get that thing back.

The most interesting function here is ‘mappend’ which we use to combine together two elements of a type. Each instance of Monoid needs to define this function for themselves.

The Ordering Monoid is defined like so:

instance Monoid Ordering where mempty = EQ LT `mappend` _ = LT EQ `mappend` y = y GT `mappend` _ = GT |

What makes this work for us is that we always keep the value on the left unless it’s ‘EQ’ in which case we take the value on the right.

Therefore as soon as one of our comparisons returns a non ‘EQ’ value that will be the value that eventually gets returned.

e.g.

> GT `mappend` LT `mappend` EQ GT |

Our ‘row1’/’row2′ comparison would look like this using ‘mappend':

> EQ `mappend` EQ `mappend` LT LT |

We can then change our ‘compareRow’ function:

compareRow x y = comparing (not . shortListed) x y `mappend` comparing cost x y `mappend` comparing distance1 x y `mappend` comparing distance2 x y |

We can simplify this further by making use of ‘mconcat’ which folds over a list of monoids applying ‘mappend’ each time.

For example we could replace our ‘row1’/’row2′ comparison with the following:

> mconcat [EQ, EQ, LT] LT |

And ‘compareRow’ now reads like this:

compareRow x y = mconcat [comparing (not . shortListed) x y, comparing cost x y, comparing distance1 x y, comparing distance2 x y] |

We’re still repeating the ‘comparing’ bit of code every time so I extracted that into a function:

by :: Ord a => (b -> a) -> b -> b -> Ordering by fn x y = comparing fn x y |

We then need to apply those functions to x and y to get our collection of monoids we can pass to mconcat:

compareRow x y = mconcat $ map (\fn -> fn x y) [by (not . shortListed), by cost, by distance1, by distance2] |

~~One problem with this code is that we’re now comparing by all the parameters when we can actually stop once we’ve found a non equality.~~

~~I’m sure there’s a clever way to short circuit this but I’m not sure what it is at the moment!~~

As BeRewt points out in the comments what I wrote here is not actually the case, it is lazily evaluated!

## Scala/Haskell: A simple example of type classes

I never really understood type classes when I was working with Scala but I recently came across a video where Dan Rosen explains them pretty well.

Since the last time I worked in Scala I’ve been playing around with Haskell where type classes are much more common – for example if we want to compare two values we need to make sure that their type extends the ‘Eq’ type class.

Learn Me a Haskell’s chapter on type classes defines them like so:

Typeclasses are like interfaces.

A typeclass defines some behaviour (like comparing for equality, comparing for ordering, enumeration) and then types that can behave in that way are made instances of that typeclass.

The behaviour of typeclasses is achieved by defining functions or just type declarations that we then implement. So when we say that a type is an instance of a typeclass, we mean that we can use the functions that the typeclass defines with that type.

In that chapter we then go on to create a ‘YesNo’ type class which defines Boolean semantics for all different types.

We start by defining the type class like so:

class YesNo a where yesno :: a -> Bool |

Any type which extends that type class can call this ‘yesno’ function and find out the truthyness of its value.

e.g.

instance YesNo Int where yesno 0 = False yesno _ = True |

If we call that:

> yesno (0 :: Int) False > yesno (1 :: Int) True |

We get the expected result, but if we try to call it for a type which hasn’t defined an instance of ‘YesNo':

> yesno "mark" No instance for (YesNo [Char]) arising from a use of `yesno' Possible fix: add an instance declaration for (YesNo [Char]) In the expression: yesno "mark" In an equation for `it': it = yesno "mark" |

In Scala we can use traits and implicits to achieve the same effect. First we define the ‘YesNo’ trait:

trait YesNo[A] { def yesno(value:A) : Boolean } |

Then we define an implicit value in a companion object which creates an instance of the ‘YesNo’ type class for Ints:

object YesNo { implicit val intYesNo = new YesNo[Int] { def yesno(value:Int) = value match { case 0 => false; case _ => true } } } |

We then need to call our ‘yesno’ function and the idea is that if we’ve defined a type class instance for the type we call it with it will return us a boolean value and if not then we’ll get a compilation error.

object YesNoWriter { def write[A](value:A)(implicit conv: YesNo[A]) : Boolean = { conv.yesno(value) } } |

If we call that:

> YesNoWriter.write(1) res1: Boolean = true > YesNoWriter.write(0) res2: Boolean = false |

It works as expected, but if we try to call it with a type which wasn’t defined for the ‘YesNo’ type class we run into trouble:

> YesNoWriter.write("mark") :10: error: could not find implicit value for parameter conv: YesNo[java.lang.String] YesNoWriter.write("mark") |

We can also define YesNoWriter like this by making use of context bounds:

object YesNoWriter { def write[A:YesNo](value:A) : Boolean = { implicitly[YesNo[A]].yesno(value) } } |

I think this pattern is preferred when we might just be tunnelling the implicit parameter through to another method but we can still use it here and use the ‘implicitly’ method to get access to the implicit value.

I’m still not entirely sure about the use of implicits but in this case they provide another way to implement polymorphism without having to use inheritance.

Dan Rosen goes into much more detail about type classes and implicits and I wrote about how we were using them on a project I worked on last year in an earlier blog post if you want to learn more.

## Haskell: My first attempt with QuickCheck and HUnit

As I mentioned in a blog post a few days I’ve started learning QuickCheck with the test-framework package as suggested by David Turner.

I first needed to install test-framework and some dependencies using cabal:

> cabal install test-framework > cabal install test-framework-quickcheck > cabal install test-framework-hunit |

I thought it’d be interesting to try and write some tests around the windowed function that I wrote a few months ago:

Windowed.hs

module Windowed (windowed) where windowed :: Int -> [a] -> [[a]] windowed size [] = [] windowed size ls@(x:xs) = if length ls >= size then (take size ls) : windowed size xs else windowed size x |

I wrote my first property like so:

import Windowed import Test.Framework (defaultMain, testGroup) import Test.Framework.Providers.QuickCheck (testProperty) import Test.QuickCheck main = defaultMain tests tests = [ testGroup "windowed" [ testProperty "should not window if n is bigger than list size" prop_nothing_if_n_too_large ] ] prop_nothing_if_n_too_large n xs = n > length xs ==> windowed n xs == [] |

And tried to compile the file:

ghc -package test-framework -package test-framework-quickcheck -threaded WindowedQC.hs -o Windowed |

Which resulted in this compilation error:

WindowedQC.hs:16:17: No instance for (QuickCheck-1.2.0.1:Test.QuickCheck.Testable (Gen Prop)) arising from a use of `testProperty' Possible fix: add an instance declaration for (QuickCheck-1.2.0.1:Test.QuickCheck.Testable (Gen Prop)) |

According to the test-framework home page this error happens when we have more than one version of QuickCheck installed so we need to tell ‘ghc’ which one to use:

ghc -package test-framework -package test-framework-quickcheck -package QuickCheck-1.2.0.1 -threaded WindowedQC.hs -o Windowed |

That solved the first compilation problem but I still had another:

WindowedQC.hs:16:17: Ambiguous type variable `a0' in the constraints: (Arbitrary a0) arising from a use of `testProperty' at WindowedQC.hs:12:17-28 (Show a0) arising from a use of `testProperty' at WindowedQC.hs:12:17-28 (Eq a0) arising from a use of `prop_nothing_if_n_too_large' at WindowedQC.hs:12:80-106 Probable fix: add a type signature that fixes these type variable(s) |

The way to solve this problem is to explicitly state which types will be passed to the property like so:

prop_nothing_if_n_too_large n xs = n > length xs ==> windowed n xs == [] where types = (xs :: [Int], n :: Int) |

I eventually ended up with the following:

WindowedQC.hs

import Windowed import Test.Framework (defaultMain, testGroup) import Test.Framework.Providers.QuickCheck (testProperty) import Test.QuickCheck import Test.Framework.Providers.HUnit import Test.HUnit main = defaultMain tests tests = [ testGroup "windowed" [ testProperty "should not window if n is bigger than list size" prop_nothing_if_n_too_large, testProperty "should create sub arrays the size of window" prop_size_of_sub_arrays_is_n, testProperty "should group adjacent items into windows" prop_groups_adjacent_items, testCase "should window a simple list" test_should_window_simple_list ] ] prop_groups_adjacent_items n xs = n < length xs ==> not (null xs) ==> n > 0 ==> (last $ last $ windowed n xs) == last xs where types = (xs :: [Int], n :: Int) prop_nothing_if_n_too_large n xs = n > length xs ==> windowed n xs == [] where types = (xs :: [Int], n :: Int) prop_size_of_sub_arrays_is_n n xs = n > 0 ==> all (\subArray -> length subArray == n) (windowed n xs) where types = (xs :: [Int], n :: Int) test_should_window_simple_list = windowed 2 [1..10] @?= [[1,2], [2,3], [3,4], [4,5], [5,6], [6,7], [7,8], [8,9], [9,10]] |

I initially only wrote QuickCheck properties but I wasn’t satisfied that just passing the properties I’ve written would guarantee the function is working as expected.

The first property does a simple check that the last item from the windowed function is the same as the last item in the list assuming that the list isn’t empty, that we’re using a positive n value and our window size is smaller than the list size.

The second checks that we end up with an empty list if we try to window to a size bigger than the list and the third checks that each of the sub arrays is the correct size.

I wasn’t sure how to write a QuickCheck property that would test the values of the individual sub arrays so I ended up writing a HUnit test instead.

If you know how I could achieve the same thing using QuickCheck please let me know.

We can then run all the tests like so:

> ./Windowed windowed: should not window if n is bigger than list size: [OK, passed 100 tests] should create sub arrays the size of window: [OK, passed 100 tests] should group adjacent items into windows: [OK, passed 100 tests] should window a simple list: [OK] Properties Test Cases Total Passed 3 1 4 Failed 0 0 0 |

## Building an API: Test Harness UI

On the project I’ve been working on we’re building an API to be used by other applications in the organisation but when we started none of those applications were ready to integrate with us and therefore drive the API design.

Initially we tried driving the API through integration style tests but we realised that taking this approach made it quite difficult for us to imagine how an application would use it.

It also meant that we didn’t have a good way to show our business stakeholders the work we’d done – showing off pieces of JSON going back and forth probably wouldn’t have gone down too well!

We therefore decided to create our own test harness UI which we would use to show case what we’d developed so far and also use to help drive the design of the API.

Obviously it would be better if we were able to drive the API out from a real application but given that wasn’t possible the test harness approach seems to work reasonably well.

The main problem that we ran into was not knowing how much effort we should be putting into the test harness UI given that its primary purpose was to show the progress being made on the UI.

We started out not writing many tests or paying much attention to how it looked since it was assumed to be a throwaway UI.

Over time it’s become more complicated and since we use it to display progress to management stakeholders we’ve spent time making it more presentable.

Despite that I’d still say the effort we’ve put in is worthwhile because it gives us a way to show progress to non technical people.

From my experience if you can’t do that they’ll start to get nervous and wonder if you know what you’re doing which isn’t a good place to be!

## Haskell: Writing a custom equality operator

In the comments on my post about generating random numbers to test a function David Turner suggested that this was exactly the use case for which QuickCheck was intended for so I’ve been learning a bit more about that this week.

I started with a simple property to check that the brute force (bf) and divide and conquer (dc) versions of the algorithm returned the same result, assuming that there were enough values in the list to have a closest pair:

prop_closest_pairs xs = length xs >= 2 ==> dcClosest xs == (fromJust $ bfClosest xs) |

I could then run that as follows:

> import QuickCheck.Test > quickCheck(prop_closest_pairs :: [(Double, Double)] -> Property) |

It failed pretty quickly because the bf and dc versions of the algorithm sometimes return the pairs in a different order.

e.g. bf may say the closest pair is (2.0, 0.0), (2.1, 1.1) while dc says it’s (2.1, 1.1), (2.0, 0.0) which will lead to the quick check property failing because those values aren’t equal:

> ((2.0, 0.0), (2.1, 1.1)) == ((2.1, 1.1), (2.0, 0.0)) False |

The best way I could think of to get around this problem was to create a type to represent a pair of points and then write a custom equality operator.

I initially ended up with the following:

type Point a = (a, a) data Pair a = P (Point a) (Point a) |

instance Eq (Pair a) where P a b == P c d = a == c && b == d || a == d && b == c |

Which didn’t actually compile:

qc_test.hs:41:58: No instance for (Eq a) arising from a use of `==' In the second argument of `(&&)', namely `b == c' In the second argument of `(||)', namely `a == d && b == c' In the expression: a == c && b == d || a == d && b == c |

The problem is that while we’ve made Pair an instance of the Equality type class there’s no guarantee that the value contained inside it is an instance of the Equality type class which means we might not be able to compare its values.

We need to add a class constraint to make sure that the value inside P is a part of Eq:

instance (Eq a) => Eq (Pair a) where P a b == P c d = a == c && b == d || a == d && b == c |

Now we’re saying that we want to make Pair an instance of the Equality type class but only when the value that Pair contains is already an instance of the Equality type class.

In this case we’re just storing pairs of doubles inside the Pair so it will work fine.

Now if we compare the two points from above we’ll see that they’re equal:

> P (2.0, 0.0) (2.1, 1.1) == P (2.1, 1.1) (2.0, 0.0) True |

I had to go and change the existing code to make use of this new but it didn’t take more than 5-10 minutes to do that.