let rec f x = if x = 0 then x else f x;; f 0;; f 1;; Lst.hd (f 0 :: f 1 :: []);; let rec from n = n::from (n+1);; Lst.hd (from 0);; type 'a llist = Nil | Cons of ('a * (unit -> 'a llist));; let hd = function | Nil -> failwith "empty list" | Cons(x,_) -> x;; let tl = function | Nil -> failwith "empty list" | Cons(_,xs) -> xs ();; let rec from n = Cons(n,fun () -> from (n+1));; from 0;; Lst.hd (from 0);; hd (from 0);; hd (tl (from 0));; from 0;; let rec to_list n xs = if n < 1 then [] else match xs with | Nil -> [] | Cons(x,xs) -> x::(to_list (n-1) (xs ()));; to_list 10 (from 0);; to_list 100 (from 0);; to_list 1000 (from 0);; type 'a cell = Nil | Cons of ('a * 'a llist) and 'a llist = (unit -> 'a cell);; let rec tl xs = match xs () with | Nil -> failwith "empty" | Cons(x,xs) -> xs;; (*this version of zip_with is not 100% lazy since the match is evaluated immediately*) let rec zip_with f xs ys = match (xs (), ys ()) with | (Cons (x,xs), Cons (y,ys)) -> fun () -> Cons(f x y,zip_with f xs ys) | _ -> fun () -> Nil;; let rec fibs = fun () -> Cons(0,fun () -> Cons(1,zip_with (+) fibs (tl fibs)));; (*does not terminate due to "wrong" implementation of zip_with*) to_list 10 fibs;; open UnitList;; (*does terminate, due to to correct, i.e., lazy implementation of zip_with*) to_list 10 fibs;; to_list 3 fibs;; (*slow, due to exponentially many recursive calls (no memoization)*) to_list 100 fibs;; open LazyList;; to_list 100 primes;; to_list 1000 primes;; to_list 10000 primes;;