８回目のHaskell

だんだんペースが落ちてきましたがまだ何とかなっている・・・はずです。まあ止まらなければよいよ（適当

今日のお題は"nextperm.c"順列を求めます。C++のSTLにもありますね。初期の配列を渡して、そこから随時次の順列に書き換えて、全ての順列が終了したらfalseを返す。これをhaskellで表現・・・の前に、正直言うと順列を生成するアルゴリズムが最初全然わかりませんでしたorz　ｃのソースを追いまくって結構時間かかって理解しました。
オリジナルのＣのソースだと、後ろから検索していますがhaskellは若干都合が悪いのでちょっと解釈を変えました。考え方としては、最初の1個と取り出し、残りの部分で順列を作る。その残りの部分の順列が終了したら最初の1個と中の1個を取り替えてまた順列を作る。という考え方なら再帰の形になるのでhaskell的に都合がよいです（＾＾；　それから、順列を生成した場合、最後は失敗するので、勉強もかねてMaybeモナドを使って実装してみました。

main = print ( next_permutation [1,2,3,4] >>= next_permutation >>= next_permutation >>= next_permutation )

next_permutation :: (Ord a) => [a] -> Maybe [a]
next_permutation []     = Nothing
next_permutation (n:ns) = case ( next_permutation ns ) of
                            Just as -> Just (n:as)
                            Nothing -> change n ns

change :: (Ord a) => a -> [a] -> Maybe[a]
change m [] = Nothing
change m (n:ns) | m > n     = Nothing
                | otherwise = Just (sub_change [] n m ns)
    where sub_change rs p m [] = (p:m:rs)
          sub_change rs p m (n:ns) | m < n     = sub_change (p:rs) n m ns
                                   | otherwise = (p:(cr (n:m:rs) ns))
              where cr rs (n:ns) = cr (n:rs) ns
                    cr rs []     = rs

例によってメイン関数は激烈に適当です。本当ならnext_permutationの戻り値がnothingになるまで結果を表示したいのだけれどもIOモナドがまだ全然わからないのでこんな適当になってますorz　Maybeモナドを使って嬉しかったので>>=を連打してみました（ぉ
今回、えらい時間がかかりました。haskellの文法よりもアルゴリズムのデバッグの方が苦労したかも（汗　

そろそろ本格的にモナドを勉強したいところ・・・だけど、まだ８回しか組んでないんだよね（＾＾；　あわてずにもうちょっとじっくりやっていこうと思います。