両替問題（末尾再帰版）

硬貨の種類を順に増やすというボトムアップを行うシンプルなもの．

module CountChange where

type Amount = Int
type Coins = [Int]
jpy :: Coins
jpy = [1,5,10,50,100,500,1000,2000,5000,10000]

cc :: Coins -> Amount -> Integer
cc cs a = foldl f (1:repeat 0) cs !! a
  where
    f xs n = exs
      where
        exs       = hxs ++ zipWith (+) txs exs
        (hxs,txs) = splitAt n xs