Haskellのお勉強（４） 素数

素数の表示

Haskellだけど細々と勉強続けてるよ。でもなかなか進まない。解説サイト見たりしてるんだけどさ、書かれてる内容は理解できても、それを実際のプログラミングの中でどう活かせば良いのかが分からないんだよね。ということでまた簡単なとこから。

import System.Environment   
import Text.Printf

prime p [] = p
prime p (x:xs) =
   prime (p ++ [x]) [ i | i <- xs, i `mod` x /= 0 ]

main = do
    args <- getArgs
    let n = if args == [] then 100 else read(args !! 0)
    print $prime [] [2..n]

エラトステネスの篩。再帰使ってやってみたよ。

~/haskell$ runghc prime.hs
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
~/haskell$

できたよ。相変わらずちょっとした記述間違いでドツボにハマっちゃうよ。prime p (x:xs) =のところをprime p x:xs =って間違えてたんだけど、それが原因だって気付くまでえらく時間掛かっちゃった。
計算途中でリストのお尻に要素を追加してるんだけど、こういうのHaskellは苦手なのかな。Lispと同じ感じで。ってことでちょっと変更してみる。

import System.Environment   
import Text.Printf

prime p [] = reverse p
prime p (x:xs) =
   prime (x:p) [ i | i <- xs, i `mod` x /= 0 ]

main = do
    args <- getArgs
    let n = if args == [] then 100 else read(args !! 0)
    print $prime [] [2..n]

リストの先頭に要素を追加していくようにして、最後にreverseするようにしてみたよ。

~/haskell$ runghc prime2.hs
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
~/haskell$

同じ結果が得られたよ。おそらくprime2.hsの方が速いんだと思うけどどうだろうか。計測してみる。

~/haskell$ time runghc prime.hs 10000
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
途中省略
,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973]

real	0m3.346s
user	0m2.567s
sys	0m0.178s
~/haskell$ time runghc prime2.hs 10000
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,
途中省略
,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973]

real	0m2.715s
user	0m2.300s
sys	0m0.161s
~/haskell$

おお、やっぱりprime2.hsの方がちょっと速いね。