Haskell勉強日誌 -エラなんとかの篩-

練習のため、素数判定で有名なエラなんとかの篩を実装しました。

エラなんとかの篩

13行目のx ^ 2が毎回評価されると実行速度に悪影響を与えそうですが、参照透明性のお陰で１度しか評価されていないハズですね。 reverseはコストが高い処理ですが、１回しか評価されないのでまあ良いでしょう。

primesを無限リストにして、take 100 primesのように書くほうがHaskellっぽい気もしますが、無限リストを返すようにしてしまうと 「篩に書けるのはmaxの平方根まででよい」という恩恵を受けられなくなってしまうため、やめました。