関数型プログラミング言語である、Haskellを使って中間メモリーを必要とするエラトステネスの篩を実装しようとしたら結構難しいことに気づきました。
まあ、関数プログラミングでメモリーを想定するのもどうかと思いますけど。２時間くらいうなった挙句、できたプログラムが以下。
not_multiplied:: Int -> Int -> Bool
not_multiplied y x = (x == y || x `mod` y /= 0)
eratosthenesSieveList:: [Int] -> [Int] -> [Int]
eratosthenesSieveList (x:xs) lst = if null xs then lst else eratosthenesSieveList xs (filter (not_multiplied x) lst)
eratosthenesSieve:: Int -> [Int]
eratosthenesSieve p = eratosthenesSieveList [2..p] [2..p]
リストを２つとるところが味噌で、第２引数のリストを第１引数のリストで徐々に変形していくようなイメージです。
素数リストの作成プログラムは公式ページにある通り、実際には1行で書けます。
そういえば、ghci が型定義を受け付けない（:: が使えない）というのは既知の問題なのだろうか。
コメントを残す