type ... = qui définit un type
concret.
type liste = Liste_vide | Cons of int * liste ;;
let n = Liste_vide;;
let x = Cons (3, Cons (5, Cons (7, n)));;
let rec longueur x = match x with
Liste_vide -> 0
| Cons (_, y) -> 1 + longueur y;;
Un arbre binaire est la généralistion binaire d'une liste. C'est soit
un arbre vide, soit un noeud avec une information associée et deux
sous-arbres (de gauche et de droite).
type arbre = Arbre_vide | Noeud of arbre * int * arbre ;;
let n = Arbre_vide;;
let a = Noeud (Noeud(n, 4, Noeud (n, 5, n)), 6,
Noeud (n, 7, n)) ;;
let rec hauteur a = match a with
Arbre_vide -> 0
| Noeud (a, _, b) ->
1 + max (hauteur a, hauteur b) ;;
Calculez son nombre de noeuds ou de feuilles. Remarquer que dans un
arbre binaire de n feuilles, il y a n-1 noeuds internes.
Les types concrets sont définis par
type t = C_1 of e_1 * ... * e_n | ...
| C_m of e'_1 * ... * e'_n' ;;
type t = { l1: e_1; ... ln: e_n} ;;
où e_1, ... e_n sont des expressions de type. Les
constructeurs commencent par une majuscule; ils définissent des motifs
de filtrage (patterns):
C_1(motif_1, ... motif_n)
C_m(motif_1, ... motif_n')
{ l1: motif_1; ... ln: motif_n}
Dans le cas des motifs de records, on peut sauter qques champs.
On peut paramétrer un type concret polymorphe en précédent
l'identificateur défini par une suite de variables de type.
type 'a arbre = Arbre_vide
| Noeud of 'a arbre * 'a * 'a arbre ;;
Un constructeur peut être 0-aire:
type couleur = Bleu | Blanc | Rouge ;;Attention: les constructeurs ne peuvent être à cheval sur 2 types.
La construction type ... == définit les types abbréviations.
type element == int ;; type couleur == int ;; type fonction_booleenne == bool -> bool ;; type 'a ident == 'a -> 'a;;Ces types peuvent servir pour définir d'autre types concrets, ou pour forcer le type d'une expression
(e: t).
Une expression de type est toute expression fabriquée à partir des
types élémentaires et des types définis (concrets ou non) par
application des foncteurs -> ou *.
Dans les interfaces de modules, cela permet de cacher la
représentation d'un type (voir plus tard).
On peut organiser une table en un arbre de recherche. Si les clés sont des entiers voici l'ajout d'une clé dans un arbre de recherche (cf ch4 du poly):
let rec recherche x a =
match a with
| Arbre_vide -> Arbre_vide
| Noeud (g, y, d) ->
if x = y then a else
if x < y then recherche x g
else recherche x d;;
let rec ajouter x a =
match a with
Arbre_vide -> Noeud (Arbre_vide, x, Arbre_vide)
| Noeud (g, y, d) ->
if x < y then
Noeud (ajouter x g, y, d)
else
Noeud (g, y, ajouter x d);;
On peut aussi représenter un arbre en mettant un record à chaque champ
type 'a arbre = Arbre_vide | Noeud of 'a noeud
and 'a noeud =
{contenu : 'a; filsG : 'a arbre; filsD : 'a arbre};;
Alors la recherche et l'insertion deviennent:
let rec recherche x a =
match a with
| Arbre_vide -> Arbre_vide
| Noeud
{contenu = y; filsG = g; filsD = d} ->
if x = y then a else
if x < y then recherche x g
else recherche x d;;
let rec ajouter x a = match a with
Arbre_vide -> Noeud {contenu = x;
filsG = Arbre_vide;
filsD = Arbre_vide}
| Noeud
{contenu = y; filsG = g; filsD = d} ->
if x <= y
then Noeud {contenu = y;
filsG = ajouter x g; filsD = d}
else Noeud {contenu = y;
filsG = g; filsD = ajouter x d} ;;
Si les arbres sont N-aires, on peut associer à chaque noeud la liste
de tous ses fils.
Si on ne croit pas beaucoup au garbage collector et à la gestion automatique de la mémoire, on peut aussi faire des listes modifiables (comme en C ou Pascal):
type 'a arbre = Arbre_vide | Noeud of 'a noeud
and 'a noeud =
{contenu : 'a; mutable filsG : 'a arbre; mutable filsD : 'a arbre};;
Alors l'insertion devient:
let rec ajouter x a = match a with
Arbre_vide -> Noeud {contenu = x;
filsG = Arbre_vide;
filsD = Arbre_vide}
| Noeud
({contenu = y; filsG = g; filsD = d} as b) -> begin
if x <= y
then b.filsG <- ajouter x g
else b.filsD <- ajouter x d;
a
end;;
Remarque: on aurait pu aussi écrire (dans Caml-light 0.72)
then g <- ajouter x g
else d <- ajouter x d;
A rotG B
/ \ --> / \
a B A c
/ \ <-- / \
b c rotD a b
let rotG = function
Arbre_vide -> failwith "rotG"
| Noeud ({balance = bA; contenu = v;
filsG = c; filsD = B} as nA) as A ->
match B with
| Arbre_vide -> failwith "rotG"
| Noeud ({balance = bB; contenu = v;
filsG = a; filsD = b} as nB) ->
nA.filsD <- a;
nB.filsG <- A;
let bAnew = bA - 1 - max 0 bB in
let bBnew = bB - 1 + min 0 bAnew in
nA.balance <- bAnew;
nB.balance <- bBnew;
B;;
let rec ajouter x a =
match a with
Arbre_vide -> (+1, Noeud (Arbre_vide, x, Arbre_vide, 0))
| Noeud (g, y, d, b) ->
let (incr, a) =
if x < y then
let (ig, a) = ajouter x g in (-ig, a)
else
ajouter x d
in
let bal = b + incr in
if incr <> 0 && bal <> 0 then
if bal < -1 then
(* La gauche est trop grande *)
let Noeud(_,_,_,b) = g in
if b < 0 then
(incr, rotD (Noeud (g, y, d, bal)))
else
(incr, rotD (Noeud (rotG (g), y, d, bal)))
else
(* La droite est trop grande *)
let Noeud(_,_,_,b) = d in
if b > 0 then
(incr, rotG (Noeud (g, y, d, bal)))
else
(incr, rotG (Noeud (g, y, rotD (g), bal)))
;;
let rotG = function
Noeud (a, A, Noeud (b, B, c, bB), bA) ->
let bAnew = bA - 1 - max (0, bB) in
let bBnew = bB - 1 + min (0, bAnew) in
Noeud (Noeud (a, A, b, bAnew), B, c, bBnew)
On représente (5+2*3) * (10*10 + 9*9) par
type terme = Const of int
| Add of terme * terme
| Mult of terme * terme
| Div of terme * terme
| Soust of terme * terme
| Sinus of terme
| Cosinus of terme
| Log of terme
| Exp of terme ;;
let t = Mult (Add (Const(5), Mult (Const(2), Const(3))),
Add (Mult(Const(10), Const(10)),
Mult(Const(9), Const(9)))) ;;
On peut supposer aussi qu'on a des variables dont le nom est un
caractère:
type terme = ...
| Var of char
Pour imprimer un terme, on peut le faire en forme
(5 + 2 * 3) + (10 * 10 + 9 * 9)
5 2 3 * + 10 10 * 9 9 * + *
* + 5 * 2 3 + * 10 10 * 9 9
#open "printf";; let rec print2 t = match t with | Const (x) -> printf "%f " x | Add (t1, t2) -> begin print2 t1 ; print2 t2; printf "+ " end | Mult (t1, t2) -> begin print2 t1 ; print2 t2; printf "* " end | Div (t1, t2) -> begin print2 t1 ; print2 t2; printf "/ " end | Soust (t1, t2) -> begin print2 t1 ; print2 t2; printf "- " end | Sinus (t1) -> begin print2 t1 ; printf "sin " end | Cosinus (t1) -> begin print2 t1 ; printf "cos " end | Log (t1) -> begin print2 t1 ; printf "log " end | Var (c) -> printf "%c " c | Exp (t1) -> begin print2 t1 ; printf "exp " end ;;Faire les procédures récursives correspondantes. Leur manière de parcourir l'arbre est appelée parcours infixe, postfixe ou préfixe. On peut numéroter les noeuds au fur et à mesure de leur parcours. L'ordre de parcours correspondant est infixe, postfixe ou préfixe. Par exemple, les valeurs des noeuds dans les arbres de recherche sont-elles cohérentes avec l'ordre infixe, préfixe ou postfixe?
let val (x, e) = assoc x e;; let rec eval t e= match t with | Const (x) -> x | Add (t1, t2) -> eval t1 e +. eval t2 e | Mult (t1, t2) -> eval t1 e *. eval t2 e | Div (t1, t2) -> eval t1 e /. eval t2 e | Soust (t1, t2) -> eval t1 e -. eval t2 e | Sinus (t1) -> sin (eval t1 e) | Cosinus (t1) -> cos (eval t1 e) | Log (t1) -> log (eval t1 e) | Var (x) -> val (x, e) | Exp (t1) -> exp (eval t1 e) ;;Pour dériver un terme par rapport à une variable:
let rec der t x= match t with
| Const (x) -> Const (0.)
| Add (t1, t2) -> Add (der t1 x, der t2 x)
| Mult (t1, t2) ->
Add (Mult (t1, der t2 x), Mult (der t1 x, t2))
| Div (t1, t2) -> Div
(Soust (Mult (der t1 x, t2), Mult (t1, der t2 x)),
Mult (t2, t2))
| Soust (t1, t2) -> Soust (der t1 x, der t2 x)
| Sinus (t1) -> Mult (der t1 x, Cosinus t1)
| Cosinus (t1) -> Moins (Mult (der t1 x, Sinus t1))
| Log (t1) -> Div (der t1 x, t1)
| Var (y) -> if x = y then Const (1.) else Const (0.)
| Exp (t1) -> Mult(der t1 x, Exp (t1))
| Moins (t1) -> Moins (der t1 x)
;;
(x + y) + z = x + (y + z)
0 + x = x
(- x) + x = 0
(- x) + (x + y) = y
- 0 = 0
x + 0 = x
- (- x) = x
x + (- x) = 0
x + ((- x) + y) = y
- (x + y) = (- y) + (- x)
Toute égalité est simplement prouvée par la mise
en forme normale selon les règles de réécritures
précédentes. La méthode de complétion de
Knuth et Bendix permet d'obtenir systématiquement ces
règles.
ri := ri op rj (ou` ri, rj sont 2 registres) ri := x (ou` x est une case mémoire) ri := c (ou` c est une constante)
(3 + x) * y * (z + x * y) peut se
calculer par l'une des 2 séquences suivantes:
r1 := 3; r1 := x; r2 := x; r2 := y; r1 := r1 + r2; r1 := r1 * r2; r2 := y; r2 := z; r3 := z; r1 := r1 + r2; r4 := x; r2 := y; r5 := y; r1 := r1 * r2; r4 := r4 * r5; r2 := 3; r3 := r3 + r4; r3 := x; r2 := r2 * r3; r2 := r2 + r3; r1 := r1 * r2; r1 := r1 * r2;
La prochaine fois, on verra comment faire l'analyse syntaxique qui permet de rentrer les termes sous une forme plus "humaine".