Haskell の 4 つの糊

なぜ関数プログラミングは重要かでは、糊の重要さが強調されています。

問題を解くための部品プログラムを書くとき、その問題を部分問題に分割し、部分問題を解き、その解を合成する。元の問題を分割する方法は、部分解を張り合せる方法に直接依存する。それゆえに、概念的には問題をモジュール化する能力を高めるためにはそのプログラミング言語のなかで新たな糊の類を用意しなければならない。...

糊の重要性は、大工仕事との類比によって、正しく評価できる。椅子は、部分(座部、脚、背もたれなど)を作り、それらを正しくくっつけ合せることで容易に作ることができる。しかし、これはジョイントと木を張り合せるという能力に依存する。その能力がなければ、椅子を作る方法はひとつ木の塊からそれを彫り出す以外なく、非常に難しい作業になる。この例は、モジュール化の強大な力と正しい糊を持つことの重要性の両方を例示するものである。

僕が思うに Haskell には 4 つの糊があります。

• 関数合成(.)
• 高階関数
• 遅延評価
• モナドの bind

関数合成(.)

関数合成を使うと、関数を簡潔に表現できます。

例として、単語の前後の空白を削る strip という関数を考えてみましょう。

strip str = fst (break (==' ') (dropWhile (==' ') str))

こんな風に動きます。

strip "  foo   "
→ "foo"

Lisp に慣れてくると括弧は気にならなくなりますが、Haskell に慣れてくると括弧を ($) で置き換えるようになります。

strip str = fst $ break (==' ') $ dropWhile (==' ') str

さらに慣れてくと、(.) を使うようになるようです。Haskell の Trace の使い方には、以下のように書かれています。

Haskellプログラミングになれてくると，処理の連結には関数適用オペレーター ($) ではなく関数合成オペレーター (.) になることが普通になる．

しかし、(.) で合成できるのは、一つの引数を取る関数です。物わかりの悪い僕は、こんな制約の厳しいオペレータなんて、使えるところは少ないと思っていました。たとえば dropWhile は引数を二つ取りますから、($) を (.) には置き換えられません。

-- これは間違い
strip str = fst . break (==' ') . dropWhile (==' ') str

しかし、Haskell では、関数をカリー化できるのでした。なので、こう書けます。

strip str = (fst . break (==' ') . dropWhile (==' ')) str

再び括弧が出てきて嫌だなと思った瞬間に、こう書けることに気付くはずです。

strip = fst . break (==' ') . dropWhile (==' ')

高階関数

Google の MapReduce が有名になったため高階関数の説明は、もう不要でしょう。分らない人は、「君のプログラミング言語で、これ、できる？」を読んで下さい。

大切なのは、「データの走査」と「仕事」を分けることです。

新しいデータ型を定義したときにその型を処理する高階関数を書くべきである。そうすれば、そのデータ型の取り扱いが簡単になり、その表現の詳細に関する知識を局所化できる。

遅延評価

g (f input)
...
もし、gがfの出力をすべて読むことなく終了すれば、fは破棄される。fは無限に出力を生成しつづける停止しないプログラムでも構わない。それはgが終了すればすぐに強制的にfは停止させられるからである。これにより、停止条件はループの本体とは切離すことができ、強力なモジュール化が可能となる

たとえば、n 番目の素数を計算する関数 nthPrime は、以下のように書けます。

sieve (p:ps) = p : sieve nonMultipleP
    where
      nonMultipleP = filter (\q -> q `mod` p /= 0) ps
primes = sieve [2..]
nthPrime n = primes !! n - 1

"[2..]" も sieve も無限リストを生成しており、停止条件なんて気にしていないことが分るでしょう。

「なぜ関数プログラミングは重要か」にはニュートン法で平方根を求めるコードが載っています。Miranda で書かれているので、参考までに Haskell で書き直してみました。

next :: Int -> Float -> Float
next n x = (x + m / x) / 2
    where
      m = fromInteger $ toInteger n
within eps (a:b:rest)
    | abs(a-b) <= eps = b
    | otherwise       = within eps (b:rest)
sqroot a0 eps n = within eps $ iterate (next n) a0

iterate で無限のリストが生成されているのが分りますか？

モナドの bind

モナドとは、Monad クラスのインスタンスであるデータ型です。Monad クラスを満たすためには、bind(>>=)と return という関数を定義する必要があります。bind は、その名の通り糊です。すなわち、Monad であれば共通の枠組みとして、この強力な糊が使える訳です。

Haskell の素敵な応用例は、なんといっても Parsec でしょう。Parsec は、モナド・パーサーです。小さなパーサーを複数書いて、bind で合成できます。

たとえば、ダブルクオートで囲まれた文字列にマッチするパーサーは、以下のようになります。

quoted = do char '"'
            s <- many (noneOf "\"")
            char '"'
            return $ "\"" ++ s ++ "\""

一文字にマッチするパーサー char や oneOf が合成されて、より大きなパーサー quoted が構成されているのが分るでしょうか？