Haskell の学習で、他人のコードを読まず、自分で考えるように心がけていたのだが。行列式を求める過程で、nPn をどうしても求めたいのだが。自分の Haskell レベルでは何時間かけても非破壊的なコードで実現できず、ついに他人のコード [1] を見てしまう。
 
  今回は人様が書いた組み合わせ処理を行うコードについて見て行く。最初に言っておくと、ここでのコードは、自分が書くコードよりも数百倍素晴らしいコードである事は、恐らくこのエントリを長らく読んで頂いている多くの人間に共通した意見になると思われる。

  以下が、数の組み合わせを求めるコードの全体になる。

divid :: [Int] -> [([Int],[Int])]
divid xxs@(x:xs) = ([],xxs) : [(x:ys,zs) | (ys,zs) <- divid xs]
divid []         = [([],[])]

perm :: [Int] -> Int -> [[Int]]
perm [] _ = []
perm xs 0 = [[]]
perm xs 1 = map (:[]) xs
perm xs n = concatMap (pm n) $ divid xs
 where pm _ (_,[])      = []
       pm n (hs,(t:ts)) = map (t:) $ perm (hs ++ ts) (n-1)

  まずは、divid 関数から見て行く。
  わずか２行の関数だが。かなりトリッキーなテクニックが駆使されている。中身について考えて行くまえに divid 関数の出力を見てゆく。

main = print $ divid [1,2,3,4]

  としたとき、プログラムは次のような結果を出力する。

[([],[1,2,3,4]),([1],[2,3,4]),([1,2],[3,4]),([1,2,3],[4]),([1,2,3,4],[])]

  型を見れば明らかだが。Int リストのタプルのリストが返されているのだが。(少なくとも自分には) 関数定義から、出力結果が得られるまでの過程を直感的に理解する事は難しい。
  次のフォーマットで、再起処理を追って処理を解析する。

  (再起の深さ) | (戻り値 ( [([Int],[Int])] 型 ))

  まずは main 関数から呼び出されたときは次のようになる。

  1 | ([], [1,2,3,4]):[(1, ys), (zs) | (ys, zs) <- divid [2,3,4]]

  関数定義のリストの内包表記では、次の処理と等価である。

  map (\(ys,zs) -> (x:ys, zs)) $ divid xs

  また、ys や zs は遅延評価される。
  次に、リスト内包表記で書かれた処理について考える。ここでは (divid xs) の結果を map 関数に渡しているので、戻り値を考えれば答えは簡単に出る。
  1 回目の再起 ( 2 回目の呼び出し) の戻り値は次のようになる。

  2 | ([], [2,3,4]):[(2, ys), (zs) | (ys, zs) <- divid [3,4]]

  同じ要領で 3 回目及び 4 回目の呼び出しを考えると次のようになる。

  3 | ([], [3,4]):[(3, ys), (zs) | (ys, zs) <- divid [4]]
  4 | ([], [4]):[(4, ys), (zs) | (ys, zs) <- divid []]

  5 回目の呼び出しでは引数のリストが空になるので ([], []) が返される。すると 4 回目の呼び出し時の戻り値は次のように決まる。

  4 | [([], [4]), ([4], [])]

  最初のタプル "([], [4])" は、既に再起を昇っている (呼び出している) 段階で固定されていたもので、次のタプル "([4], [])" がリスト内包表記の結果になる。
  これより、各再起処理における戻り値は次のようになる。

  3 | [([], [3,4]), ([3], [4]), ([3,4], [])]
  2 | [([], [2,3,4]), ([2], [3,4]), ([2,3], [4]), ([2,3,4], [])]
  1 | [([], [1,2,3,4]), ([1], [2,3,4]), ([1,2], [3,4]), ([1,2,3], [4]), ([1,2,3,4], [])]

  ある関数を再起し、その関数の結果を加工すると、こんな面白いことができる。

  次に perm 関数について見て行く。
  これまたトリッキーな処理に見えるのは、自分のプログラミングスキルが低い為だろうか。落ち込んでてもしょうがないので、中身を見て行く。中核の処理は次の 4 行。1 行目は終了判定である。

perm xs 1 = map (:[]) xs
perm xs n = concatMap (pm n) $ divid xs
 where pm _ (_,[])      = []
       pm n (hs,(t:ts)) = map (t:) $ perm (hs ++ ts) (n-1

  ここでも具体的な値 ([1,2,3,4] 4) が入ってきた場合を考えてみる。
  まず divid の出力を concatMap に渡している。map 処理自体の pm では、divid 関数の出力の後半のタプルの先頭要素 (つまり、"1","2","3","4") を先頭とした、組み合わせのリストを perm を再起して実現している。
  1 回目の呼び出しで、"1","2","3","4" を先頭として 「perm (hs ++ ts) (n-1)」 を呼び出す。
  これに具体的な値を代入させると、例えば先頭が "1" の場合には 「perm [2,3,4] 3」 となり、先頭が "2" の場合には、「perm [1,3,4] 3」となる。
  これを「perm [] 1」まで繰り返せば、各数値の組み合わせのリストが求められる。

  このようにすると、ツリー処理のリーフ部分の戻り値をリストで返すイメージの処理をリストモナドを駆使することで、変数の再代入を許さない Haskell でも実現できる。
  (しかし、これらの処理を自分でゼロから考えて設計する事は絶対できなかったと思う)

・おわりに

  divid 関数でも用いられているように、(x:xs) のように引数のリストをどんどん削って、for ループのような処理を行うのはよくやるが。戻り値を map 関数に渡して加工するのは、よほどうまく設計しないと書けないだろう。
  これにしても、読めば理解できる内容だが。これを自分で思いつくのは難しい。


[1] http://www.sampou.org/cgi-bin/haskell.cgi?Programming%3A%B6%CC%BC%EA%C8%A2%3A%C1%C8%B9%E7%A4%BB