自分で遅延リストを作って、素数計算

SML 30分プログラム

30分プログラム、その668。自分で遅延リストを作って、素数計算をしてみました。
明日、研究室で発表をしなければいけないことを考えてると憂鬱になるので、素数を数えるコードを書いてみました。こういう無心で書けるコードは心が落ちつくので、わりとありだと思います。

使い方

- forEach (printLn o Int.toString) primes;

で延々と素数が表示されるので、それを見てを心を落ちつける。

ソースコード

datatype 'a stream = Nil
		   | Cons of 'a * (unit -> 'a stream)

fun cons x y = Cons (x,y);

fun force f = f ()

fun fromN n =
    cons n (fn () => fromN (n+1));

fun filter f xs =
    case xs of
	Nil => Nil
      | Cons (x,xs) =>
	if f x then
	    Cons (x,fn () => filter f (force xs))
	else
	    filter f (force xs)

fun forEach f Nil = ()
  | forEach f (Cons(x,xs)) = (f x; forEach f (force xs))

fun sieve Nil = Nil
  | sieve (Cons(x,xs)) =
    let
	fun ys () = sieve (filter (fn n => n mod x <> 0)
				  (force xs))
    in
	Cons(x,ys)
    end

fun take 0 _            = []
  | take _ Nil          = []
  | take n (Cons(x,xs)) = x::take (n-1) (force xs);

fun printLn s =
    (print s; print "\n")

val primes = sieve (fromN 2)

参考