(******************************************************************************)
(* 1. Paresse *****************************************************************)
(******************************************************************************)

(* 1.1. Mise en jambes ********************************************************)

let fibo fibo' n =
  if n <= 1 then n
  else (fibo' (n-1)) + (fibo' (n-2));;


(* Qestions 2., 3. *)

let rec recursive f n =
  f (recursive f) n;;

(recursive fibo) 10;;


(* Questions 4., 5. *)

let rec recursive f =
  f (recursive f);;

(recursive fibo) 10;;

(* Question 6. *)

let fibo fibo' n =
  if n <= 1 then n
  else ((Lazy.force fibo') (n-1)) + ((Lazy.force fibo') (n-2));;

let rec recursive f =
  f (lazy (recursive f));;

(recursive fibo) 10;;



(* 1.2. Mémoizons z'un brin ***************************************************)

(* 1.2.1. Fibonacci, encore et toujours ***************************************)

let fibo fibo' n =
  print_string ("Calling fibo "^(string_of_int n)^"...\n") ;
  if n <= 1 then n
  else (fibo' (n-1)) + (fibo' (n-2));;

let rec recursive f n = 
  f (recursive f) n;;

(recursive fibo) 10;;


(* Question 2., 3. *)

let memoize f =
  let t = Hashtbl.create 10 in
  let rec f' x =
    try Hashtbl.find t x
    with
      | Not_found ->
	  let r = f f' x in
	    Hashtbl.add t x r ; r
  in f';;

(memoize fibo) 10;;


(* 1.2.2. Nombres premiers ****************************************************)

(* Question 4. *)

let is_prime n =
  print_string ("Calling is_prime "^(string_of_int n)^"...\n");
  let rec test n d =
    if d*d > n then true
    else if n mod d = 0 then false
    else test n (d+1)
  in test n 2;;

(* Question 5. *)

let is_prime =
  let t = Hashtbl.create 100 in
  let aux n =
    try
      Hashtbl.find t n
    with
      | Not_found ->
	  let p = is_prime n in Hashtbl.add t n p ; p
  in aux;;
    
is_prime 2;;
is_prime 17;;
is_prime 35;;
is_prime 17;;



(* 1.3. La fabuleuse fonction de Wilhelm Ackermann ****************************)

(* Question 1. *)

let rec ack m n =
  match m,n with
    | 0,_ -> n+1
    | _,0 -> ack (m-1) 1
    | _,_ -> ack (m-1) (ack m (n-1));;

ack 3 10;;
ack 4 1;;


(* Question 2. *)

let ack m n =
  let t = Hashtbl.create 10 in
  let rec aux m n =
    try
      Hashtbl.find t (m,n)
    with
      | Not_found ->
	  let r = match m,n with
	    | 0,_ -> n+1
	    | _,0 -> aux (m-1) 1
	    | _,_ -> aux (m-1) (aux m (n-1))
	  in Hashtbl.add t (m,n) r ; r
  in aux m n;;

ack 3 10;;
ack 4 1;;



(******************************************************************************)
(* 2. Flots paresseux *********************************************************)
(******************************************************************************)

(* 2.1. Des listes infinies ? et pourquoi pas des objets récursifs ?! *********)

let rec l = 0::l;;

type 'a stream = Nil | Cons of 'a * ('a stream Lazy.t);;

let rec l = Cons (0, lazy l);;

(* 2.2. Fonctions de base *****************************************************)

let rec stream_of_list = function
  | [] -> Nil
  | x::q -> Cons (x, lazy (stream_of_list q));;

stream_of_list [1; 6; 6; 4];;


(* Question 1. *)

exception EndOfStream;;

let hd = function
  | Nil -> raise EndOfStream
  | Cons (x,q) -> x;;


(* Question 2. *)

let tl = function
  | Nil -> raise EndOfStream
  | Cons (x,q) -> Lazy.force q;;


(* Question 3. *)

let iter f s =
  let rec aux n s =
    if n > 0 then
      try
	f (hd s) ; aux (n-1) (tl s)
      with
	| EndOfStream -> ()
    else
      failwith "Stream is too long."
  in aux 100 s;;

let print_istream = iter (fun x -> print_int x; print_string ", ");;
print_istream (stream_of_list [1; 6; 6; 4]);;


(* Question 4. *)

let stream_of_fun f =
  let rec aux n f = match (f n) with
    | None -> Nil
    | Some x -> Cons (x, lazy (aux (n+1) f))
  in aux 0 f;;

let nat = stream_of_fun (fun n -> Some n);;
print_istream nat;;


(* 2.3. Transformation, filtrage **********************************************)

(* Question 1. *)

let rec map f = function
  | Nil -> Nil
  | Cons (x,q) -> Cons (f x, lazy (map f (Lazy.force q)));;

print_istream (map (fun x -> x*x) nat);;


(* Question 2. *)

let rec filter p = function
  | Nil -> Nil
  | Cons (x,q) ->
      if p x then Cons (x, lazy (filter p (Lazy.force q)))
      else (filter p (Lazy.force q));;

print_istream (filter (fun x -> x mod 2 = 0) nat);;


(* Question 3. *)

let rec sieve = function
  | Nil -> Nil
  | Cons (x,q) -> Cons (x, lazy (sieve (filter (fun y -> y mod x <> 0) (Lazy.force q))));;

let primes = sieve (stream_of_fun (fun n -> Some (n+2)));;
print_istream primes;;


(* 2.4. Quick sort ************************************************************)

(* Question 1. *)

let rec append s1 s2 = match s1 with
  | Nil -> s2
  | Cons (x,q) -> Cons(x, lazy (append (Lazy.force q) s2));;

print_istream (append (stream_of_list [1; 6; 6; 4]) primes);;


(* Question 2. *)

let rec quick_sort = function
  | Nil -> Nil
  | Cons (x,q) ->
      append
	(quick_sort (filter (fun y -> y <= x) (Lazy.force q)))
	(Cons (x, lazy (quick_sort (filter (fun y -> y > x) (Lazy.force q)))));;

print_istream (quick_sort (stream_of_list [9; 6; 2; 1; 7; 3; 4; 6; 8]));;


(* 2.5. Lecture d'un fichier **************************************************)

let stream_of_file filename =
  let f = open_in filename in
    stream_of_fun (fun _ -> try Some (input_char f) with End_of_file -> None);;

let f = stream_of_file "../td_03/td_03.ml";;
iter print_char f;;

(* Question 1. *)

let rec to_lines = function
  | Nil -> Nil
  | Cons (x,q) ->
      if x = '\n' then
	Cons ("", lazy (to_lines (Lazy.force q)))
      else
	match (to_lines (Lazy.force q)) with
	  | Nil -> Cons (String.make 1 x, lazy Nil)
	  | Cons (s,q) -> Cons ((String.make 1 x)^s, q);;

iter (fun s -> print_string s; print_newline ()) (to_lines f);;


(******************************************************************************)
(* 3. Commencement des continuations ******************************************)
(******************************************************************************)

(* Question 1. *)

let is_prime n k =
  let rec test n d =
    if d*d > n then true
    else if n mod d = 0 then false
    else test n (d+1)
  in k (test n 2);;

let rec prod_prime n k =
  if n <= 2 then k 2
  else prod_prime (n-1) (fun p -> is_prime n (fun b -> k (if b then n*p else p)));;

prod_prime 10 print_int;;