短いプログラムで,構文のおさらいをします.

階乗を求める(再帰的な関数)

--階乗(!n)
fact 1 = 1
fact n = n*fact (n-1)

あらゆる言語の再帰関数のサンプルで見かけますね^^;*1

実行結果

Main> fact 10
3628800

素数を求める(リストの内包表現)

エラトステネスのふるいという方法で,素数を求めてみます.
整数の集合の中から,分かっている一番小さい素数(2)の倍数を消去します.
2,3,4,5,6,7,8,9,10...
残っている数の中で,2の次に大きな数(3)は素数ですね.
今度はこの素数(3)の倍数も集合の中から消していきます.
2,3,4,5,6,7,8,9,10...
すると残った一番小さな数(5)も素数です.これを繰り返していくと素数の表が得られます.

--素数(エラトステネスのふるい)
eratosthenesSieve (x:xs) =
    x: eratosthenesSieve [y|y<-xs, y `mod` x /=0]  --ふるいにかける
prime = eratosthenesSieve [2..]

eratosthenesSieve関数に渡すリストの先頭は素数です.
渡されたリストの中から,その素数で割り切れる数を省く*2のが

[y|y<-xs, y `mod` x /=0]

の内包表現です.

このprime関数を呼び出すと,ずーっと素数の続くリストを返しますが
このリストは無限リストでしょうか? 素数が無限に続けば無限リストですが...
実は,上で紹介した階乗を使うと素数が無限個続くか調べる事が出来ます.
気になる方は素数は無限個存在するかを読んでみてください.

実行結果

素数を小さい物から100個取得してみます.

Main> take 100 prime
[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,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,
223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,
457,461,463,467,479,487,491,499,503,509,521,523,541]

コメント


お名前:

*1 スタックいらないのにねぇ
*2 割り切れない数だけで,リストを構成