僕は Haskell を知るまで、再帰に関しては、もう学ぶべきことはないと思っていました。しかし、繰り返しさえ再帰で実現しなければならない純粋関数型言語に触れてはじめて、再帰の深淵を見た気分になりました。
以下、Programming in Haskell から 3 つ問題を出します。あなたには、実装できるでしょうか？
問題
以下の関数を実装しなさい。
- 与えられたリストのすべての部分リストを生成する関数 subs
- 第一引数を第二引数のリストへ挿入したすべてのリストを生成する関数 interleave
- 与えられたリストの順列を生成する関数 perms
言葉だけではよく分らないと思いますので、実行例を示します。
subs [1,2,3] → [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]] interleave 1 [2,3,4] → [[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]] perms [1,2,3] → [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
subs
subs に与えるリストの大きさを増やしながら、実行してみましょう。
subs [] → [[]] subs [3] → [[],[3]] subs [2,3] → [[],[3],[2],[2,3]] subs [1,2,3] → [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
ここで、最後の式について考えることにし、x = 1、xs = [2,3] とします。
パターンをよく観察すると、subs [1,2,3] の結果の前半は、subs [2,3] に等しいと気付きます。一つ前の式ですから、これは subs xs と表現でき、これを yss と呼ぶことにしましょう。
つまり、Haskell で書くとこうなります。
subs (x:xs) = yss ++ 後半 where yss = subs xs
さて後半ですが、subs [2,3] すなわち yss の各要素に x をコンスした形になっています。よって subs は、こう実現できます。
subs (x:xs) = yss ++ map (x:) yss where yss = subs xs
interleave
interleave に与えるリストの大きさを増やしながら、実行してみましょう。
interleave 1 [] → [ [1]] interleave 1 [4] → [ [1,4], [4,1]] interleave 1 [3,4] → [ [1,3,4], [3,1,4], [3,4,1]] interleave 1 [2,3,4] → [[1,2,3,4],[2,1,3,4],[2,3,1,4],[2,3,4,1]]
ここで、最後の式について考えることにし、x = 1、y = 2、ys = [3,4] とします。
パターンをよく観察すると、結果の tail は、interleave 1 [3,4] に 2 をコンスしたものになっています。すなわち、こう書けます。
map (y:) (interleave x ys)
結果の head は、x:y:ys と書けますから、結局全体としてこう実装できます。
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)
perms
perms に与えるリストの大きさを増やしながら、実行してみましょう。
perms [] → [[]] perms [3] → [[3]] perms [2,3] → [[2,3], [3,2]] perms [1,2,3] → [[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]
ここで、最後の式について考えることにし、x = 1、xs = [2,3] とします。パターンをよく観察すると、perms xs の各要素に対し、x を interleave すればよいと分ります。
よって、こう実装できます。
perms (x:xs) = concatMap (interleave x) (perms xs)
