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

photo en cc-by par Jan Ramroth
, par
Récursion terminale / tail recursion (pour éviter les débordements de pile / stock overflow). Du sucre syntaxique pour la correspondance de motifs (match with, gardes de motifs, regroupement de motifs, alias). Quelques explications sur la façon dont ocaml gère la mémoire pour nous : en particulier sur la représentation mémoire des types de données immuables, comme les listes, donnant un avant-goût de la persistance et le ramassage automatique des miettes (garbage collecting).
Il est temps de donner un lien vers un bon support de cours, pour vous permettre de compléter vos notes de cours par un texte de référence.
Le support de cours de Jean-Christophe Filliâtre est un texte que vous pouvez étudier en entier par vous même en complément de mon cours. Avec l’aimable accord de son auteur voici un lien vers son cours d’initiation à la programmation fonctionnelle (choisir le pdf) https://www.lri.fr/~filliatr/m1/cours-ocaml.en.html
Certaines parties de cours de la semaine 4 ont été faites au tableau.
La mise en évidence du l’optimisation par gcc des appels récursifs terminaux en langage C, ayant partiellement échouée cellé-ci attendra de plus amples explications lors d’un prochain cours.
- (* 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 *)
- 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 *)
- (* 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_int n;
- print_int r;
- match n with
- |0-> r
- |n -> facttr (n-1) (r*n)
- in facttr n 1;;
- factorielle 5;;
- (* liste_aleatoire en TR *)
- let rec lia n = match n with
- | 0 -> []
- lia 300000;;
- let lia n =
- let rec tr n l = match n with
- | 0 -> 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) && (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 ... *)