# get and compile the latest monodevelop on Ubuntu/Linux

I assume you installed mono (I got mono-complete) and git already.
This should be easy using apt-get, synaptic or the software-store.

This is just my write-down of the things I had to do while following
the documentation on github,
as there where some things you might miss (indeed this was triggered

# Clone it

First let’s get the source-files and it’s submodules:

git clone https://github.com/mono/monodevelop.git
cd monodevelop
git submodule update --init --recursive


This might take some while so get tea ;)

# Configure

I decided to use the stable version and put it into the default location (/usr/lib/monodevelop).
So just configure it this way:

./configure --profile=stable


Well this got me the following error:

configure: error: Cannot enable GNOME platform without gnome-sharp-2.0


Which is no big deal – just grap the packet using apt-get:

sudo apt-get install gnome-sharp2


and retry

./configure --profile=stable


this now works on my test-VM if you have any other issues repeat till you got all dependencies installed.

Hint
If you don’t know the package-names (for example the error was “gnome-sharp-2.0″ but the package
is named “gnome-sharp2″ use synaptic to search for it (or your favorite search-engine on the net).

# Build

Now just compile/build it:

make


This to fails on the first go for me, and the error is harder to spot – but looking at the output
I did find this:

WARNING: Error getting response stream (Write: The authentication or decryption has failed.)


The real problem is that nuget could not download some packages (nuget is .nets packet manager –
or will be till Paket rules but that is another story).

Anyway it could not get the packages because some Mozilla LXR certificates where missing.
You can get them by running this command:

mozroots --import --sync


Well let’s try again:

make


Of course this too will take some time…

# Install it

This is optional, but as I don’t want to keep the sources and want to use this in production I’m gonna install
monodevelop into the system by:

sudo make install


THAT’S IT

# Clean up (optional)

I don’t need the sources any longer (but you can keep them if you want to update regulary) so:

cd ..
rm monodevelop -rf


Will remove them.

# Church numerals, .net and working around the value restriction

I find it kindof fun to play with lambda calculus from time to time. Recently I had another go at the church numerals and the goal of my little kata was get a nice type-representation for them:

Have something lie
zero :: Number
– a successor function succ :: Number -> Number
– and the most trivial operators: add :: Number -> Number -> Number and mult :: Number -> Number -> Number

It’s not too hard to do this in Haskell, if you allow me to use existential types:

{-# LANGUAGE RankNTypes #-}

module ChurchNumerals where

import Prelude hiding (succ)

newtype Number = Nr (forall a. (a -> a) -> a -> a)

eval :: Number -> Integer
eval (Nr a) = a (+1) 0

zero :: Number
zero = Nr (\ _ z -> z)

succ :: Number -> Number
succ (Nr a) = Nr (\ s z -> s (a s z))

add :: Number -> Number -> Number
add (Nr a) = a succ

mult :: Number -> Number -> Number
mult (Nr a) b = a (add b) zero

one :: Number
one = succ zero

two :: Number
two = succ one


# Using .net / Fsharp

Well for algebraic data-types there is are no existentials in F# but maybe we don’t really need it (??):

module Numbers =

type Number<'a> = Nr of (('a->'a) -> 'a -> 'a)

let zero = Nr (fun _ z -> z)
let succ (Nr n) = Nr (fun s z -> s (n s z))

let eval (Nr f) = f ((+) 1) 0
let show (Nr f) =
f ((+) "1+") "0"
|> printf "%s"

let add (Nr f : _ Number) (b : _ Number) =
f succ b

let mult (Nr f : _ Number) (b : _ Number) =


So it might look just like a minor annoyance (to move the generic-parameter around) and on first glance it seems to work:

    let multiplyStuff =
let one = succ zero
let two = succ one
let three = succ two
let res = mult two three
eval res
// return 6


But just the innocent looking addition of a sideeffekt that does not alter the behviour:

    let multiplyStuff =
let one = succ zero
let two = succ one
let three = succ two
let res = mult two three
show res // print the structure
eval res


bust the compiler:

Type mismatch. Expecting a
Number<int>
but given a
Number<string>
The type 'int' does not match the type 'string'


And the even more innocent looking definition of just the 1-literal:

let one = succ zero


gives us a value restricition error:

Value restriction. The value 'one' has been
inferred to have generic type
val one : Number<'_a>
Either define 'one' as a simple data term,
make it a function with explicit arguments or,
if you do not intend for it to be generic,


## What is going on

In the first example I cheated – I wraped it into a local binding so that the compiler could infer concrete types for one, two, three and res – indeed the eval res
forces res to be of type Number<int> and mult (which indeed is Number<Number<'a>> -> Number<Number<'a>> -> Number<'a>) forces the others to be Number<Number<'int>>.

The second example now of course cannot compile as res suddenly needs to be both Number<int> and Number<string> (from show : Number<string> -> unit).

The third example finaly just tells you that the compiler simply does not know what the 'a in one : Number<'a> is supposed to be (You cannot have a generic value in .net).

# Interfaces to the rescue

While we cannot have generic functions in data-types/records in .net/F# we can have generic methods on interfaces.
And indeed we get a reasonable nice solution to our problem using an interface INumber that just contains the same application Nr had in the above example:

module Churchs =
type INumber =
abstract apply : ('a -> 'a) -> 'a -> 'a

let eval (n : INumber) =
n.apply ((+) 1) 0

let show (n : INumber) =
n.apply ((+) "1+") "0"
|> printf "%s"

let zero =
{ new INumber with
member __.apply(_: 'a -> 'a) (z: 'a): 'a =  z
}

let succ (n : INumber) =
{ new INumber with
member __.apply(s: 'a -> 'a) (z: 'a): 'a =  s (n.apply s z)
}

let one : INumber = succ zero
let two : INumber = succ one
let three : INumber = succ two

let add (a : INumber) (b : INumber) : INumber =
a.apply succ b

let mult (a : INumber) (b : INumber) : INumber =


Yes the definition of zero and succ is a bit more verbose but the rest of the code stays the same and the types now finally are as simple as we wanted them (or as Haskell got them).

Indeed this is another reason why interfaces are often more usefull than records of functions in F# and should not be considered to be an antipattern – even if you have some Haskell background ;)

# what is a functor

## Quick intro to categories

Category theory is a topic from pure math but don’t fear – the basic stuff is not that hard to grasp.
And the domain (Types in programming languagues or Haskell in this case) should be well known to us
developers.

### Basic definition

A category $$\mathcal{C}$$ consists of two collections (or classes) of stuff: Objects $$Obj_{\mathcal{C}}$$ and Arrows $$Hom_{\mathcal{C}}$$.
For a first intuition it might be benefical to just think of objects as just mathematical sets
and arrows as just mathematical mappings (functions).

To make it a bit easier to read we will use upper-case letters like $$A$$, $$B$$ and $$C$$ for objects and lower-case letters like $$f$$, $$g$$ and $$h$$ for arrows.

You know it’s math so those classes will come with a few extra stuff and their elements have to fullfill some laws (I will stop to write the category in there for now – it’s always the same):

• Every Arrow $$f$$ is given a domain $$dom(f) \in Obj$$ and codomain $$codom(f) \in Obj$$ and we write a short-form of this as $$f: A \rightarrow B$$ if $$f$$s domain is $$A$$ and its codomain is $$B$$. Often the collection of all arrows from domain $$A$$ to codomain $$B$$ is written as $$\mathcal{C}(A,B)$$.
• There is an operation $$\circ$$ you we can use to compose two arrows: if we have $$f: A \rightarrow B$$ and $$g: B \rightarrow C$$ we get another arrow $$g \circ f: A \rightarrow C$$.
• There is a special arrow $$id_A: A \rightarrow A$$ for each object $$A$$. And yes – this will be just what you think it is.
• Here are the laws: for all arrows you have $$f \circ (g \circ h) = (f \circ g) \circ h$$ and $$f \circ id = id \circ f = f$$ (and yeah you have to choose the right domains/codomains and even the $$id$$ functions used there will be two different ones for this to work out – you can try this as an exercise or just read on and do it as an exercise in Haskell)

Chances are good, that this all looks very familiar to you. Indeed not only do arrows look like functions between set, the collection of all sets and the functions between them form a category $$\mathcal{Set}$$.

Now we want to transfer this into Haskell-World: We can get a category (usually called $$\mathcal{hask}$$), where the objects are the haskell-types (Int, [Char], Maybe Float, Int -> Int, whatever) and the arrows are just your usual haskell functions.

Easy isn’t it? It’s just new names for your stuff ;)

## What is a functor

Now we climb the ebony-tower one more level: we look at the structure-preserving-maps between categories – and yes those we will call functors.

So what exactly does structure-preserving mean here?

Well for a functor $$\mathcal{F}$$ between two categories $$\mathcal{C}$$ and $$\mathcal{D}$$ we need two mappings: one that maps objects in $$\mathcal{C}$$ to objects in $$\mathcal{D}$$ and one that will map their arrows so that domains, and codomains match.
We will be lazy here and just use the same symbol $$\mathcal{F}$$ for both of them.
So we have $$\mathcal{F}: Obj_{\mathcal{C}} \rightarrow Obj_{\mathcal{D}}$$ and
$$\mathcal{F}: Hom_{\mathcal{C}} \rightarrow Hom_{\mathcal{D}}$$
Structur-preserving now just means that everything has to fit:

Imagine you have an arrow in $$\mathcal{C}$$: $$f: A \rightarrow B$$. For $$F(f)$$ we demand that
$$F(f): F(A) \rightarrow F(B)$$
that is the functor maps the domain and codomain just right.

Of course the composition needs to be compatible as well – meaning
$$\mathcal{F}(f \circ_{\mathcal{C}} g) = \mathcal{F}(f) \circ_{\mathcal{D}} \mathcal{F}(g)$$
(Note that there are two different compositions involved here).

Well in Haskell we cannot just use the same symbols for different stuff – and indeed this was something
I first struggled with a bit. So I hope to make this clear here.

We already saw that the objects are just types, and now we need something to map types to types.
Type-constructors with kind * -> * do just this.
That would include Maybe, [], … – and yes these are the things we call functors in Haskell.

Remember: there is a type-class called Functor in Haskell defined like this:

class  Functor f  where
fmap        :: (a -> b) -> f a -> f b


(There is another operator, defined with fmap in there that is not important for us here).

If you look carefully you see that fmap seems to be just what we need for our second mapping – the one that takes arrows to arrows (or functions to functions for us).

Maybe you did not see it till now – but we did not really change the categorie we are working in. Those
functors don’t change the category they go from $$\mathcal{hask}$$ to $$\mathcal{hask}$$ – in math these are called endo-functors.

If you have a look at the documentationFunctors in Haskell should obey these laws:

fmap id  ==  id
fmap (f . g)  ==  fmap f . fmap g


Look closely – these are exactly the laws the categorial functors need to obay for $$\mathcal{hask}$$.

Of course your usual instances of Functor all obey these laws – but they are not
checked by the compiler. So you have to be carefull when writing new functors.

As you might know I work in .net/F#/C# in my day-job. It has no type-classes and so there nobody really
talks about functors there – but of course they are there.
F#s Option, most collection types with LINQ and so forth all have what you need for it.
Yes there is no common fmap but you have Option.map and List.map and of course LINQs .Select.
And the mapping between the types is just done through generics.

# markdown plugins … oh my

I just saw that my old markdown-plugin (markdown on save) broke … sadly the new one that should be compatible with it (jetpack markdown) does not really care about my old posts and so you will see lot’s of issues.

Right now I don’t know how exactly I can get everything working with haskell-syntax highlighting again.

Any recommendations are appreciated :(

# Introduction

as I mentioned I want to try some real-life Haskell and of course this means using some kind of database.
I looked around a bit and found the really great Persistent package from Micheal Snoyman.
Not only is this wonderfuly documented – no you get an yesod integration and a online-book(chapter) explaining it for free – thank you Micheal!

This post will only detail the setup and installation I had to do on top of my PostgresSQL installation and it’s more or less my notes I wrote along the way (I hope you enjoy this experiment).

So here we go – with opened SublimeText and console we start…

# Set up the playground

• made a directory and initialized a git repository in it git init
• copied my generic haskell .gitignore into it
• initialized cabal cabal init setting up the basic names and stuff
• added persistent, persistent-sqlite and persistent-postgresql as dependencies
• shamelessly copied the code from here into main.hs:

{-# LANGUAGE EmptyDataDecls    #-}
{-# LANGUAGE FlexibleContexts  #-}
{-# LANGUAGE QuasiQuotes       #-}
{-# LANGUAGE TypeFamilies      #-}
import           Database.Persist
import           Database.Persist.Sqlite
import           Database.Persist.TH</p>

<p>share [mkPersist sqlSettings, mkMigrate &quot;migrateAll&quot;] [persistLowerCase|
Person
name String
age Int Maybe
deriving Show
BlogPost
title String
authorId PersonId
deriving Show
|]</p>

<p>main :: IO ()
main = runSqlite &quot;:memory:&quot; $do runMigration migrateAll</p> <pre><code>johnId &amp;lt;- insert$ Person &amp;quot;John Doe&amp;quot; $Just 35 janeId &amp;lt;- insert$ Person &amp;quot;Jane Doe&amp;quot; Nothing

insert $BlogPost &amp;quot;My fr1st p0st&amp;quot; johnId insert$ BlogPost &amp;quot;One more for good measure&amp;quot; johnId

oneJohnPost &amp;lt;- selectList [BlogPostAuthorId ==. johnId] [LimitTo 1]
liftIO $print (oneJohnPost :: [Entity BlogPost]) john &amp;lt;- get johnId liftIO$ print (john :: Maybe Person)

delete janeId
deleteWhere [BlogPostAuthorId ==. johnId]
</code></pre>

<p>

• obviously wanting a sandbox: cabal sandbox init
• get the stuff from the net and write this here in the meantime ;) cabal install --dependencies-only

# the usual cabal oddysee starts.. (but do not fear – Penelope does not have to wait long)

So this was the first thing that failed – persistent-sqlite went like a charm but persistent-postgresql had a issue.

Ok – comment out the postgres part for now – the code does not need it.

But as cabal build showed I had a missing module Database.Persist.TH – and as I could not find the right package at once, let’s comment it out for now.

Yeah that got me another missing module Control.Monad.IO.Class – but this time ghc (and me) knows where to find it: transformers – so in it.

Now I get some more information – as you could guess the .TH stands for TemplateHaskell and sure enough ghc complains about things like share and mkPersist.

And sure enough there is a persistent-template package with those functions and the missing module – so another cabal install later, we finally have a compiling program.

Yes there are a few warnings (unused constructors and so forth) but let’s forget about this right now.

# let’s run

a cabal run yields

Migrating: CREATE TABLE "person"("id" INTEGER PRIMARY KEY,"name" VARCHAR NOT NULL,"age" INTEGER NULL)
Migrating: CREATE TABLE "blog_post"("id" INTEGER PRIMARY KEY,"title" VARCHAR NOT NULL,"author_id" INTEGER NOT NULL REFERENCES "person")
[Entity {entityKey = Key {unKey = PersistInt64 1}, entityVal = BlogPost {blogPostTitle = "My fr1st p0st", blogPostAuthorId = Key {unKey = PersistInt64 1}}}]
Just (Person {personName = "John Doe", personAge = Just 35})


Which looks like just what the copied code should do … great!

# back to postgres

But of course I want to run this in my local postgresql db – so there’s still one thing left before I could call it a day – so remove let’s get it back in there.

Retrying the install I saw this nice little helper-message:

setup: The program pg_config is required but it could not be found.


And indeed – I did not have this on my system – running openSUSE it’s no big deal to find out where the bugger lives: cnf pg_config – voila postgresql92-devel so give it to me sudo zypper install postgresql92-devel (note: of course you might have to do some sudo apt-get or something similar if you are on a debian based system – but I’m sure you get it – if you are on windows … well let’s say I keep this task for another day and propably ms-sql or mysql instead of postgres).

After this little intermezzo persistent-postgresql builds/installs and we can look at how to use it with our “copy&paste” example.

Turns out that this too is already mentioned in the book chapter I linked earlier – right at the bottom of the doc.
The changes are very slight:

• import Database.Persist.Postgresql instead of .Sqlite
• get a connection string for the database:
    connStr = "host=localhost dbname=test user=??? password=**** port=5432"


<

p>(fill in whatever you need – obviously you should use a known user/password).

• run withPostgresqlPool with runSqlPersistMPool instead of just runSqlite like this:

main = withPostgresqlPool connStr 10 $pool -> do flip runSqlPersistMPool pool$ do


The rest may stay untouched.

And YEAH – cabal run yields

Migrating: CREATe TABLE "person"("id" SERIAL PRIMARY KEY UNIQUE,"name" VARCHAR NOT NULL,"age" INT8 NULL)
HINWEIS:  CREATE TABLE erstellt implizit eine Sequenz »person_id_seq« für die »serial«-Spalte »person.id«
HINWEIS:  CREATE TABLE / PRIMARY KEY erstellt implizit einen Index »person_pkey« für Tabelle »person«
Migrating: CREATe TABLE "blog_post"("id" SERIAL PRIMARY KEY UNIQUE,"title" VARCHAR NOT NULL,"author_id" INT8 NOT NULL)
HINWEIS:  CREATE TABLE erstellt implizit eine Sequenz »blog_post_id_seq« für die »serial«-Spalte »blog_post.id«
HINWEIS:  CREATE TABLE / PRIMARY KEY erstellt implizit einen Index »blog_post_pkey« für Tabelle »blog_post«
Migrating: ALTER TABLE "blog_post" ADD CONSTRAINT "blog_post_author_id_fkey" FOREIGN KEY("author_id") REFERENCES "person"("id")
[Entity {entityKey = Key {unKey = PersistInt64 1}, entityVal = BlogPost {blogPostTitle = "My fr1st p0st", blogPostAuthorId = Key {unKey = PersistInt64 1}}}]
Just (Person {personName = "John Doe", personAge = Just 35})


Checking my test database with pgAdminIII I see that indeed I now have a person and a blog_post table with the right columns set up. The first having an “John Deo” entry and the second beeing empty.

Rerunning again adds another “John Doe” with id “3” as it should.
As a last test I removed the “delete” so I can check for a blog post … and yes I now have yet another “John 5″ who has 2 posts … so yes it’s working as it should.

This should wrap up the first tests – rather painless which is great!

# Introduction

I want to try some real life style CRUD applications with Haskell and co.
To do this I wanted to install PostgreSQL as I heard lot’s of good stuff about it.

### Disclaimer

I am in no way an expert or even competent with PostgreSQL but this got me a working instance together with an UI tool to administrate it.

# Packages to install

I installed the followig packages following this and some other tutorials on the net:

• postgresql-init
• libpq5
• postgres92
• libqt4-sql-postgresql
• postgresl92-server
• postgresql
• postgresql-server
• libwx-gtk2u_stc-2_8-0-wxcontainer
• libwx-gtk2u_xrc-2_8-0-wxcontainer
• libreoffice-base-drivers-postgresql

Obviously some of those got auto-selected (using YAST) and I added pgadmin3 and the plugin for libre-office as I saw it in the repose ;)

# Post-Install (setting up the user, password, authentication method and data-path)

Following the short guide I

• created a data-directory mkdir /usr/local/pgsql/data
• made (already configured user) postgres the owner of this chown postgres /usr/local/pgsql/data
• switched to this user su - postgres
• initialised the database initdb -D /usr/local/pgsql/data
• started postgres using this folder postgres -D /usr/local/pgsql/data
• created a test database createdb test

(do not forget using godmode for this before you go – su)

Next I had to change the default password (again as su) – following the steps here:

• start postgres (if not already) rcpostgresql start
• switch to the user postgres and open the master-db: su postgres -c psql postgres
• in the sql-command alter the defaultusers password: ALTER USER postgres WITH PASSWORD '****' (of course using you password instead of the stars)

Next on the checklist is changing the authentication mode (I guess this is only a good idea for your local test-instance – but this way it’s much easier to get everything going – indeed pgAdminIII will propose the same if it has problems connecting).
So open the file /var/lib/pgsql/data/pg_hba.conf (you will need administrative rights to access it) and change the uncommented occurrences of ident to md5.
Save the file and restart the database with rcpostgresql restart

Now everything should be fine to use pgAdminIII.

• Host = localhost
• Port = 5432 (this is configured in /var/lib/pgsql/data/postgres.conf),
• User = postgres (of course you can create another user with createuser -D -p <username> – without -p if you do not need a password)
• Passwort = whatever you choose in the last step

That’s it – now you should be able to access everything using this tool or the sql-command (pgsql)

As always: have fun :D

# fold and accumulate

(You can also look at this post using the great my FPComplete tutorial for this)

Recently I played a bit with threepenny-gui and soon ran into the situation where I wanted to update a behavior (my state) using the old state and certain events.
Not having to much real functional approach to reactive programming my mind at once cried “give me some fold man” … but alas: there is nothing that has a close shape to a fold in this library.

So I skimmed through the libraray and could really not get how I could ever get to use “old-state” together with an event …

After a while I finally saw some “accumulate” functions in there, and as I knew their close relationship with folds (for example in .net/linq fold is named Accumulate) I knew I might have found a way out … but wait this is the type-signature of the one I finally used:

accumB :: MonadIO m => a -> Event (a -> a) -> m (Behavior a)


let’s rephrase that a bit and you get basically

accum :: acc -> [acc -> acc] -> acc


It’s quite a bit away from

foldl :: (acc -> b -> acc) -> acc -> [b] -> acc


And I really struggled to finally see how you could use accum to get foldl.

If you like me don’t see how you could possible to this read on – if you find this trivial better close the site now.

# the idea

After 20 minutes or so (searching around for other stuff, coming back, scratching my head, …) I finally saw how to do it:

Just map the bs into functions acc -> acc and vóila: done.

# let’s implement this

So let’s try – here is functional version of the basic accum function:

accum :: acc -> [acc -> acc] -> acc
accum acc []     = acc
accum acc (f:fs) = accum (f acc) fs

main = do
putStrLn $show . accum 0$ [(+1), (+2), (+3), (+4)]


And of course, using f :: acc -> b -> acc and given a b we map this into \acc -> f acc b or flip f b:

fold :: (acc -> b -> acc) -> acc -> [b] -> acc
fold f acc = accum acc . map (flip f)


Seems to be correct (at least the compiler is happy and the results math).

# a bit eq. reasoning

So let’s get a bit further by actually showing that this is correct. Using the definition of accum we see that (abusing the syntax highlighter and eq. reasoning here – so == is meta-equals instead of a lang. construct):

fold f acc [] == accum acc . map (flip f) $[] == accum acc [] == acc  So the base-case is the same as foldl – check. The non-empty list case is not much more: fold f acc (b:bs) == accum acc . map (flip f)$ (b:bs)
== accum acc $((\a -> f a b) : map (flip f) bs) == accum ((\a -> f a b) acc)$ map (flip f) bs


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