datatype 'a stream =
Cons of 'a * (unit -> 'a stream)
fun shd (Cons (x, xs)) = x
fun stl (Cons (x, xs)) = xs ()
fun ones () =
Cons (1, ones)
fun smap f (Cons (x, xs)) =
Cons (f x, fn () => smap f (xs ()))
fun sfilter f (Cons (x, xs)) =
if f x then
Cons (x, fn () => sfilter f (xs ()))
else
sfilter f (xs ())
fun succ n = n + 1
fun nats () =
Cons (0, fn () => smap succ (nats ()))
fun take 0 (Cons (x, xs)) = []
| take n (Cons (x, xs)) = x :: take (n - 1) (xs ())
fun divides m n =
n mod m = 0
fun sieve (Cons (x, xs)) =
Cons (x, fn () =>
sieve (sfilter (not o (divides x)) (xs ())))
val primes =
sieve (stl (stl (nats ())))
(* can you write fact as a val? *)
(* without references and "fun", no recursion? *)
datatype T =
T of (int * int * T) -> (int * int * T)
val fact_aux =
fn (n, r, T f) =>
if n <= 0
then (n, r, T f)
else f (n - 1, n * r, T f)
val fact' =
fn n => #2 (fact_aux (n, 1, T fact_aux))
(* can do recursion without "fun" using references *)
val f = ref (fn x => x + 1)
val fact =
fn x =>
case x
of 0 => 1
| n => n * (!f) (n - 1)
val _ = f := fact
(* woah... hard to know what's expressible! *)