2010-07-12

よく haskell コードの例として出される

primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

は遅いよ，という割と有名な話を昨日読んでみたんだけど，なんだか腑に落ちない部分があったのでここに書いてみる．参考にした記事は以下の 3 つ:

まず上の 2 つを読んで「篩に掛けられた後のリストの先頭を n とすると n^2 未満の (それまでの篩に引っかからなかった) 数は素数だからそれを利用して計算量を減らそう」ていうことだろうと適当に理解したつもりだったんですが，3 番目を読むと

エラトステネスの方法で、たとえば 5 の倍数を消すとき、5 の次は 10 を対象とする。7 は相手にしない。(6、8、9 はすでに消えてる。)
しかし、このコードでは 7 を 5 で割ってしまう。これでは誇大広告と言われてもしかたたないだろう。

という風に書いてあって，なんか自分の理解と違うなあという感じで頭が混乱してるなうというわけです．それで，もやもやな疑問を放置するのもあれなのでとりあえずこの記事の意図するのはどういうことだろうと考えてみたのが，

でもこれも間違いで，一見すると正しいようにみえるけどその前の篩でいくつか数が抜け落ちているため 4 個飛ばしで値を除くという処理自体が不可能．
そういうわけで Haskell さんむずかしくて意味が分からない感じなので誰か助言ください…．

実験記