ふるい〜ふるかね〜

某日記にインスパイヤされて
無限リストを書いてみた。OCamlで。

open Lazy
type 'a inf_list = {
  hd : 'a;
  tl : 'a inf_list Lazy.t;
}
let hd x = x.hd and tl x = force(x.tl)

let rec primes_from_2 = { hd = 2; tl = lazy(primes_from 3) }

and primes_from n =
  if is_prime n then { hd = n; tl = lazy(primes_from (n+1)) }
  else primes_from (n+1)

and is_prime n =
  let rec iter n x =
    let m = hd x in
    m*m > n || n mod m != 0 && iter n (tl x)
  in
  iter n primes_from_2

コンパイルできるのが不思議なくらいだ。
動作チェックは

let test_print =
  let a = ref primes_from_2 in
  let p = ref(hd !a) in
  while !p < 1000000 do
    Printf.printf "%d\n" !p;
    a := tl !a;
    p := hd !a;
  done

とでも。

追記: 試しにhaskell書いてみた。みじけぇ。。。

primes :: [Integer]
primes = 2 : primes_from 3
  where primes_from n = if prime_test n primes then n : primes_from (n+1)
                        else primes_from (n+1)
        prime_test n (hd:tl) = hd*hd > n || mod n hd /= 0 && prime_test n tl

ただ、ウィソのghciで試した限りでは&&と||を使うより
if then elseを使うほうが断然速いという罠。