両替の組み合わせは？

id:a-san さんの両替するのに何通りあるか？に刺激されて，両替の組み合わせを列挙する enumChange をつくってみた。Maybe の扱いでちょっと苦労したよ。

　cf. http://d.hatena.ne.jp/a-san/20060508#p1

enumChange coins amount = map peel (cc amount 0)
    where
        cc amount kindsOfCoins
            | amount == 0 = [Just []]
            | (amount < 0) = [Nothing] | kindsOfCoins >= length coins = [Nothing]
            | otherwise =
                filterN ((cc amount (kindsOfCoins + 1)) ++
                       (divide faceOfCoin (cc (amount - faceOfCoins) kindsOfCoins)))
            where
                faceOfCoin = coins !! kindsOfCoins

divide a = map divide'
    where
        divide' x = case x of
            Just m -> Just (a:m)
            Nothing -> Nothing

filterN list = filter (\x -> x /= Nothing) list

peel x = case x of
             Just m -> m
             Nothing -> error "`Nothing' is found."

実行。

*Main> enumChange [10,5,1] 10
[[1,1,1,1,1,1,1,1,1,1],[5,1,1,1,1,1],[5,5],[10]]
*Main> length $ enumChange [10,5,1] 10
4

countChange は id:a-san さんのもの。

*Main> length $ enumChange [500,100,50,10,5,1] 100
159
*Main> countChange [500,100,50,10,5,1] 100
159
*Main> length $ enumChange [50,25,10,5,1] 100
292
*Main> countChange [50,25,10,5,1] 100
292
*Main> enumChange [500,100,50,10,5,1] 100
[[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,
5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1],[5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[5,5,5,5,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
（以下略）

いけてるみたいだな。

以下，自分用のメモ。

• cc は両替したコインの組み合わせのリストを返す。
• amount == 0 ならうまくいった組み合わせなので，リストの終端としての空リストを返す。
• (amont < 0)，kindsOfCoins >= length coins のときはその組み合わせがうまくいかないときなので Nothing。
• (cc amount (kindsOfCoins + 1)) は kindsOfCoins のコインを１枚も使わない場合の組み合わせ。返ってくるリストには Nothing が混じっているから filterN で取り除いてやる。
• (divide …) は kindsOfCoins のコインを１枚以上使う場合の組み合わせ。これは kindsOfCoins のコインを０枚以上使って (amount – faceOfCoin) を両替する場合の組み合わせのそれぞれに，kindsOfCoins を１枚追加して求めている。
• cc の返すリストは Maybe [a] のリストだから peel で Maybe をはずす。

追記：
Data.Maybe に catMaybes という関数があった。わざわざ peel を作んなくてもよかったのか。
GHCi で使うなら :module Data.Maybe，プログラムで使うなら import Data.Maybe しておく。

Prelude Data.Maybe> :type catMaybes
catMaybes :: [Maybe a] -> [a]
Prelude Data.Maybe> catMaybes [Just 1, Just 2, Just 3]
[1,2,3]

Nothing は無視してくれるみたいだ。

Prelude Data.Maybe> catMaybes [Just 1, Nothing, Just 3]
[1,3]

ってことは filterN もいらないのか……orz