Semaine 4 – récursion terminale (tail recursion), persistance, plus de syntaxe

(* 1) Nouvelles formes syntaxiques *)
 
(* forme favorite *)
let cube = function x -> x*x*x;;
(* autre forme (rappel) *)
let cube x = x * x * x;;
(* rappel sur let ... in ... et and *)
let x = 2;;
let z =
  let x = 4
  and y = x - 1
  in x + y
;;
z;;
y;;
 
(* let in pour une fonction "interne" *)
let cube x =
  let carre_inner n = n * n
  in
  (carre_inner x) * x;;
 
cube 3;;
cube;;
carre_inner;;
 
 
type parite =
    Impair | Pair;;
 
(* recursion mutuelle *)
let rec
    choux = function
  | 0 -> Pair
  | 1 -> Impair
  | n -> fleur (n - 1)
  and
  fleur = function
  | 0 -> Impair
  | 1 -> Pair
  | n -> choux (n - 1);;
choux 1;;
choux 2;;
fleur 451;;
 
 
(* pattern matching match with *)
 
type truc = Bidule | Machin | Chose of int | Truc of int;;
 
Chose 4;;
 
let identite = function
    x ->
(function
      | Chose n -> n
      | Truc _ -> 0
      | Machin -> 2
      | Bidule -> -1) (Chose x) ;;
 
(* l'expression suivante : *)
(function | m1 -> e1
 | m2 -> e2 | ...) e;;
 
(* s'écrit plus simplement : *)
match e with
| m1 -> e1
| m2 -> e2
...;;
 
let identite = function
    x -> match Chose x
         with
         | Chose n -> n
         | Truc _ -> 0
         | Machin -> 2
         | Bidule -> -1
;;
identite 56;;
 
(* cube avec une valeur speciale en zero *)
let zcube z = function
  | 0 -> z
  | n -> n * n * n;;
zcube (-12) 0;;
zcube 0 (-12);;
 
(* arguments dans l'autre ordre avec match *)
let zcube x z = match x
  with
  | 0 -> z
  | n -> n * n * n;;
zcube 0 (-12);;
zcube (-12) 0;;
 
(* gardes de motifs avec when *)
let abscube = function
  | 0 -> z
  | n when n < 0 -> -n * n * n
  | n  -> n * n * n;;
;;
 
(* rappel du type d'exemple *)
type truc = Bidule | Machin | Chose of int | Truc of int ;;
 
(* regroupement de cas *)
let f = function
  | Bidule -> 1
  | Chose n -> n
  | Truc _
  | Machin -> e
;;
 
let f = function
  | Bidule
  | Machin -> 0
  | Chose n
  | Truc n -> n
;;
 
let f = function
  | Chose _ (* <- n ne passerait pas *)
  | Bidule
  | Machin -> 0
  | Truc n -> n
;;
 
let f = function
  | Bidule
  | Machin -> 0
  | Chose n
  | Truc n when  n > 0 -> n
  | Chose n
  | Truc n -> 1
;;
 
f (Chose (-10));;
 
(* alias avec as *)
let f = function
  | Bidule
  | Machin as b -> (b, 0)
  | Chose n
  | Truc n as b -> (b, n)
;;
 
 
(* Bonne pratique: eviter les catch all _ *)
let f = function
      | Chose n -> n
      | Truc _ -> 0
      | _ -> 42 (* mauvaise pratique *)
;;
(* etendre le type truc ne levera pas de warning ici *)
(* preferer le regroupement des cas restants au _ *)
 
let f = function
      | Chose n -> n
      | Truc _ -> 0
      | Bidule | Machin _ -> 42 (* mieux *)
;;
 
(* Gestion memoire *)
let rec concatenation s t =
match s with
| [] -> t
| x::xs -> x::(concatenation xs t);;
 
(* persistance  (au tableau) *)
 
(* recursion terminale / Tail Recursion (au tableau) *)
 
(* avec une fonction de portée local *)
 
(* Mise sous forme recursive terminale (pas toujours possible) *)
 
(* la fonction longueur suivante n'est pas TR *)
 
let rec longueur l = match l with
  | [] -> 0
  | x::xs -> 1 + longueur xs;;
 
(* on peut la réecrire ainsi : *)
let rec longueur_tr l acc =
  print_int acc;
  match l with
  | [] -> acc
  | x::xs -> longueur_tr xs (acc + 1);;
(* cette fonction est TR *)
(*Exemple de réductions  successives *)
longueur_tr [10;20;30] 0;;
longueur_tr [20;30] 1;;
longueur_tr [30] 2;;
longueur_tr [] 3;;
3;;
 
(* internaliser cette version tail recursive *)
let longueur l =
  let rec longueur_tr l acc
    = match l with
    | [] -> acc
    | x::xs ->
       longueur_tr xs (acc + 1)
  in
  longueur_tr l 0
;;
(* ainsi on utilise simplement la fonction longueur a un argument *)
 
(* factorielle en version TR ? *)
let factorielle n =
  let rec facttr n r =
    print_string "facttr ";
    print_int n;
    print_string " ";
    print_int r;
    print_string "\n";
    match n with
    |0-> r
    |n -> facttr (n-1) (r*n)
  in facttr n 1;;
  factorielle 5;;
 
(* liste_aleatoire en TR *)
open Random;;
 
let rec lia n = match n with
  | 0 -> []
  | n -> (Random.int 100000)::(lia (n - 1));;
lia 300000;;
 
let lia n =
  let rec tr n l = match n with
    | 0 -> l
    | n -> tr (n - 1) ((Random.int 10000000)::l)
  in
  tr n []
;;
lia 3000000;;
 
(* est_croissante l retourne vrai ou faux *)
(* selon si la liste est croissante *)
let rec est_croissante = function
  | [] -> true
  | x::[] -> true
  | x::y::l -> (x <= y) &amp;&amp; (est_croissante (y::l));;
 
est_croissante [1;2;3;4;5];;
est_croissante [1;2;3;4;2;5];;
(* TODO a mettre sous forme récursive terminale ... *)