Haskell と式の展開

順列を列挙するプログラムは次のようになる。

perm [] = [[]]
perm xs = concat [map (x:) $ perm (delete x xs)| x <- xs]

一見何かの暗号のようで意味が分からないが、上のプログラムで perm に引数 "abc" を渡したときの動作を考えてみる。

[map ... | x <-xs] の部分は集合の内包的な定義だから、その意味は、リスト xs に含まれる要素を一つ x として取り出し、map ... の関数の引数として渡して得られた値を要素とする新しい集合をつくるということだ。

抽象的な説明では意味がつかめないので、xs = "abc" の時のことを考えてみる。文字集合 "abc" から、'a', 'b', 'c' を取り出してそれぞれを、map ... にわたすということだ。

map (x:) perm (delete x xs) の意味は、たとえば、x = 'a' の時はこれと、perm (delete x xs) つまり "abc" から 'a' を取り除いた文字集合 "bc" の順列できたリスト [ "bc", "cb" ] の要素とをつなげた文字列のリスト ["abc", "acb" ] だ。この操作は、x = 'b', x= 'c' の場合も同様な操作が行われるから、結局、xs = "abc" のとき、[map ... | x <-xs] の戻り値は、[["abc", "acb"], ["bac", "bca"], ["cab", "cba"]] となる。外側の括弧は内包的定義の結果できるリストの括弧で、内側の括弧はmap 関数の適用によってできるカッコだ。内側の括弧は余分なので、concat で取り除いて結局、["abc", "acb", "bac", "bca", "cab", "cba"] となる。

これだけの内容が2行に収められているのは驚異的だが、concat がなぜ登場しなくてはならないのかがもう一つ腑に落ちない。そこで、上のプログラムの2行目の再帰式を直接展開してみることを考えてみる。xs = "abc" の時定義の再帰式を展開すると次のようになる。

perm "abc" = concat [map (x:) $ perm (delete x xs)| x <- "abc"]
= concat [map ('a':) $ perm "bc", map ('b:') $ perm "ac", map ('c':) $ perm "ab"]
= concat [map ('a':) $ concat [map (x:) $ perm (delete x xs)| x <- "bc"], .. , .. ]
= concat [map ('a':) $ concat [map ('b':) $ perm "c", map ('c':) $ perm "b"], .. , .. ]
= concat [map ('a':) $ concat [map ('b':) $ concat [map ('c':) [[]]], map('c') $ concat [map ('b') [[]]], .. , .. ]
= concat [map ('a':) $ concat [map ('b':) $ concat ["c"], map ('c:') $ concat ["b"]]], .. , .. ]
= concat [map ('a':) $ concat [map ('b':) "c", map ('c':) "b"], .. , .. ]
= concat [map ('a':) $ concat [["bc"], ["cb"]], .. , .. ]
= concat [map ('a':) ["bc", "cb"], .. , .. ]
= concat [["abc", "acb"], ["bac", "bca"], ["cab", "cba"]]
= ["abc", "acb", "bac", "bca", "cab", "cba"]

となって、式の展開をする上で concat は不可欠だということが分かる。

このように、Haskell では、どのように暗号的な関数の定義であっても、単純な式の展開を繰り返すことによってプログラムが実行されているということが分かる。このとき注意が必要なのは、式の展開は機械的な操作であると言うことだ。関数の定義の意味が全く分からなくても逐次関数を展開することによって最終的にプログラムは実行される。つまり、これは関数の定義の統語論的な展開だ。

一方順列プログラムについて最初に試みたのはその意味を考えるという意味論的な手法だった。

Haskell のプログラムは複雑な内容をコンパクトに記述できる一方で暗号的な記述になりがちだが、上に述べたような、意味論的なアプローチと、式をひたすら展開するという統語論的なアプローチを適宜適用することによって、他の人の書いたプログラムを理解することができるようになる。
[PR]
by tnomura9 | 2009-09-02 22:14 | Haskell | Comments(0)
<< Haskell と意味論と統語論 Haskell ワンライナー >>