(* 1 Premier jour : noyau fonctionnel *)
(* 1.1 Recurrence numerique *)

(* Exercice 1.1 *)

(* Version naive : 
   on suppose que l'exposant est un entier positif *)
let rec slow_exp b n =
  if n = 0 then 
    1
  else
    b * (slow_exp b (n-1))

(* Version defensive :
   on verifie que l'exposant est un entier positif *)
let slow_exp b n =
  (* on suppose ici que n est correct,
     notez que `b' n'est pas argument de `loop' *)
  let rec loop n = 
    if n = 0 then 
      1
    else
      b * (loop (n-1))
  in
    if n < 0 then
      failwith "slow_exp; invalid argument"
    else
      loop n

(* alternative *)
let slow_exp b n =
  if n < 0 then
    failwith "slow_exp; invalid argument"
  else (
    let rec loop n = 
      if n = 0 then 
	1
      else
	b * (loop (n-1))
    in
      loop n 
  )

(* Version recursive terminale:
   la fonction auxiliaire est locale, en fait, elle peut se passer de `b' *)
let slow_exp b n =
  let rec slow_exp_loop n a =
    if n = 0 then
      a
    else
      slow_exp_loop (n-1) (b*a)
  in
    if n < 0 then
      failwith "slow_exp; invalid argument"
    else
      slow_exp_loop n 1
    
(* Exercice 1.2 *)

let even n = 
  (n mod 2) = 0

let fast_exp b n =
  let rec loop n =
    if n = 0 then
      1
    else if even n then
      let b' = loop (n/2) in
	b' * b'
    else
      b * (loop (n-1))
  in
    if n < 0 then
      failwith "fast_exp; invalid argument"
    else
      loop n 
    
(* Exercice 1.3 *)

let rec gcd n m =
  if m = 0 then
    n
  else
    gcd m (n mod m)


(* Exercice 1.4 *)

type rat = { num : int ; den : int }

let rat_reduce r =
  let a = gcd r.num r.den in
    { num = r.num / a; den = r.den / a }

let rat_plus r1 r2 =
  let n1, d1 = r1.num, r1.den in
  let n2, d2 = r2.num, r2.den in
    {
      num = (d2 * n1) + (d1 * n2);
      den = d1 * d2
    }

let rat_mul r1 r2 =
  {
    num = r1.num * r2.num;
    den = r1.den * r2.den
  }

let rat_equal r1 r2 =
  let r1' = rat_reduce r1 
  and r2' = rat_reduce r2 in
    (r1'.num = r2'.num) && (r1'.den = r2'.den)
  

(* Exercice 1.6 *)

let rec gen_rec d f a n =
  if n <= 0 then 
    a
  else
    f n (gen_rec d f a (d n))

let phi n r =
  if even n then
    r * r
  else
    2 * r

let delta n =
  if even n then
    n / 2
  else
    n - 1

let puiss2 n = 
  gen_rec delta phi 1 n 

let fast_exp e n =
  let phi n r =
    if even n then
      r * r
    else
      e * r
  in  
    gen_rec delta phi 1 n

(* Exercice 1.7 *)

let rec supprime xs n =
  if n = 0 then xs
  else if n < 0 then raise (Invalid_argument "supprime")
  else (
    match xs with
	[] -> raise (Invalid_argument "supprime")
      | _::xs -> supprime xs (n-1) 
  )

let prefixe xs =
  match xs with
      [] -> 0
    | [_] -> 0
    | x::xs -> (
	let rec loop xs =
	  match xs with
	      [] -> 0
	    | x'::xs -> if x=x' then succ (loop xs) else 0
	in
	  match loop xs with
	      0 -> 0
	    | n -> succ n
      )

(* Exercice 1.8 *)

type univ =
    Et of string * int
  | Ad of string * char
  | Ec of string * int

let separe ms =
  let rec loop ms (ets, ads, ecs) =
    match ms with
	[] -> (ets, ads, ecs)
      | (Et (n,i))::ms -> loop ms ((Et (n,i))::ets, ads, ecs)
      | (Ad (n,c))::ms -> loop ms (ets, (Ad (n,c))::ads, ecs)
      | (Ec (n,i))::ms -> loop ms (ets, ads, (Ec (n,i))::ecs)
  in
    loop ms ([], [], [])

(* variante *)
let separe ms = 
  let rec loop ms (ets, ads, ecs) =
    match ms with
	[] -> (ets, ads, ecs)
      | m::ms -> (
	  match m with
	      Et _ -> loop ms (m::ets, ads, ecs)
	    | Ad _ -> loop ms (ets, m::ads, ecs)
	    | Ec _ -> loop ms (ets, ads, m::ecs)
	)
  in
    loop ms ([], [], [])

(* Exercice 1.9 *)

type piece = Pile | Face

let rec alea1 ps =
  match ps with
      Pile::Face::ps -> true::(alea1 ps)
    | Face::pile::ps -> false::(alea1 ps)
    | _::_::ps -> (alea1 ps)
    | _ -> []

let rec reste_alea1 ps =
  match ps with
      Pile::Pile::ps -> Pile::(reste_alea1 ps)
    | Face::Face::ps -> Face::(reste_alea1 ps)
    | _::_::ps -> (reste_alea1 ps)
    | _ -> []

(* alternative, avec filtrage garde *)
let rec reste_alea1 ps =
  match ps with
      p1::p2::ps when p1=p2 -> p1::(reste_alea1 ps)
    | _::_::ps -> (reste_alea1 ps)
    | _ -> []

let rec alea ps =
  match ps with
      [] -> []
    | _ -> (alea1 ps)@(alea (reste_alea1 ps))

(* Exercice 1.10 *)