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

photo en cc-by par Jan Ramroth

mardi 18 février 2014, par Pierre

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 *)
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) && (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 ... *)

Télécharger

Dans la même rubrique

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

Recherche

Enseignement

Administration

Autres réalisations (logiciels, etc.)

Café

Divers