Dinh Tien Tuan Anh tuananhbirm at hotmail.com
Wed Jul 13 11:37:07 EDT 2005

```Thanks for all your solutions
It seems that recursion is the only way.
i thought it is a variation of the "integer parition" problem so that can be
solved linearly (by generating next solution in (anti)lexicographic order)

i guess i have to learn Monads then, ^_^

Cheers

>From: Kurt <kelanslists at gmail.com>
>Subject: Re: [Haskell-cafe] Coin changing algorithm
>Date: Wed, 13 Jul 2005 11:19:03 -0400
>
>Here's mine, which is similar to Cale's, although done before I saw his:
>
>coins = reverse [1,5,10,25]
>
>change' 0 = [[]]
>change' amt =
>     concat \$ map subchange \$ filter (amt >=) coins
>     where
>         -- recursively make change
>         subchange c =
>             map (\l -> c:l) \$ filter (canon c) \$ change' (amt - c)
>
>         -- filter change lists to those in some canonical order
>         -- this ensures uniqueness
>         canon _ [] = True
>         canon c (x:xs) = c <= x
>
>change amt num = filter (\l -> length l <= num) \$ change' amt
>_______________________________________________