(** Corrigé du TP2 *)

(** Exercice 1 *)

let (_ : float * (string * (int * int))) = (1.5, ("3", (4, 5))) ;;

let (_ : (int*int) * (int*int)) = ((1,2),(3,5));;

let (_ : (int*float) vect) = [|2,3.5;4,5.2;6,7.5|];;

let (_ : char vect * int vect vect) = ([|`a`;`b`|],[|[||];[|1;2;3|]|]);;

(** Exercice 2 *)

let (_ : int*float*string) = 1, 2., "foo";;

let (_ : (int*string)*(float*int)) = ((1,"foo"),(0.,42));;

let (_ : (int*(float*string)) * int) = (1, (0.,"hello")),42;;

let (_ : (int*bool) vect * float) = [| 1, true; 2, false |], 42.;;

(** Exercice 3 *)

let min_triple (a,b,c) =
  if a <= b && a <= c
    then a
  else if b <= a && b <= c
    then b
    else c ;;

min_triple (1,2,3) = 1;;
min_triple (1,22, -3) = -3;;
min_triple (100,22, -3 + 42) = 22;;

let min_triple_bis = function
  | (a,b,c) when a <= b && a <= c -> a
  | (a,b,c) when b <= a && b <= c -> b
  | (_,_,c) -> c;;

(** Exercice 4 *)

(** (a) *)

let f (x,y) = sin x *. cos y;;
let f_curried x y = sin x *. cos y;;

let g (x,y,z) = (x+y) * z;;
let g_curried x y z = (x+y) * z;;

(** (b) *)

let (curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c) =
  fun f x y -> f (x, y);;

let (uncurry : ('a -> 'b -> 'c) -> ('a * 'b) -> 'c) =
  fun f (x,y) -> f x y;;

uncurry f_curried (1., 20.) = f (1., 20.);;
curry f 1. 20. = f_curried 1. 20.;;

(** Exercice 5 *)

let somfct f g x = f x +. g x;;

(* Alternative plus explicite *)
let somfct2 f g = fun x -> f x +. g x;;

let prodfct f g x = f x *. g x;;

let prodfct2 f g = fun x -> f x *. g x;;

let prodext a f x = a *. f x;;

let derive f epsilon x =
  ((f (x +. epsilon) -. f (x -. epsilon)) /. (2. *. epsilon));;

let compose f g x = f (g x);;

(* Ou: *)
let compose2 f g = fun x -> f (g x);;

(** Exercice 6 *)

let rec compose_n f n = match n with
  | 0 -> (fun x -> x)
  | 1 -> f
  | _ -> (fun x -> f (compose_n f (n-1) x));;

compose_n (fun x -> x+1) 0 42 = 42;;
compose_n (fun x -> x+1) 3 39 = 42;;

(* Ou, utilisant le principe "diviser pour régner", aussi appelée dans ce
   cas précis "exponentiation rapide". Terminaison du fait que n, qui
   reste positif, decroit strictement. *)
let rec compose_n2 f n = match n with
  | 0 -> (fun x -> x)
  | 1 -> f
  | _ when n mod 2 = 0 ->
      (* n = 2.n', donc f^n = (f^n') ^ 2 *)
      let f' = compose_n2 f (n/2) in
      compose f' f'
  | _ ->
      (* n = 2.n' + 1, donc f^n = f o (f^n')^2 *)
      let n' = n/2 in
      let f' = compose_n2 f n' in
      compose f (compose f' f')
;;

compose_n2 (fun x -> x+1) 0 42 = 42;;
compose_n2 (fun x -> x+1) 3 39 = 42;;
compose_n2 (fun x -> x+1) 15 0 = 15;;
compose_n2 (fun x -> x+1) 22 0 = 22;;

(** Exercice 7 *)

(* calcule une approximation de l'integrale de f entre a et b,
   via une fonction en escaliers de n tronçons. *)
let integre f a b n =
  if n <= 0 then failwith "n doit etre > 0";
  let s = ref 0. in
  let step = (b -. a) /. float_of_int n in
  for k = 1 to n do
    s := !s +. f (a +. float_of_int k *. step);
  done;
  !s *. step;;

integre (fun x-> x) 0. 4. 100, 8.;;  (* environ 8 *)
integre exp 0. 4. 100, exp 4. -. 1.;;

(** Exercice 8 *)

let abs_int = function
  | n when n >= 0 -> n
  | n -> - n;;

let abs_float x = match x with
  | _ when x >= 0. -> x
  | _ -> -. x;;

(** Exercice 9 *)

(** Produit de deux entiers positifs x et y.
    Precondition: x et y sont >= 0
    terminaison: a chaque appel recursif, y decroit, mais reste positif *)
let rec mult_egypt x y = match y with
  | 0 -> 0
  | 1 -> x
  | _ when y mod 2 = 0 -> mult_egypt (2 * x) (y / 2)
  | _ -> x + mult_egypt x (y - 1);;

mult_egypt 2 10 = 20;;
mult_egypt 2 2 = 4;;
mult_egypt 2 1 = 2;;
mult_egypt 2 0 = 0;;

(** Exercice 10 *)

(** (a) *)

let rec somme n =
  if n <= 0
    then 0
    else n + somme (n-1);;

somme 10 = 55;;

(** (b) *)

(** factorielle de l'argument d'entree, ou 0 s'il est negatif.
    la terminaison se prouve par le fait que n decroit strictement et
    reste positif *)
let rec fact = function
  | n when n <= 0 -> 0
  | 1 -> 1
  | n -> n * fact (n-1);;

(** (c) *)

(** general f n   correspond a l'expression f n (f n-1 (f n-2 .... (f 2 1))).
    La fonction termine car n decroit a chaque appel *)
let rec general f n =
  if n = 1
    then 1
    else f n (general f (n-1));;

general (fun x y -> x+y) 10 = 55;;
general (fun x y -> x*y) 5 = 120;;

general (fun x y -> x*x + y) 10;;

(** Exercice 11 *)

(** (a) *)

(** calcule le nombre de permutations de p elements parmi n.
    la terminaison est prouvée par le fait que n decroit
    strictement dans chaque appel recursif, et reste positif. *)
let rec binomial n p = match p with
  | _ when p > n -> 0   (* impossible *)
  | 0 -> 1
  | 1 -> n
  | _ -> binomial (n-1)(p-1) + binomial (n-1) p;;

binomial 6 4 = fact 6 / (fact 4 * fact (6-4));;

(** (b) *)

(* version iterative de binomial n p *)
let binomial2_iter n p =
  let prod = ref 1 in  (* produit final *)
  let div = ref 1 in   (* diviseur final *)
  let p, n = ref p, ref n in
  while !p > 0 do
    prod := !prod * !n;
    div := !div * !p;
    decr p;
    decr n;
  done;
  (* on divise le produit des n, pour n=n...n-p, par le produit des
     k, k=p...1 *)
  !prod / !div ;;

binomial2_iter 6 4 = binomial 6 4;;
binomial2_iter 12 7 = binomial 12 7;;
binomial2_iter 6 12 = 0;;
binomial2_iter 6 0 = 1;;

(** version récursive de la fonction binomiale.
    precondition: p doit etre >= 1
    terminaison: p decroit a chaque etape *)
let rec binomial2_rec n p = match p with
  | _ when p < 0 -> 0
  | 0 -> 1
  | 1 -> n
  | _ -> (n * (binomial2_rec (n-1) (p-1))) / p;;

binomial2_rec 6 4 = binomial 6 4;;
binomial2_rec 12 7 = binomial 12 7;;
binomial2_rec 6 12 = 0;;
binomial2_rec 6 0 = 1;;

(** (c) *)

(** Précondition: n >= 0; post-condition: retourne le tableau
    [binomial i n] pour i=0...n *)
let pascal n = match n with
  | 0 -> [| |]
  | _ ->
    let a = make_vect (n+1) 0 in
    for i = 0 to n do
      a.(i) <- binomial2_rec n i;
    done;
    a ;;

init_vect 6 pascal ;;   (* tableau de (pascal i) pour i allant de 0 a 5 *)
init_vect 100 pascal ;;   (* tableau de (pascal i) pour i allant de 0 a 5 *)

(** (d) *)

(* On remarque que si on utilise la fonction "binomial" pour definir
   la fonction "pascal", le calcul de "pascal n" devient tres lent quand n
   devient grand. C'est moins evident avec "binomial2_rec" qui est
   plus efficace (car elle fait bien moins d'appels recursifs !) *)

(** Exercice 12 *)

let pi = 3.14159;;
let pi_fois_2 = pi *. 2.;;
let pi_sur_2 = pi /. 2.;;

let square x = x *. x;;

(* retourne une approximation de "cosinus x" en utilisant son développement
   limité au voisinage de [0,epsilon]. Requiert que epsilon soit strictement
   positif. *)
let rec cos_app x epsilon =
  match x with
  | _ when x < 0. -> cos_app (x +. pi_fois_2) epsilon
  | _ when x > pi ->
      (* cos (x + pi) = - (cos x) *)
      -. (cos_app (x -. pi) epsilon)
  | _ when x > pi_sur_2 ->
      (* cos (x + pi/2) = - sin x *)
      -. (sin_app (x -. pi_sur_2) epsilon)
  | _ when x > epsilon ->
      (* cos(2x) = cos(x)^2 - sin(x)^2 *)
      square (cos_app (x/.2.) epsilon) -. square (sin_app (x/.2.) epsilon)
  | _ ->
      (* cas terminal:  cos x ~ 1 - x^2/2 *)
      1. -. (x *. x) /. 2.
(* idem mais pour le sinus *)
and sin_app x epsilon =
  match x with
  | _ when x < 0. -> sin_app (x +. pi_fois_2) epsilon
  | _ when x > pi ->
      (* sin (x + pi) = - (sin x) *)
      -. (sin_app (x -. pi) epsilon)
  | _ when x > pi_sur_2 ->
      (* sin (x + pi/2) = cos x *)
      cos_app (x -. pi_sur_2) epsilon
  | _ when x > epsilon ->
      (* sin(2x) =  2 sin(x)cos(x) *)
      2. *. sin_app (x/.2.) epsilon *. cos_app (x/.2.) epsilon
  | _ ->
      (* cas terminal:  sin x ~ x *)
      x;;

cos_app 1. 1e-4, cos 1.;;
cos_app 2. 1e-4, cos 2.;;
sin_app 1. 1e-4, sin 1.;;
sin_app 2. 1e-4, sin 2.;;

(** Exercice 13 *)

(** (a) *)

let deplace pos =
  let n = !pos in
  let n' = if random__int 2 = 0
    then n+1
    else n-1
  in
  pos := n';
  n' ;;

let retour pos = !pos = 0;;

let marche_aleatoire n =
  let max_right = ref 0 in  (* abscisse max *)
  let num_retour = ref 0 in (* nombre de retours a l'origine *)
  let pos = ref 0 in        (* position *)
  for i = 1 to n do
    let p = deplace pos in
    max_right := max !max_right p;
    if retour pos then incr num_retour;
  done;
  !pos, !max_right, !num_retour;;

marche_aleatoire 200;;
marche_aleatoire 200;;
marche_aleatoire 200;;

(** (b) *)

(* parcourt le plan pendant au plus n pas, s'arrete des qu'on revient
   a l'origine. Précondition: n doit être positif. Postcondition: retourne
   le nombre de pas effectués. *)
let marche_aleatoire_plan n =
  (* deplacement vers un point cardinal *)
  let deplace pos =
    let x,y = !pos in
    match random__int 4 with
    | 0 -> pos := x+1, y  (* Est *)
    | 1 -> pos := x, y+1  (* Nord *)
    | 2 -> pos := x-1, y  (* Ouest *)
    | 3 -> pos := x, y-1  (* Sud *)
    | _ -> failwith "impossible"
  in
  let position = ref (0,0) in   (* position actuelle *)
  let nombre_pas = ref 0 in     (* nombre de pas *)
  (* n-!nombre_pas decroit a chaque fois, donc cette boucle termine.
     La boucle s'arrete si on depasse n pas, ou si on revient
     a l'origine apres avoir fait au moins un pas. *)
  while !nombre_pas < n && (!nombre_pas = 0 || !position <> (0, 0)) do
    deplace position;
    incr nombre_pas;
  done;
  !nombre_pas ;;

marche_aleatoire_plan 1000;;
marche_aleatoire_plan 1000;;
marche_aleatoire_plan 1000;;