(* Question 1 *)
let rec fibo0 = function
| 0 -> 0
| 1 -> 1
| n -> fibo0 (n-1) + fibo0 (n-2)
;;
let rec iter n f x =
if n = 0 then x
else iter (n-1) f (f x)
;;
let fibo1 n =
let rec couple_suivant (a, b) = (b, a+b) in
fst (iter n couple_suivant (0, 1))
;;
(* Question 2 *)
let rec rev_append l1 l2 = match l1 with
| [] -> l2
| h :: t -> rev_append t (h :: l2)
;;
let rev l = rev_append l []
;;
(* Question 3 *)
let rec map1 f = function
| [] -> []
| h :: t -> f h :: map1 f t
;;
(* Question 4 *)
let rec filter p = function
| [] -> []
| h :: t when p h -> h :: filter p t
| _ :: t -> filter p t
;;
(* Question 5 *)
let rec fold_left f a = function
| [] -> a
| h :: t -> fold_left f (f h) t
;;
(* Question 6 *)
let rec flatten = function
| [] -> []
| h :: t -> h @ (flatten t)
;;
(* Question 7 *)
let fibogen f0 f1 op n =
let rec couple_suivant (a, b) = (b, op a b) in
fst (iter n couple_suivant (f0, f1))
;;
(* Question 9 *)
let rec nb_occ e = function
| [] -> 0
| h :: t when h = e -> 1 + (nb_occ e t)
| _ :: t -> nb_occ e t
;;
(* Question 10 *)
let rec jette n l =
if n = 0 then l
else match l with
| [] -> invalid_arg "jette"
| _ :: t -> jette (n-1) t
;;
let tronque n l = rev (jette n (rev l))
;;
(* Question 11 *)
let rec remplace x lx = function
| [] -> []
| h :: t when h = x -> lx @ (remplace x lx t)
| h :: t -> h :: remplace x lx t
;;
(* Question 12 *)
let exp =
let rec exp a b = function
| 0 -> a
| n when n mod 2 = 0 -> exp a (b * b) (n/2)
| n -> exp (a * b) (b * b) (n/2)
in
exp 1
;;
(* Question 13 *)
type op = S | M
;;
let decompose =
let rec decompose acc = function
| 0 -> acc
| n when n mod 2 = 0 -> decompose (S :: acc) (n/2)
| n -> decompose (S :: M :: acc) (n/2)
in
decompose []
;;
let recompose =
let rec recompose acc = function
| [] -> acc
| S :: t -> recompose (acc * 2) t
| M :: t -> recompose (acc + 1) t
in
recompose 0
;;
(* Question 14 *)
let ecoute =
let rec ecoute egal = function
| [] -> []
| S :: t -> egal :: ecoute true t
| M :: t -> false :: ecoute false t
in
ecoute false
;;
let rec retrouve = function
| [] -> []
| [true] -> [S]
| [false] -> [S]
| _ :: true :: t -> S :: retrouve (true :: t)
| _ :: false :: t -> S :: M :: retrouve t
;;
(* Vérification *)
let id x = recompose (retrouve (ecoute (decompose x)))
;;
map1 id [0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20;21]
;;
