# 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
```

##### About the author

Mark Needham is a Developer Relations Engineer for Neo4j, the world's leading graph database.