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;;