人気ブログランキング | 話題のタグを見る

Haskell で順列のプログラムを作ってみた

Haskell でリストの要素を使った順列を列挙する関数をプログラムしてみた。このような関数を perm とすると、関数型は perm :: [a] -> [[a]] となる。

そこで先ず perm [] の値を考えてみる。これは [[a]] 型になり、[] の順列は [] 一個だけだから perm [] = [[]] になるはずだ。そこで prem [] と同じ動作をする関数を次のように perm0 x として定義する。

Prelude> let perm0 [] = [[]]
Prelude> perm0 []
[[]]

次に要素が1個だけの配列 [a] について perm [a] がどのように振る舞うかを考えてみた。これを perm1 として考えるが、あとで perm を再帰的に定義したいので、perm0 x との関係で考えてみた。

[a] の要素 a を取り出すと、[] が残る。perm0 [] = [[]] であることを考えると。a を使った順列は 、

map (a:) [[]]

になる。これは a と a を取り去った配列の全ての順列との結合を意味する。[a] から a を取り去ってできる配列は [] 一つだけだから [] の全ての要素の配列を集めたリストは [[]] だからだ。上の結果は ghci でも確認できる。

Prelude> map (1:) [[]]
[[1]]

さて、[a] から a を取り去ってできるリストはどうやって作ればいいのだろうか。それは filter 関数を利用すれば簡単にできる。

Prelude> filter (/=1) [1]
[]

部品がそろったので perm [a] と同じ動作をする prem1 [a] をプログラムすることができる。

Prelude> let perm1 x = map (\y -> map (y:) (perm0 (filter (/=y) x))) x
Prelude> perm1 [1]
[[[1]]]

この map が入れ子になっているプログラムがどんな動作をしているのかを説明するのは少しむずかしいが順を追って考えてみよう。

先ず最外側の map はリスト [a] から要素 a を取り出す操作を表している。これは、ラムダ関数の変数 y に引き渡される。内側の map はリスト (perm0 (filter (/=y) x) の要素を一つ取り出して y をその先頭に結合する。perm0 はどんなリストかというと、リスト filter (/=y) x の要素の順列からできるリストだ。さらに filter (/=y) x はリスト x から要素 y を取り去ってできるリストである。

具体的に [1] について上のプログラムがどう動作するかを考える。まず y には 1 が入る。もちろん x = [1] である。そうすると filter (/=y) x = [] である。従って perm0 (filter (/=y) x) = [[]] である。すると map (y:) (perm 0 (filter (/=y) x))) x = map (1:) [[]] = [[1]] だ。しかし、最外層の map もあるので結局 perm1 [1] = [[[1]]] になる。

perm1 [1] は上のプログラムでうまく動作するような気がするが、perm の型を考えると perm1 [1] = [[1]] となって欲しい。そこで perm1 の定義を次のように変更する。

Prelude> let perm1 x = concat (map (\y -> map (y:) (perm0 (filter (/=y) x))) x)
Prelude> perm1 [1]
[[1]]

perm1 [1] が動いたので perm2 [1,2] を考えてみる。perm1 x の定義は perm0 x との関係で定義していたので、perm2 x は perm1 との関係で定義できるのではないかと考えてみる。すなわち、perm1 の定義の perm1 を perm2 に perm0 を perm1 に変えてみる。驚いたことにこの企みは次のように成功する。

Prelude> let perm2 x = concat (map (\y -> map (y:) (perm1 (filter (/=y) x))) x)
Prelude> perm2 [1,2]
[[1,2],[2,1]]

調子に乗って perm3 [1,2,3] も試してみる。

Prelude> let perm3 x = concat (map (\y -> map (y:) (perm2 (filter (/=y) x))) x)
Prelude> perm3 [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

再帰的定義の利点は、base case から初めて統一的な方法で recursive case のプログラムを記述できることだ。ここまで来たら目的の perm :: [a] -> [[a]] のプログラムをすることができる。これまでの perm0, perm1, perm2 を同じ perm で定義すればいいのだ。

Prelude> :{
Prelude| let
Prelude| perm [] = [[]]
Prelude| perm x = concat (map (\y -> map (y:) (perm (filter (/=y) x))) x)
Prelude| :}
Prelude> perm [1,2,3]
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

再帰的プログラムを考えるのは再帰的定義の部分のテストができないので難しくなりがちだが、base case から逆算的にテスト用の関数を作っていくと、テスト用の関数から再帰的定義に移行するのは意外に簡単だった。


by tnomura9 | 2017-03-14 23:15 | Haskell | Comments(0)
<< 手のひらに咲いた花 免疫学の知識 >>