Haskell の優雅さを示すためによく使われるコードは、優雅さと分かりやすさだけに特化しており、現実的には遅いことが多い。書き手は他に効率のよい実装があることを知っているのだけれど、読み手はそうではないから、後で効率が悪いと気づいて愕然とするみたいだ。
この記事では、神話になっている例を3つ取り上げ、効率のよい実装と合わせて紹介する。その 3 つの例とは、以下の通り。
- フィボナッチ数
- 素数生成
- ソート
フィボナッチ数
遅延評価を活かした優雅なフィボナッチ数の実装は、以下の通り。
fib n = fibs !! n fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Haskellの「fib = 1:1:zipWith (+) fib (tail fib)」はとても遅いにも書かれているように、この実装は遅い。
その理由は、(+) の計算が遅延し、その待機している計算を捨てられないので、リストが大きくなるからである。
a b c fibs = 0 : 1 : 0 + 1 : 1 + a : a + b : ...
a の計算は遅延するが、b の計算に使われるので捨てられない。a を捨ててリストが長くならないようにするには、(+) の計算を正格評価してやればよい。このためには、自前で zipWith' を実装する必要がある。
zipWith' f (a:as) (b:bs) = x `seq` x : zipWith' f as bs where x = f a b zipWith' _ _ _ = [] fib n = fibs !! n fibs = 0 : 1 : zipWith' (+) fibs (tail fibs)
遅延評価版 foldl に対して正格評価版 fold' はあるのに、遅延評価版 zipWith に対する正格評価版 zipWith' が用意されてないのは、どうしてだろう？
とにかく効率のよいコードを示すには、いろいろ説明しないといけなくなるから、効率は悪いけど優雅なコードを示したくなる気持ちが分かってもらえると嬉しい。
素数生成
よくエラトステネスの篩と称されるコードは以下の通り。
prime n = primes !! n primes = sieve [2..] sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
遅延評価によるエラトステネスの篩に書かれているように、実はこれはエラトステネスの篩ではない。なぜだろう？ エラトステネスの方法で、たとえば5の倍数を消すとき、5 の次は 10 を対象とする。7 は相手にしない。(6、8、9 はすでに消えてる。)
しかし、このコードでは 7 を 5 で割ってしまう。これでは誇大広告と言われてもしかたたないだろう。
この問題を扱った学術的な論文としては、The Genuine Sieve of Eratosthenesがある。実際問題として、Haskellで素数が必要であれば、この論文の作者が実装した primes パッケージを使おう。
ソート
あまりにも有名なのは、以下の quicksort だ。
quicksort [] = [] quicksort (p:xs) = quicksort [ x | x <- xs, x <= p] ++ [p] ++ quicksort [ x | x <- xs, x > p]
そもそもこのコードは、pivot としてリストの先頭を使っているから、整列されたリストをソートしようとすると、O(n^2) になってしまう。
Haskell 98 では、sortBy を O(n^2) の挿入ソートして定義しており驚愕する。しかし実際の実装では、マージソートが使われている。
木を利用したヒープソートは関数プログラミングの楽しみの紹介記事を、配列を利用したヒープソートならST で破壊的なヒープソートを、配列を用いたクイックソートはHaskellの配列でクイックソートを参照のこと。
