let f1 x = x + 1;; let rec f2 x = f2 (x+1);; Lst.hd (f1 5::f2 5);; List.hd (f1 5::f2 5);; (*Lazy Lists 1st try*) type 'a llist = Nil | Cons of 'a * (unit -> 'a llist);; let hd = function | Nil -> failwith "empty_list" | Cons (x,_) -> x ;; hd Nil;; hd (Cons(1, fun () -> Nil));; let rec from n = Cons(n, fun () -> from (n+1));; from 0;; hd (from 0);; let tl = function | Nil -> failwith "empty_list" | Cons (_,xs) -> xs ();; hd (tl (from 0));; hd (tl (tl (from 0)));; hd (tl (tl (tl (from 0))));; let rec to_list n xs = if n <= 0 then [] else match xs with | Nil -> [] | Cons(x,xs) -> x::(to_list (n-1) (xs ()));; to_list 5 (from 0);; to_list 5 (from 1000);; to_list 1000 (from 0);; (*Lazy Lists 3rd try*) (*this is what we want; interpreter does not allow*) type 'a llist = (unit -> Nil) | (unit -> Cons of 'a * 'a llist);; (*this is how we can make interpreter happy*) type 'a cell = Nil | Cons of 'a * 'a llist and 'a llist = unit -> 'a cell;; let rec from n = fun () -> Cons(n, from (n+1));; let rec to_list n xs = if n <= 0 then [] else match xs () with | Nil -> [] | Cons(x,xs) -> x::to_list (n-1) xs;; to_list 5 (from 0);; to_list 1000 (from 0);; let hd xs = match xs () with | Nil -> failwith "empty_list" | Cons(x,_) -> x;; hd (from 0);; let tl xs = match xs () with | Nil -> failwith "empty_list" | Cons(_,xs) -> xs;; hd (tl(from 0));; 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) ;; let rec fibs = fun () -> Cons(0,fun () -> Cons(1, zip_with (+) fibs (tl fibs)));; (*because zip_with blocks too late *) to_list 10 fibs;; (*solution: block evaluation as early as possible *) let rec zip_with f xs ys = fun () -> match (xs (),ys ()) with | Cons(x,xs),Cons(y,ys) -> Cons(f x y,zip_with f xs ys) ;; let rec fibs = fun () -> Cons(0,fun () -> Cons(1, zip_with (+) fibs (tl fibs)));; to_list 10 fibs;; (*because of lack of memoization this is slow*) to_list 30 fibs;; (*internal support for Lazyness*) print_string "1";; lazy (print_string "1");; let e1 = lazy (print_string "1");; Lazy.force e1;; let e2 = lazy (let rec f () = print_int 1; f () in f ());; Lazy.force e2;; open LazyList;; primes;; to_list 100 primes;; to_list 1000 primes;; List.nth (to_list 1000 primes) 999;; to_list 1000000 primes;; open LazyList;; fibs;; (*because of memoization this is fast*) List.nth (to_list 100 fibs) 99;;