Haskellでエラトステネスの篩
Haskellで素数のリストを作ってみた。
dropMultiples :: Integral a => a -> [a] -> [a] --dropMultiples x ys = filter (\z -> 0 /= (mod z x)) ys dropMultiples x = filter ((0 /=) . (`mod` x)) -- ポイントフリーにしてみたけど微妙? takePrimes :: Integral a => [a] -> [a] takePrimes [] = [] takePrimes (x:xs) = x : (takePrimes $ dropMultiples x xs) primes :: Integral a => [a] primes = takePrimes [2..] main :: IO () main = print $ take 10 primes
エラトステネスの篩をかなり安直に書いただけ。 とりあえず10個目まで出力。
こんな愚直な実装でも無限に計算できる訳で、遅延評価ってのは凄いねぇ。