(** Corrigé du TP3 *)

(** 1 *)

let rec fib_naive = function
  | 1 -> 1
  | 2 -> 1
  | n -> fib_naive (n-1) + fib_naive (n-2);;

let fib n =
  (* a=fib (i-1), b=fib i. S'arrêter quand i = n *)
  let rec fib_aux a b i n =
    if i = n
      then b
      else fib_aux b (a+b) (i+1) n
  in
  match n with
  | 1 | 2 -> 1
  | _ -> fib_aux 1 1 2 n
;;

map
  (fun i -> fib i = fib_naive i)
  [1;2;3;4;5;6;7;8;9;10;11;20;30];;

(** 2 *)

(* a *)

(* précondition: m,n entiers naturels. *)
let rec ackermann m n = match m, n with
  | 0, _ -> n+1
  | _, 0 -> ackermann (m-1) 1
  | _ -> ackermann (m-1) (ackermann m (n-1));;

(* b *)

let ackermann_row m n =
  init_vect (n+1) (ackermann m);;

(* c *)

ackermann_row 0 4;;
ackermann_row 1 4;;
ackermann_row 2 4;;
ackermann_row 3 4;;
ackermann_row 4 0;;

(* d *)

(* En considérant l'ordre lexicographique sur NxN, on voit qu'à chaque appel
  récursif le couple (m,n) décroit strictement (dans un cas
  m diminue, dans l'autre m reste le même mais n diminue) et reste >= (0,0).
  Cette fonction termine donc. *)

(** 3 *)

(* 3.2 *)

let rec length = function
  | [] -> 0
  | _::l -> 1 + length l;;

length [1;2;3;4] = 4;;
length [] = 0;;

(* 3.3 *)

let rec chercher_multiple n l = match l with
  | [] -> None
  | x :: _ when x mod n = 0 -> Some x
  | _ :: l' -> chercher_multiple n l';;

chercher_multiple 2 [4;5;6] = Some 4;;
chercher_multiple 7 [4;5;6] = None;;
chercher_multiple 3 [1;2;4;5;6;9] = Some 6;;
chercher_multiple 4 [2;16;8;4]= Some 16;;
chercher_multiple 2 [] = None;;

let rec chercher p = function
  | [] -> None
  | x :: _ when p x -> Some x
  | _ :: l' -> chercher p l';;

let chercher_multiple2 n l = chercher (fun x -> x mod n = 0) l;;

chercher_multiple2 2 [4;5;6] = Some 4;;
chercher_multiple2 7 [4;5;6] = None;;
chercher_multiple2 3 [1;2;4;5;6;9] = Some 6;;
chercher_multiple2 4 [2;16;8;4]= Some 16;;
chercher_multiple2 2 [] = None;;

(* 3.4 *)

let rec append l1 l2 = match l1 with
  | [] -> l2
  | x :: l1' -> x :: append l1' l2;;

append [1;2;3] [4;5] = [1;2;3;4;5];;
append [] [] = [];;
append [] [1;2] = [1;2];;
append [1;2] [] = [1;2];;

let rec flatten = function
  | [] -> []
  | x :: l -> append x (flatten l);;

flatten [[1]; [2]; [3]] = [1;2;3];;
flatten [[]; [1;2;3]; [4]; [5;6]] = [1;2;3;4;5;6];;

(* 3.5 *)

let rec associer l x = match l with
  | [] -> None
  | (y,v) :: _ when x = y -> Some v
  | _ :: l' -> associer l' x;;

associer [1, "1"; 2, "2"] 1 = Some "1";;
associer [1, "1"; 2, "2"] 2 = Some "2";;
associer [1, "1"; 2, "2"] 3 = None;;

(* 3.6 *)

let rec compare_list_int l1 l2 = match l1, l2 with
  | [], [] -> false
  | [], _ -> true
  | _, [] -> false
  | x1::l1', x2 :: l2' ->
      x1 < x2 || (x1 = x2 && compare_list_int l1' l2')
;;

compare_list_int [1;2;3] [1;2;3;4] = true;;
compare_list_int [1;2;3;5] [1;2;3;4] = false;;
compare_list_int [5] [1;2;3;4] = false;;

let rec compare_list cmp_elem l1 l2 = match l1, l2 with
  | [], [] -> false
  | [], _ -> true
  | _, [] -> false
  | x1::l1', x2 :: l2' ->
      cmp_elem x1 x2 || (x1 = x2 && compare_list cmp_elem l1' l2')
;;


let smaller x y = x < y ;;

compare_list smaller [1;2;3] [1;2;3;4] = true;;
compare_list smaller [1;2;3;5] [1;2;3;4] = false;;
compare_list smaller [5] [1;2;3;4] = false;;
compare_list smaller ["a"; "b"] ["a"; "b"; "c"] = true;;
compare_list smaller ["a"; "d"] ["a"; "b"; "c"] = false;;