Caml : solution du TD 6

Une solution du TD 6 de Caml (v.15.9)

Projet 1
N.B. le type arbre binaire est simplement nommé arbre ici.
1.
type arbre = Vide | Noeud of int * arbre * arbre;;
N.B. Pour visualiser un arbre, on utilisera ici sa représentation parenthésée :
() pour un arbre vide,
(n,(),()) ou pour simplifier (n) pour un arbre réduit à une feuille,
et plus généralement (n,sad,sad) où sag et sad sont des arbres.
2.
let (v:arbre)=Vide
let f=Noeud(1,Vide,Vide);;
let a=Noeud(2,f,f);;
let s=Noeud(3,Vide,f);;
3.
v, f et a sont saturés.
4.
N.B. Il est important que les fonctions primitives d'un types soient indépendantes les unes des autres.
let estvide (a:arbre) = (a==Vide);;

let estfeuille (a:arbre) = match a with 

   | Vide -> false 

   | Noeud(_,g,d) -> (g<>Vide);;

let etiquette a = match a with Noeud(i,\_,\_) -> i;;
N.B. On aura un avertissement de "match incomplet" et, à l'utilisation, si l'arbre est vide, on aura une Exception: Match_failure.

let sag a = match a with 

   | Vide -> Vide 

   | Noeud(_,g,d) -> g;;

let sad a = match a with 

   | Vide -> Vide 

   | Noeud(_,g,d) -> d;;

N.B. On retourne un arbre vide s'il y a une erreur de paramètre.

let estsature a = match a with 

   | Vide->true 
   | (_,g,d)->(g==Vide)==(d==Vide);;

let rec taille a = 

   if (estvide a) then 0 else (taille (sag a))+(taille (sad s));;

let hauteur a = 

   if (estvide a) then -1 

   else if (estfeuille a) then 0 

   else 1+max(hauteur (sag a), hauteur (sad s));;

N.B. La hauteur d'un arbre réduit à une feuille est par convention 0.

let rec prefixe a = match a with 

   | Vide -> [] 

   | Noeud (e,g,d) -> e::(prefixe g)@(prefixe d);;

let rec postfixe a = match a with 

   | Vide -> [] 
   | Noeud (e,g,d) -> (prefixe g)@(prefixe d)@[e];;

let rec infixe a = match a with 

   | Vide -> [] 

   | Noeud (e,g,d) -> (prefixe g)@(e::(prefixe d));;

let rec feuillage a = match a with 

   | Vide -> [] 

   | Noeud (e,Vide,Vide) -> [e] 

   | Noeud (_,g,d) -> (feuillage g)@(feuillage d);;

let rec lister a = 

   if (estvide a) then "[]" 

   else "[" ^(string_of_int (etiquette a)) ^ ", " ^ (lister (sag a)) ^ 
   ", " ^ (lister (sad a)) ^ " ]";;

En Caml, tous les éléments d'une liste doivent être de même type, on ne peut donc pas créer des arbres sous forme de listes emboitées.
let arborer s = ... → à réaliser en TP

Projet 2. Listes d'entiers
type listedentier = Vide | Noeud of int * Listedentier;;
test (s==[])
let estvide (s:listedentier) = (s==Vide);;
fonction List.hd

let tete (s:listedentier) = match s with 

   | Vide -> failwith "listevide" 

   | Noeud(t,_) -> t;;

fonction List.tl

let queue s = match a with 

   | Vide -> Vide

   | Noeud(_,q) -> q;;

N.B. La fonction queue est robuste.
opérateur ::
let ajouter s e = Noeud(e,s);;
opérateur @

let rec concatener s t = match s with

   | Vide -> t

   | Noeud(t,q) -> Noeud(t,(concatener q t));;

Projet 3. ABR
1.
La principale différence est la contrainte imposée aux étiquettes, la structure de l'arbre sera la même que celle d'un arbre binaire.
(6,(3,( 1),(4)),(3,(0),(2))) respecte (1) mais pas (2).
(6,(3,(-1),(4)),(8,(7),(9))) respecte (1) et (2), c'est un ABR non trivial.
() et (14) sont des ABR triviaux.
2. 3.
type abr = arbre;;
Pour chaque fonction, construire si nécessaire un algorithme.
Après implémentation, les fonctions seront testées sur différents exemples bien choisis.
let rec estABR a = ...
let rec ajouterABR x a = ...
let rec supprimerABR x a = ...
let rec listerABR a = ...
let rec ABRdeliste s = ...
let rec estABR a = ...
etc.

Projet 4. Le monnayeur
A réaliser en TP.