CoinChange.hs

-- code from http://stackoverflow.com/a/21427171/849891 by András Kovács
combsOf :: Int -> [a] -> [[a]]
combsOf n _ | n < 1   = [[]]
combsOf n (x:xs)      = combsOf n xs ++ map (x:) (combsOf (n - 1) xs)
combsOf _ _           = []

-- what I meant was this
change :: Int -> [Int] -> [[Int]]
change n xs 
     | n<0 || null xs = []
change n _  | n==0    = [[]]
change n (x:xs)       = change n xs ++ map (x:) (change (n - x) (x:xs))

-- *Main> length $ change 100 [1,5,10,25,50]   ==>  292
-- although it doesn't scale, like the  DP version does:
--   (code by András Kovács from the forked-from Gist)
coinChange :: [Int] -> [Int]
coinChange = foldr go (1: repeat 0) where
    go coin xs = rs where
        (a, b) = splitAt coin xs
        rs = a ++ zipWith (+) b rs
     -- rs = take coin xs ++ zipWith (+) (drop coin xs) rs

main = print $ coinChange [1,5,10,25,50] !! 100 -- prints 292

-- foldr g [1,0,0,0,...] [1,5,10,25,50]
--  = g 1 $ g 5 $ g 10 $ g 25 $ g 50 [1,0,0,0,...]
--  = 

{-
Prelude> take 101 $ g 50 (1:repeat 0)
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]
Prelude> take 101 $ g 25 $ g 50 (1:repeat 0)
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0
,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0
,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3]
Prelude> take 101 $ g 10 $ g 25 $ g 50 (1:repeat 0)
[1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,0,0,0,0
,1,0,0,0,0,1,0,0,0,0,3,0,0,0,0,1,0,0,0,0,3,0,0,0,0,1,0,0,0,0,3,0,0,0,0,3,0,0,0,0
,3,0,0,0,0,3,0,0,0,0,3,0,0,0,0,3,0,0,0,0,6]
Prelude> take 101 $ g 5 $ g 10 $ g 25 $ g 50 (1:repeat 0)
[1,0,0,0,0,1,0,0,0,0,2,0,0,0,0,2,0,0,0,0,3,0,0,0,0,4,0,0,0,0,5,0,0,0,0,6,0,0,0,0
,7,0,0,0,0,8,0,0,0,0,11,0,0,0,0,12,0,0,0,0,15,0,0,0,0,16,0,0,0,0,19,0,0,0,0,22,0
,0,0,0,25,0,0,0,0,28,0,0,0,0,31,0,0,0,0,34,0,0,0,0,40]
Prelude> take 101 $ g 1 $ g 5 $ g 10 $ g 25 $ g 50 (1:repeat 0)
[1,1,1,1,1,2,2,2,2,2,4,4,4,4,4,6,6,6,6,6,9,9,9,9,9,13,13,13,13,13,18,18,18,18,18
,24,24,24,24,24,31,31,31,31,31,39,39,39,39,39,50,50,50,50,50,62,62,62,62,62,77,7
7,77,77,77,93,93,93,93,93,112,112,112,112,112,134,134,134,134,134,159,159,159,15
9,159,187,187,187,187,187,218,218,218,218,218,252,252,252,252,252,292]
-}