珠玉のリスト・プログラミング

Haskell

僕は 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)

関数プログラミング

著者の Hutton さんは、なんて頭がいいんだと思っていたら、これらは "An introduction to functional programming" から取ってきた関数だそうです。日本語訳は「関数プログラミング」ですね。

そういえば、学生のときに「関数プログラミング」を輪講で読みました。学生のころに、ようやく追いついたということか！ 読み返したいけれど、本は実家の段ボールの中かなぁ。。。