# coin-change kata

given a list of coins $$[c_1,..,c_n]$$ and a amount of money $$A$$ we shall find a list $$[a_1,..,a_n]$$ of integers such that $$\sum_i a_i c_i = A$$ – but not just any: We want to minimize the number of coins given: $$minimize \sum_i a_i$$

See here for more on this problem.

I stumpled on this reading twitter, where Mike Bild solved this using various LINQ-like expressions (well the first version of what I give you here) … as I could not stand the not-optimal solution I had to brute-force a better solution (… and maybe I come back and try to improve on that some time)

### remark (shameless plug)

You can find the same article on school of haskell – where you can even play with it. But make sure to give me some nice comments here :D

## a trivial algorithm (that does give you correct change but not with fewest coins)

First define the coins used (as a Integer-list):

coins :: [Integer]
coins = [100, 25, 10, 5, 1]



Then the idea is to fold over the coins using the remaining amount we have to change and the count of used coins so far (so a 3 at position 2 will mean 2 – 25ct coins used)

change :: Integer -> [Integer]
change n = reverse . snd $foldl next (n, []) coins where next (remaining, cs) coin | coin <= remaining = (r', cnt:cs) | otherwise = (remaining, 0:cs) where r' = remaining mod coin cnt = remaining div coin  ## Why this might fail in the general case Well sometimes … let’s change the coins and look for 30cts … change :: Integer -> [Integer] change n = reverse . snd$ foldl next (n, []) coins
where next (remaining, cs) coin
| coin <= remaining = (r', cnt:cs)
| otherwise         = (remaining, 0:cs)
where r' = remaining mod coin
cnt = remaining div coin



so 6 coins (1x25ct and 5*1ct) – WTF … well the algorithm is too stupid in this case (the answer is of course 2x15ct) … stay tuned – I gonna fix it … soon

## brute-forcing our way

An easy way to fix this is to try every possible combination for small cases like the samples it’s still ok

import Data.List(minimumBy)
import Data.Maybe(mapMaybe)
import Control.Applicative ( (<$>) ) findChange :: [Coin] -> Cents -> Maybe [Integer] findChange coins amount = snd <$> calc amount coins
where calc r []
| r == 0    = Just (0, [])
| otherwise = Nothing
calc r (c:cs)
| r < 0     = Nothing
| otherwise = findMinimum . mapMaybe try $[0 .. r div c] where try n = do (n', ns) <- calc (r-n*c) cs return (n + n', n:ns) findMinimum [] = Nothing findMinimum vs = Just . minimumBy (\ (a,_) (b, _) -> compare a b)$ vs



As you can see, the code has changed a bit – but produces the right answer (2x15ct)!

Instead of trying to find the right fold-function I went for manual recursion for now: You will find the algorithm inside of calc. The first few guards handle the edge-cases (nothing more to change, no-coins left to try, to much change given). But in the case that there is still something to give-back and where there are coins left to change with the algorithm tries every combination and finaly turns back the one with fewest coins given recursivley.

## brute-force brakes down

Remember: I told you “it’s still ok”? Well I lied – try the brute-force algorithm for your normal coins [100, 50, 25, 10, 5, 2, 1] and (say) 2$34ct … this will take the algorithm on my machine almost 10seconds! Try the same for 100$ and get yourself some coffee…

## What can we do…

If you look carefully you’ll see that we do the recursive-call not one time but two times – and just as with fibonacci numbers we will sureley hit the same spot more than once – but every time we calculate the thing again. Just write the algorithm down as a tree and you will see that we recalculate the same branches time-and-time again…

So how can we change this?

We have to memoize the caluclated values! This is more or less the basic idea in dynamic programming (DP) – and while I will not give a complete introduction here I will try to show how you can change the algorithm to use this.

## First step towards DP

The first thing we are going to do is modify the algorithm a bit so that we can see better where the recursion is (the case expression below):

-- | tries change (using coins form the first parameter) to the amount of money in the second parameter with the fewest number of pieces in the change
-- | the first parameter should be a decreasing list of distinct values
takeCoin :: [Coin] -> Cents -> Maybe (Integer, [Coin])
takeCoin [] cents
| cents == 0   = Just (0, [])
| otherwise    = Nothing
takeCoin coins@(coin:coins') cents
| cents < 0    = Nothing
| coin > cents = takeCoin coins' cents
| otherwise    = case (takeCoin coins (cents-coin), takeCoin coins' cents) of
(Just (n, t), Just (n',t')) -> Just $if n+1 <= n' then (n+1, coin:t) else (n', t') (Nothing, Just (n',t')) -> Just (n', t') (Just (n,t), Nothing) -> Just (n+1, coin:t)  This will still take long (indeed it will do slightly worse) but you can see better where the magic (aka recursion) is and where the edge-cases gets handled. ## enter lazy-arrays Now how to memoize … well the easiest thing I can think of (and indeed almost the same as with real DP) is to use an array. Well now you cannot mutate arrays in Haskell but as Haskell is lazy this will be no problem! How so? Well we just put lots of chunks into the array and let the algorithm lazily evalute those at needed. BTW: this is the point where this algorithm can break down: the chunks need quite some memory and if your DP-table is large this will exhaust your memory (look for the knapsackproblem with large data-sets …) but again (this time for sure): for this it will be sufficient (for me)! So here it is – the final (quite quick) DP-solution to the problem import Data.Array takeCoinDP :: [Coin] -> Cents -> Maybe (Integer, [Coin]) takeCoinDP coins cents = get ltCoin cents where arr = array ((0,0), (ltCoin, cents)) [((i,c), takeC i c) | i <- [0..ltCoin], c <- [0..cents]] get i c | i < 0 && c == 0 = Just (0, []) | i < 0 || c < 0 = Nothing | otherwise = arr!(i,c) ltCoin = length coins - 1 takeC cNr cts | coin > cts = get (cNr-1) cts | otherwise = case (get cNr (cts-coin), get (cNr-1) cts) of (Just (n, t), Just (n',t')) -> Just$ if n+1 <= n' then (n+1, coin:t) else (n', t')
(Nothing,     Just (n',t')) -> Just (n', t')
(Just (n,t),  Nothing)      -> Just (n+1, coin:t)
(Nothing,     Nothing)      -> Nothing
where coin = coins !! cNr

main :: IO ()
main = do
putStrLn "let's change 2$34ct" let coins = defaultCoins let amount = 234 putStrLn "here we go ... this should be alot quicker..." let res = takeCoinDP coins amount print res  I hope you see the similarity to the version above. The only trick here is to move the edge cases to the selection from the array (to avoid index-out-of-range exceptions and stuff). Enjoy! # Installing GLPK and GLPK-hs on Windows As I want to try some LP (looking into a coursera-course) I tried to setup GLPK on Windows. (BTW: doing this in Linux is trivial: apt-get or you friendly packet-manager). The goal was to get this simple skript: import Control.Monad.LPMonad import Data.LinearProgram import Data.LinearProgram.GLPK objFun :: LinFunc String Int objFun = linCombination [(10, "x1"), (6, "x2"), (4, "x3")] lp :: LP String Int lp = execLPM$ do
setDirection Max
setObjective objFun
leqTo (varSum ["x1", "x2", "x3"]) 100
leqTo (linCombination [(10, "x1"), (4, "x2"), (5, "x3")]) 600
leqTo (linCombination [(2, "x1"), (2, "x2"), (6, "x3")]) 300
varGeq "x1" 0
varBds "x2" 0 50
varGeq "x3" 0
setVarKind "x1" IntVar
setVarKind "x2" ContVar

main = print =<< glpSolveVars mipDefaults lp



running.

Well here are the steps that got me going:

• in the /w32 folder edit the Build_GLPK_with_VC10.bat file to update your installation folder for VS2010 (mine was under Programm files (x86))
• run the batch-file and make sure you are in the right environment (I put it into programm files so I had to run the developers console from VS2010 tools as administrator!)
• copy the build version of glpk dll and lib without it’s version (for example copy glpk_4_52.dll glpk.dll)
• use cabal install with extra-libs and extra-sources like this:
cabal install glpk-hs --extra-lib-dirs="c:\Program Files (x86)\GNU\glpk\w32" --extra-include-dirs="c:\Program Files (x86)\GNU\glpk\src" 
• now runhaskell example.hs should run and result in $$x_1 = 40$$, $$x_2 = 50$$ and $$x_3 = 0$$.

I’ve seen syntax like:

let !s = f x


from time to time (for example in Marlows Book) but I never reall knew what this really is, nor where I should look for it.

Today I stumpled upon the Bang patterns extension to GHC – and voila – here we go.

## So what is it?

If we add the extension we can force evalutation wo WHNF (weak head normal form – more or less evaluated “one step”) by just adding a !(Bang) in front of an identifier – and this extents to pattern-matching as well (this and the fact that is’s shorter to write and better to read makes it so much better then seq).

Here are a few examples showing a bit of it’s power/capabilities:

let makeTuple() = (1+1, 2+2)
let f = makeTuple()
:sprint f
>> f = _

let !f = makeTuple()
:sprint f
>>f = (_,_)



I wanted to try out some of Haskells web-frameworks for quite some time now. The problem so far was always the huge pile of things those come bundeled with (template haskell, conduit, comonads, etc.) and I somehow wanted to understand all this first.

To make this short: NO I do not understand all this but I think I will never really be ready to try it if I wait for me to turn genius overnight (guess will never happen) – so I just hold my breath and jump right into it!

# but say … which one?

That leaves me with the choice of the framework. After looking a bit at the online tutorials I wanted to go for either snap or yesod. But on first glance (well …) snap seemed to be a bit easier to get startet. Having said that I think I will try yesod too someday soon.

# Installation Odyssee

## First try: Windows

I work mainly on Windows and so of course I tried to get this working in windows. I even can remember that I tried to install snap some time ago and it seemed to work … but … Well after

 cabal-dev install snap
I soon (well it took quite some time to compile all this) got the dreaded “failed to install because of …” message …

About an hour (with yet another complete reinstall of Haskell-Plattform and various test with different versions) later I finally contacted the snap guys on their IRC channel and after describing the problems the final verdict was like this:

we have no Windows developer on our team … this is about the help you can expect

To be honest: the guy was quite helpful and it seems that the problem is in some crypto-package and not with snap but I’m quite disappointed anyway.

Anyhow: forget Windows for now …

## Ubuntu to the rescue….

Luckily I have quite a nice Ubuntu-VM installed on my machine (where I can just do a simple snapshot-restore to reset my cabal-hell) and so I went there next. Here the installation was quite simple (that is

cabal-dev install snap
) worked just fine.

### TIP OF THE DAY

I did not really want to do this installation for each project I am going to try but on Linux (have to try this on Windows as well) you can add a symbolic link to the created cabal-dev folder in each new project you are going to make (do not forget to place a symbolic link to the snap executable in cabal-dev/bin somewhere your PATH is pointing – or add this folder to your path. This works quite nice for me and I do not soil my global or user cabal repository.

# first toy project

For my first project I want to implement a basic calculator on a webpage. Finally it should work with AJAX/jQuery or even do all it’s calculation in the browser using Fay.

## First Iteration – getting something up

I worked through the two basic tutorials on the snap homepage: hello world and snaplets tutorial but two be honest – the second one just produced “WTF”s on my side – so I decided to keep it dumb for now and just get snap to serve me static HTML files together with a simple CSS stylesheet and of course a jQuery-plugin I am going to use (yeah … it’s JavaScript … for now).

You can find the project on github but so far it’s only a very basic extension of the first example above.

### some details on the code

To get snap to serve me the stylesheets and possible scripts I had to extend the routes in the site-function:

site :: Snap ()
site =
ifTop (serveDirectory "./content/") <|>
route [ ("api/sum/:operants", sumHandler)
] <|>
dir "scripts" (serveDirectory "./scripts/") <|>
dir "styles" (serveDirectory "./styles/")



This basically says that everything requested in with only the root-path is served (with some so called default-configuration) via serveDirectory straight from the content-folder (the default configuration sees that index.html is served … btw: Index.html will get you a 404)

The next part will serve for AJAX-requests – it binds a handler sumHandler to a URL like this http://mySite/api/sum/2%202 (see below).

The rest are static routes: /scripts/xyz tries to find the file xyz in the ./scripts folder and similar for styles (this is where I put the javascript files and the stylesheets).

The handler for the very simple API is implemented like this:

sumHandler :: Snap ()
sumHandler = do
param <- getParam "operants"
maybe (writeJSON errorMsg)
(writeJSON . sumString . unpack) param
where errorMsg :: ByteString
errorMsg = pack "please give some operants"

sumString :: String -> Integer
sumString = sumUp . words
where sumUp :: [String] -> Integer
sumUp = sum . map read



It gets the string xyz in http://mySite/api/sum/xyz, splits it by spaces (words) and sums the integers (no there is no exception handling yet) up. It finally serves the answer as JSON (for this I use the snap-extras package).

I’m sure there is an easier way to do all this but this is what I was able to find in a reasonable time using my google-ninja-skills.

## next Iteration: getting a basic web-page and AJAX queries to work …

well … but next time

I am sure some/most of you know better then me, so pls let me know what and how I can improve. For example: is this the right way to get to some kind of RESTful API (using handlers like this) or is there some special snap-way I just have not found yet?

# my OpenPGP/GnuPG public Key

You can use this to send me secure mails and fuck the NSA :D

ASC file with my key

 -----BEGIN PGP PUBLIC KEY BLOCK----- Version: GnuPG v2.0.20 (MingW32)

 mQENBFH7YaABCAClwtwRGmTMAnD+cvtRnfmj9ZhqaX6ahh61r0kKxj/ow9nVJJTE jkI2tlVNhh01bV+HvDSvX3Cuy2cuPDJ2QpeoRCPhtMTsECae0cHrdDFtu9zPQ9v4 yswQA/JPH4zl/H5hQo/KXjbMzybmrvKq8oW5PBKYTF5jRRdoAmqawkENo1Douj0P HG2pcQj6lZwMPUsHwykwdsYbVXEfUYQr3pnU0ZFjB3cS74hD4NmEpXMYUTzGexR+ cuW1rBLwl8I2RPiIcH0ztUPqoCDMeaRS0PVyPJ7D1z2yp5kK1vmH7zrlSe5nFZS/ RGChbSISZiVD1CJZXf1U3+bZHzY0iN77cyefABEBAAG0K0NhcnN0ZW4gS8O2bmln IDxDYXJzdGVuQktvZW5pZ0B0LW9ubGluZS5kZT6JATkEEwECACMFAlH7Y24CGw8H CwkIBwMCAQYVCAIJCgsEFgIDAQIeAQIXgAAKCRDmjt5r1nNDxRWTB/0e4O9e2QE8 2JPa0debyttCyrH5Bzy4IUm5DM1X2/fOWmdfQEAenGjcwJcbu/fp4AoPkI3B9RFk bzoG64eCuQk7p9OMjPW8R+EE0e1/WcrxJZsngJ/IZ0v43+mDRP/ZwT0v+dnJyLuA ClhvxL0meyeWLI9J2PFC8MrIOAbcZ+63jM90N1/mS19wM6W6BFe8PTBXTqz5J5Md hUo/4L2qQUAxcyLaidK0Zlg8LzDDiu/qz2jjhNRkpBXLITe56Bq7tmmpka+EPQ/C 1ynXLGvfEe3ojd5qC59o+tXiyVgHgzExe7IREXh5tV58Z4i+YhfaovzZMUbPnwwS 4sZi0ckUA7T8tCpDYXJzdGVuIEvDtm5pZyA8Q2Fyc3RlbkBnZXR0aW5nc2hhcnBl ci5kZT6JATkEEwECACMFAlH7YaACGw8HCwkIBwMCAQYVCAIJCgsEFgIDAQIeAQIX gAAKCRDmjt5r1nNDxf74B/4yxLabM1bnLCp/Zx/NyslLGXzr5gZBTOZ2vYUNjEvz b6vb36P1EoA8zBygEdX9CX63e1G50bR4qwljlRfHwlEIHmXRiqeUb2feNVjLriCP ThqVD1Tw47gTFTcmE/Pe/+V/1G+znMtLzaoHAnpc4GFM4dzs5KFLG7o6GAyt4b8e rPKhlbzTUt2h8Sl5PtWtHjVmSM2EFOfWOoQW4OfpADD2Pfgik8QaWS/bn1GaBkMC 2vcbIE+USIXc88Wto1w5P74DGREM7EZnC462noqqihA62UbWpXA5n1N2tI1D3ULI rscDqaC9j3gqljv9DDEMo/VF4shagJE2j5NwN41IbtMJtC9DYXJzdGVuIEvDtm5p ZyA8Q2Fyc3Rlbi5Lb2VuaWdAd2llZ2FuZC1nbGFzLmRlPokBOQQTAQIAIwUCUftj hgIbDwcLCQgHAwIBBhUIAgkKCwQWAgMBAh4BAheAAAoJEOaO3mvWc0PFfdEH/2Ef wfrqH/pDrpiWqwW+n7NQ1dUVa6Lfb5r0Cce+gBOWzshH67OgGxmp5yPFa+vlG+Gi EnOL0JUVlM1gywbDw34+CXlopFA32lDyPXGCDg4zA5ZHqv6nO92NJrRCPikRp5O0 cUPFmHJs6S+jpGwCaGQ72dIpi8RaKKW9NKTQ2sx68ObLlpfrLosjh/R6rpnzPC8o mHeqaMlMMAcFcOCb2KK9gOUDvuB9Nl+gLSGQtAQsCwWFTHCscj6qmCB/pZGMrQu0 k2FYxscZntNhhjmrf68iylB021RxTb49EMiYXozL8s0C+Etr9/Mw2K+HP+seLcsQ CT2X2qPxj5oxi9FaMuA= =mg2D -----END PGP PUBLIC KEY BLOCK----- 

# Easy in OOP–harder in FP: a list of animals

WARNING: what I describe here seems to be an antipattern

So better only use it with what is said in the Haskell-Wiki and mind the good comments bellow – Thank you Stephen and Jacob

Sometimes things you take for granted in your common OOP language (says C#) seems to be hard or impossible in Haskell at first glance.

This is no big deal – indeed the problem is so simple I thought for a moment I must have lost my mind over night as I could find no easy way to solve this in Haskell at first – and indeed the solution is quite simple but it involves a language extension I had not seen before (yeah – I’m still in my Haskell-noob-years – ask me again another decade or so ) but maybe this article can help some fellow beginner.

In this post I’m going to describe a possibility to access a list of animals (data) of different types that share some common traits like the number of limbs.

To see what I want look at the following short C# code:

interface IAnimal
{
int NumberOfLimbs { get; }
}

class Dog : IAnimal
{
public string Name { get; set; }
public string Color { get; set; }

public int NumberOfLimbs
{
get { return 4; }
}
}

class Spider : IAnimal
{
public int NumberOfLimbs
{
get { return 8; }
}
}

static class Animals
{
public static void DescribeAnimals()
{
var animals = new IAnimal[] {new Dog {Name = "Mozart"}, new Spider()};
foreach(var animal in animals)
Console.WriteLine("This one has {0} limbs", animal.NumberOfLimbs);
}
}



The purpose of this is just to get a array/list of animals – you don’t even have to use a interface – a base class would serve the same purpose.

Easy right?

How hard can this be in Haskell?

I came upon this problem while trying to write a simple ray-tracer where a scene consists of a collection of renderable objects. Of course this is easy if you go and use an algebraic data-type for this. But I wanted the raytracer to be open (you want to provide some object other then spheres and polygons – go on: add them) – but of course ADTs are closed – so no luck there.

Of course the next thing you are thinking of are data and type-classes and indeed you can solve the problem in this way but it’s not as easy as it might seem.

Let’s get back to the example above – an open way to implement the NumberOfLimbs property could look like this:

module Animals where

class IBody a where
nrLimbs :: a -> Int

newtype Dog = Dog String
instance IBody Dog where
nrLimbs (Dog _) = 4

newtype Spider = Spider ()
instance IBody Spider where
nrLimbs (Spider ()) = 8



But how can we get a list of things with different data-types (Dog and Spider) ? – Well we don’t – a list is a homogenous data-structure and IBody is not a data-type but a type-constructor so we have to say what ‘a’ is.

So we have to get a data-type that somehow can a instance of the IBody class without having to say what the data-type really is. Well you cannot do this in vanilla Haskell but we are not out of luck: there is an language-extension named “ExistentialQuantification” that can help us here: it gives you a “forall” quantifier just like in math that allows you to remove a concrete data type from your data-definition.

You can read a much better explanation than I could give here (HaskellWiki: Existential ypes) but here is what this can look like in our simple example:

data Animal = forall a. (IBody a) => Animal a

describeAnimals :: [Animal] -> [String]
describeAnimals []     = []
describeAnimals (a:as) = describe a : describeAnimals as
where describe (Animal a) = "This one has " ++ (show \$ nrLimbs a) ++ " limbs"



As you can see I added an Animal data-type whose constructor can wrap every IBody-Instance, but you don’t have to constraint it to any concrete type a because it’s “forall” those.

Of course now the compiler cannot know anything other of such an Animal besides that it’s of instance IBody – but that is exactly what we want.

The describeAnimals function finally takes advantage of this and can handle list of Animals, and you could use it like this:

> let animals = [Animal (Dog "Mozart"), Animal (Spider ())]
> describeAnimals animals
["This one has 4 limbs","This one has 8 limbs"]



Of course this is not the hole story and I encourage you to read the very good wiki article I linked above.

you know Hoogle – don’t you?

In case you don’t Hoogle is a search-engine where you can look for Haskell functions. You can use with it’s web-interface and there are a couple of plugins (for GHCi, etc.)

The great thing is: not only can you search by name or Module – you can even search by type!

Well why would that be useful?

I just forgot the name for the function that gives you the Unicode-Index for a character – but of course the type of this function should be $$Char –> Int$$

So enter “Char –> Int” into Hoogle and voila: the second found function is the one I forgot!

This one is so good I want something similar for .net … but wait, with the weak type-system and cluttered side-effects that might be not so useful after all (search for “XYZ –> ()”? … stupid thing I want this Update-Db thingy not the Draw-to-Screen … stupid OOP )