[Haskell-cafe] Re: Coin changing algorithm

[Okasaki, C. DR EECS]

This is a classic dynamic programming problem.  Dynamic programming is
easy to do in Haskell using recursive arrays.  Instead of using
recursive arrays directly, however, I'll add a few helper functions that
make this kind of problem easier.

> import Array
>
> tabulate :: (Ix a) => (a,a) -> (a -> b) -> Array a b
> tabulate bounds f = array bounds [(i,f i) | i <- range bounds]
>
> dp :: (Ix a) => (a,a) -> ((a->b) -> a -> b) -> a -> b
> dp bounds f = (memo!) where
>   memo = tabulate bounds (f (memo!))

'tabulate' just turns a function into an array. 'dp' is a memoizing Y
combinator.  That is, you give the same kind of almost recursive
function you would give to the Y combinator, and it "ties the knot" for
you, but also interposes an array to hold the intermediate results.

(What do I mean by an "almost recursive function"?  I mean that instead
of writing a recursive function "f = ...f...", you instead write f to
take what will end up being the recursive function as its first
argument.  Then, whenever the f would normally call itself, it instead
calls this argument, as in "f rec = ...rec...".)

Now, here is the change algorithm, using esentially the same recursion
as Radu, except that I introduce an 'i' parameter, that is the index of
the largest denomination that you are allowed to use.  (Using this
parameter makes it easier to store the results in an array than passing
around a list of the available coins.)

> change m n = dp bounds f (m,n,8) where
>   bounds = ((0,0,0), (m,n,8))
>   coins = listArray (1,8) [1,2,5,10,20,50,100,200]
>   f rec (m,n,i)
>     | m == 0 = [[]]
>     | n == 0 || i == 0 = []
>     | c > m = rec (m,n,i-1)
>     | otherwise = map (c:) (rec (m-c,n-1,i)) ++ rec (m,n,i-1)
>     where c = coins!i

In the f function, m is the amount of change to make, n is the number of
coins that can be used, and i is the highest kind of coin that you are
allowed to use.  

You can do most traditional dynamic programming problems this way.

Enjoy,
Chris