Mark Needham

Thoughts on Software Development

Archive for May, 2012

Google Maps without any labels/country names

with one comment

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:

Map no labels

Written by Mark Needham

May 31st, 2012 at 9:52 pm

Posted in Software Development

Tagged with

Haskell: Using type classes to generify Project Euler #31

with 2 comments

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

Written by Mark Needham

May 30th, 2012 at 12:08 pm

Posted in Haskell

Tagged with

Haskell: Java Style Enums

with 2 comments

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]

Written by Mark Needham

May 30th, 2012 at 11:10 am

Posted in Haskell

Tagged with

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

without comments

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.

Written by Mark Needham

May 28th, 2012 at 11:18 am

Posted in Haskell

Tagged with

Haskell: Debugging code

without comments

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.

Written by Mark Needham

May 27th, 2012 at 10:16 pm

Posted in Haskell

Tagged with

Haskell: Using monoids when sorting by multiple parameters

with 7 comments

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!

Written by Mark Needham

May 23rd, 2012 at 6:44 am

Posted in Haskell

Tagged with

Scala/Haskell: A simple example of type classes

without comments

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.

Written by Mark Needham

May 22nd, 2012 at 10:26 am

Posted in Haskell,Scala

Tagged with ,

Haskell: My first attempt with QuickCheck and HUnit

without comments

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

Written by Mark Needham

May 20th, 2012 at 7:09 pm

Posted in Haskell

Tagged with

Building an API: Test Harness UI

with 2 comments

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!

Written by Mark Needham

May 19th, 2012 at 8:03 pm

Haskell: Writing a custom equality operator

with 4 comments

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.

Written by Mark Needham

May 16th, 2012 at 1:16 pm

Posted in Haskell

Tagged with