Haskellの神話

Haskell

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の配列でクイックソートを参照のこと。