俺は Haskell の sieve についてとんでもない思い違いをしていたようだ...

　　　　　　　 ,.‐'´　`''‐- ､._ヽ 　 /.i　∠,. -─;==:- ､ゝ‐;----//　ヾ.､
　　　　　　　[　|､!　 /'￣r'bゝ}二. {`´ '´＿_ （_Y_）,. |.r-'‐┬‐l l⌒　| }
　　　　　　　 ﾞl |｀}　..:ヽ--ﾞ‐´ﾘ￣ヽd､　''''　 ￣￣　 |l　　　!ﾆ! !⌒ //
.　　　　　　 　 i.! l .:::::　　 　 ｿ;;:..　 ヽ､._　　　　　_,ノ'　　　　　ゞ）ノ./

ええっとこの読みものは昔から思いこんでいたモノが実は嘘でしたと聞いてびっくりしたという驚きを純粋に表現したもので、何かにケチを付けている訳ではありません。読みものとして楽しくお読み下さい。

Haskellian の皆さんは当然ご存知だと思いますが、私にとって、あまりの衝撃でしたので、、、記憶にとどめておくために書いておくの。

Haskell との出会いは先輩がゼミの発表かなんかで sieve (エストラステネ、もといエラストテネスの篩)のカッコいい実装を教えてくれたときです。まだその頃は発表は OHP とかだった。ペラペラっとね。なつかしいなあ:

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

こりゃすごいや、と思ったんですが、色々事情があり、私は Haskell じゃなくて OCaml プログラマになって今に至っています。でもこの時のオドロキはしっかりと心に焼き付いていたのです。皆さんの中にも、上の sieve を見て Haskellian になった方もいるのかもしれませんね。

で、ちょっと今日素数が欲しかったので、「せっかくだから、俺は Haskell を選ぶぜー」と叫びながら上の定義で計算したんですが、何か、遅いの。というか一時間待たされた上に結果が stack overflow とか何それ「おーのー」。OCaml でベタにやったら10秒かからなかった。

あれ、おっかしーなー、やっぱ俺と Haskell って相性よくないのかなと思って、Haskell sieve で検索したら、なんと、

この sieve は本当の sieve ではない。実はお話にならないくらい非効率である。

ナ ゝ　　　ナ ゝ　/　 　 十＿"　 　 ー;=‐　　　　　　　　　|! |!　 　
　cト　　　　cト　/＾､_ﾉ　 | ､.__　つ　 （.__ 　 ￣￣￣￣ 　 ・ ・　　　 

何を今更？今や常識？すいません。Haskell に関しては素人なんで。詳しくは The Genuine Sieve of Eratosthenes を読んでください。やっぱり遅延評価での complexity は難しすぎるわ。そして、正しい計算量の sieve の実装は正直よくわかんないです。でもまあ、その詳細は本題ではないのです。

私の Haskell との美しかったセピア色の思い出は、この論文で見事に打ち砕かれてしまいました。ショックが大きくてちょっと、クラクラしています。なんか、初恋の女の子なんだけど、高嶺の花だから声もかけなかったのが十年ぶりにwktkして会ってみたら実は男で関脇になっていてごっつぁんです、みたいな、そんな、ショック。これから僕は Haskell の何を信じて生きていけばいいの？

この論文が出たときも、なんだってー!!だったので JFP なんかに載ったと思うんですが、皆様も驚かれたのでしょうか。そういや、昔は Haskell と言えばとりあえず sieve を見せとけば恐れ入るだろうという布教体制がひかれておりましたが、この数年見ないな、と思っていたのです。まさか、これなん？

関係ないけど、初代 MSX で頑張ってお絵描きソフトのプログラムを自作して、それでエッシャー風ダマシ絵を描いていたら、実は横8dot に存在できる色は2色のみだったと気づいて、マジでくやし泣きしたあの日を思い出しました。(キングコング(CF-2000)壊れたのかと思った) 参考: http://en.wikipedia.org/wiki/Attribute_clash

あー、でも、MSX も泣いた後チクショーっていろいろプログラミングの勉強させてもらったし、Haskell との思いでも今日から作ればいいんだよね？Haskell よ、味なまねをしよるわ、

　　　　　　　（　 _,, -''"　　　　　 ',　　　　　　　　　　　　 __.＿＿　　　　　　　＿＿＿_
　　　ハ　　　（　l　　　　　　　　　',＿＿_＿,､　　　　　　(:::} ｌ ｌ ｌ ,} 　　 　　／　　　 　 ＼
　　　ハ　　　（　.',　　　　　　　　　ﾄ───‐'　　　　　　ｌ::ｌ￣￣ｌ　　　　　ｌ 　　　　　　 │
　　　ハ　　　（　 .',　　　　　　　　　|　　　　　 　 　 　 　 ｌ::|二二ｌ　　　　　|　　ハ　こ 　.|
　　　　　　　（　／ｨ　　　　　　　　　ｈ　　　　　　　　　, '´￣￣￣｀ヽ　　　|　　ハ　や　│
⌒⌒⌒ヽ(⌒ヽ／　',　　　　　　　　 ｌ.ｌ　　　　　　　　 ,'　 ｒ──—‐tｌ. 　　|　　ハ　つ　│
　　　　　　　￣　　　',　　　　　　　ｆｌｌＪ.　　　　　　　　{　ｒ' ー-､ﾉ ,r‐ｌ 　　 |　　！　め　│
　　　　　　　　　　　　ヾ　　　　 ﾙ'ﾉ　|ll　　　　　　　,-ｌ　ｌ　´~~ ‐ ｌ~｀ﾄ,.　　ｌ 　　　　　　　|
　　　　　　　　　　　　　〉vw'ﾚﾊﾉ　　 l.lll　　　　　　 ヽｌ　ｌ ',　　 ,_ !　,'ﾉ 　　ヽ　 __＿＿／
　　　　　　　　　　　　　l_,,, =====､_　!'lll　　　　　　　.ﾊ. ｌ　 ｒ'"__ﾞ,,｀ｌ| 　　　　)ノ
　　　　　　　　　　＿,,ノ※※※※※｀ｰ,,,　　　　　　 /　ｌヽﾉ ´'ー'´ﾊ
　　　　　　　-‐'"´　ヽ※※※※※_,, -''"｀''ｰ-､ _,へ,＿',　ヽ,,二,,/ .ｌ
　　　　　　　　　　　　 ￣￣￣￣￣　　　　　　　｀''ｰ-､　ｌ　　　　　　ﾄ､へ

こんな感じで行きたいと思います。よろしくお願いします。

いや、 OCaml も色々と残念ですよ。ただ、個人的には小出しにされてきたんで、慣れちゃったヨ。