Types récursifs
Un article de Mangue.org, l'encyclopéde libre.
Dans le cours précédent nous avons vu comment construire nos propres structures de données. Nous allons aller plus loin dans la définition de types et créer des types récursifs. Grâce à eux nous serons capables de coder quelque chose de similaire aux listes chaînées et surtout des arbres binaires (ou d'autres types d'arbres)...
| Sommaire |
Les listes
Peut être avez vous remarqué l'étrange similarité entre les listes et les types sommes. Imaginez un type codant une valeur de son propre type (puisque c'est possible)... Nous écrirons alors des fonctions récursives agissant sur ce type de données.
| Remarque |
| Un type est récursif si son identificateur (son nom) apparaît dans sa définition. Nous pourrons ainsi créer des structures dont la taille varira en mémoire. |
Nous allons implémenter une liste dynamique. Ce n'est pas la même chose que le type 'a list que nous avons vu dans les cours précédents. Chaque élément d'une liste dynamique est un enregistrement comprenant une valeur biensûr mais également un lien vers l'élément suivant.
Les listes simples
Commençons par quelque chose de relativement facile, une liste chainée (attention c'est un abus de langage puisque les véritables listes chaînées ne sont pas construites de même) dans un seul sens. C'est ce que nous appellerons une liste simple.
Pour les construire nous avons besoin d'un type codant deux valeurs, une valeur effective et un pointeur (toujours par abus de langage) vers l'élément suivant de la liste. Nous définirons également une constante NULL permettant d'indiquer qu'il n'y a plus d'éléments dans la liste.
Voilà ce que ça donne :
# type ('a) liste_simple =
| NULL (* cas terminal représentant la fin de la liste (pas d'élément) *)
| Data of 'a * ('a) liste_simple ;;
Type liste_simple defined.
# let liste = NULL ;;
liste : 'a liste_simple = NULL
# let liste = (0,liste) ;;
liste : int * 'a liste_simple = 0, NULL
# let liste = (1,liste) ;;
liste : int * (int * 'a liste_simple) = 1, (0, NULL)
# let liste2 = Data(0,(Data(1,(Data(2,NULL))))) ;;
liste2 : int liste_simple = Data (0, Data (1, Data (2, NULL)))
Vous vous en doutiez certainement il est indispensable d'invoquer le constructeur Data pour construire des valeurs de type liste_simple. Nous avons essayé de le faire par de simples n-uplets et l'évaluation nous a renvoyé un résultat de type int * ('a) liste_simple
| Danger |
| Prenez garde à ceci puisque c'est une cause fréquente d'erreur dans les programmes. |
Fonctions sur les listes récursives
Ecrivons à présent une fonction chargée de compter le nombre d'éléments d'une liste_simple. Il nous suffira d'écrire une fonction récursive avec filtrage. Celle ci renverra 0 dans le cas de NULL ou le nombre total d'éléments de ce qu'il reste dans la liste dans le cas d'un Data(...,...)
Je vous rappelle, pour mémoire, la fonction longueur que nous avions écrit pour calculer la longuer d'une liste (type 'a list). Vous remarquerez l'étrange similarité avec notre fonction longueur_liste_simple :
# let rec longueur = fun | [] -> 0 | (_ :: reste) -> 1 + longueur (reste) ;; longueur : 'a list -> int = <fun> # let rec longueur_liste_simple = fun | NULL -> 0 | (Data(_,suite)) -> 1 + longueur_liste_simple (suite) ;; longueur_liste_simple : 'a liste_simple -> int = <fun> # longueur_liste_simple (liste2) ;; - : int = 3
Je vais maintenant vous demander d'écrire deux fonctions équivalentes aux opérateurs :: et @ mais agissant sur des liste_simple. Pas vraiment de problèmes à mon avis pour :: puisqu'il vous suffira d'insérer un élément en tête de liste. En revanche je vous précise que pour @ vous devrez écrire une fonction récursive à deux arguments. Avant de regarder la solution essayez de trouver par vous même et si vous avez des problèmes n'hésitez pas de poser des questions sur le forum, même si elles vous paraissent débiles ;-)
# 1 :: [] ;;
- : int list = [1]
# [0;1;2] @ [3;4;5] ;;
- : int list = [0; 1; 2; 3; 4; 5]
# let ajoute élément liste = Data(élément,liste) ;;
ajoute : 'a -> 'a liste_simple -> 'a liste_simple = <fun>
# ajoute 63 liste2 ;;
- : int liste_simple = Data (63, Data (0, Data (1, Data (2, NULL))))
# let rec concatene = fun
| l NULL -> l (* cas simple la seconde liste est vide *)
| NULL l -> l (* cas simple la première liste est vide *)
|(Data(e,suite)) liste -> Data(e,concatene suite liste) ;;
concatene : 'a liste_simple -> 'a liste_simple -> 'a liste_simple = <fun>
# concatene liste2 (Data(81,(Data(63,NULL)))) ;;
- : int liste_simple =
Data (0, Data (1, Data (2, Data (81, Data (63, NULL)))))
# trace "concatene" ;;
The function concatene is now traced.
- : unit = ()
# concatene liste2 liste2 ;;
concatene <-- Data (<poly>, Data (<poly>, Data (<poly>, NULL)))
concatene --> <fun>
concatene* <-- Data (<poly>, Data (<poly>, Data (<poly>, NULL)))
concatene <-- Data (<poly>, Data (<poly>, NULL))
concatene --> <fun>
concatene* <-- Data (<poly>, Data (<poly>, Data (<poly>, NULL)))
concatene <-- Data (<poly>, NULL)
concatene --> <fun>
concatene* <-- Data (<poly>, Data (<poly>, Data (<poly>, NULL)))
concatene <-- NULL
concatene --> <fun>
concatene* <-- Data (<poly>, Data (<poly>, Data (<poly>, NULL)))
concatene* --> Data (<poly>, Data (<poly>, Data (<poly>, NULL)))
concatene* --> Data
(<poly>, Data (<poly>, Data (<poly>, Data (<poly>, NULL))))
concatene* --> Data
(<poly>,
Data
(<poly>, Data (<poly>, Data (<poly>, Data (<poly>, NULL)))))
concatene* --> Data
(<poly>,
Data
(<poly>,
Data
(<poly>,
Data (<poly>, Data (<poly>, Data (<poly>, NULL))))))
- : int liste_simple =
Data (0, Data (1, Data (2, Data (0, Data (1, Data (2, NULL))))))
# untrace "concatene" ;;
The function concatene is no longer traced.
- : unit = ()
Voilà avec ces trois fonctions vous pouvez refaire sur le type 'a liste_simple tout ce que vous faisiez avec le type 'a list
| Question |
A quoi correspond ce <poly> qui apparaît lorsqu'on trace la fonction concatene ? Ce n'est pas si important, pour l'instant considérez simplement qu'il s'agit de valeurs un peu spéciales comme c'était le cas avec <fun>
|
Exercice
Je vais maintenant vous demander d'écrire une fonction prenant en argument un int liste_simple (libre à vous de l'étendre aux 'a liste_simple) et renvoyant une valeur de type string lisible par un être humain.
# string_of_liste_simple ;; - : int liste_simple -> string = <fun> # string_of_liste_simple liste2 ;; - : string = "0;1;2"
Autres listes
Il est aussi possible de construire des listes doubles. Celle-cis seront différentes des listes simples dans le sens où elles redirigeront en même temps vers l'élément suivant et l'élément précédent de la liste. Nous devrons donc étendre la structure de base des listes afin qu'elle comporte deux pointeurs (toujours par abus de langage) au lieu d'un seul.
Pour implémenter un tel type de données nous devrons donc utiliser un type codant trois valeurs dont deux serviront uniquement de liens vers d'autres éléments de la liste. Pour accomplir ce prodige vous avez deux solutions, soit utiliser les références que nous ne connaissons pas encore, soit faire intervenir des valeurs mutables en tant que champs d'enregistrements. Celà deviendrait rapidement très complexe c'est pourquoi je ne le traite pas ici. Si vous voulez vraiment essayer et que vous avez des problèmes le forum est là :)
Arbres binaires
Les arbres binaires font appel à une abstraction plus importante. Il s'agit également d'un type récursif ; cette fois chaque "élèment" peut coder soit une constante (on parle alors de feuilles), soit un autre arbre binaire (on parle alors de noeud) comme dans le schéma suivant :
Dans le cadre de cec cours nous nous limiterons aux abres binaires, c'est à dire que chaque noeud comprendra deux informations (pas plus mais pas moins non plus). Vous rencontrerez certainement un jour d'autres types d'arbres mais ils ne sont utilisés qu'exceptionnellement, c'est pourquoi je n'en parlerai pas davantage.
Voici l'implémentation du type 'a Tree, qui est récursive évidemment, et pour laquelle j'utilise des noms d'identificateurs en anglais afin de laisser tous les noms en français imaginables libres pour définir des constantes par la suite...
# type ('a) Tree =
| Leaf of 'a
| Knot of ('a Tree) * ('a Tree) ;;
Type Tree defined.
# let arbre1 = Leaf(0) ;;
arbre1 : int Tree = Leaf 0
# let arbre2 = Knot (Leaf invalid_arg,Leaf failwith) ;;
arbre2 : (string -> 'a) Tree = Knot (Leaf <fun>, Leaf <fun>)
Non seulement celà semble difficile à construire mais en plus il va falloir écrire toues les fonctiosn nécessaires à l'exploitation de ce type alors quel peut bien en être l'intérêt ??! Pour l'instant il est clair que celà ne peut servir qu'à impressionner vos amis lors d'un repas, mais nous allons les utiliser pour des choses bien plus intéressantes ;-p
Associons à chaque noeud une information supplémentaire, par exemple les opérateurs arithmétiques de base. Dans ce cas notre arbre pourrait servir à représenter des opérations simples comme le montre ce schéma :
Plus un noeud est situé en bas de l'arbre, plus l'expression arithmétique simple qu'il représente est comprise entre parenthèses. Il n'y a donc qu'une seule évaluation possible pour ce type d'arbre, de plus il est inutile de coder en Caml la notion de parenthèses ou de priorité de calcul puisqu'elle est évidente dans un arbre !
| Réponse |
Vous pouvez vous demander comment représenter un simple - x dans ce type d'arbre... Et bien il suffit de coder 0 - x.De cette façon il est possible de coder toutes les opérations arithmétiques simples :-) |
Exploitation d'un arbre...
Nous allons dans le cadre de cet exemple nous limiter à des int Tree mais il est possible de faire la même chose pour des nombres réels, sachez le ! Et si vous vous en sentez la force essayez donc de le faire par vous même...
Il va falloir écrire uen fonction pour chaque opérateur de l'arbre. Par la suite, et pour éviter le risque de confusion, nous allons définir un type Opérateur qui sera utilisé dans les 'int Tree comme ceci :
# type Operator =
| OpMult (* produit *)
| OpDivi (* division entière *)
| OpMod (* reste de la division entière *)
| OpSum (* somme *)
| OpSub (* différence *) ;;
Type Operator defined.
# type ('a) Tree =
| Leaf of 'a
| Knot of ('a Tree) * ('a Tree) * Operator ;;
Type Tree defined.
# let ArbreBinaire =
Knot
(
Knot
(
Leaf ( 2),
Knot ( Leaf (0), Leaf (-1), OpSub),
OpMult
),
Knot ( Leaf (1), Leaf (4), OpSum),
OpSum
) ;;
ArbreBinaire : int Tree =
Knot
(Knot (Leaf 2, Knot (Leaf 0, Leaf -1, OpSub), OpMult),
Knot (Leaf 1, Leaf 4, OpSum), OpSum)
| Astuce |
| L'indentation n'est pas obligatoire pour définir une telle constante, mais je pense que vous admettrez que la lisibilité en est améliorée ! |
Nous allons maintenant nous attaquer au gros du problème, c'est à dire la fonction eval_Tree) permettant justement d'évaluer l'expression (entière dans notre exemple) codée par un arbre. Le type int Tree est récursif, alors notre fonction le sera forcément ! Voici une correction possible :
# let rec eval_Tree = fun | (Leaf x) -> x | (Knot(x,y,OpSum)) -> eval_Tree(x) + eval_Tree(y) | (Knot(x,y,OpSub)) -> eval_Tree(x) - eval_Tree(y) | (Knot(x,y,OpMult)) -> eval_Tree(x) * eval_Tree(y) | (Knot(x,y,OpDivi)) -> eval_Tree(x) / eval_Tree(y) | (Knot(x,y,OpMod)) -> eval_Tree(x) mod eval_Tree(y) ;; eval_Tree : int Tree -> int = <fun> # eval_Tree (ArbreBinaire) ;; - : int = 7
Il n'y a que très peu de modifications à apporter pour adapter cette fonction à des float Tree par exemple (mais attention cette fois l'opérateur OpMod n'aurait plus de sens et il faudrait en interdire l'évaluation...
| Danger |
la fonction eval_Tree provoque une explosion combinatoire, c'est à dire que le nombre d'appels récursifs à la fonction augmente à une vitesse impressionante... Si vous en doutez encore tracez les appels récursifs de la fonction.Il en résulte qu'un appel de cette fonction avec un arbre complexe en argument risque de provoquer un dépassement de mémoire... |
Exercice
Vous devez maintenant écrire une fonction string_of_Tree qui renverra l'arbre binaire écrit sous forme de chaîne de caractère afin d'en faciliter la lecture par un humain. La correction proposée est écrite avec le type int Tree mais vous n'aurez aucune difficultée à l'adapter à des float Tree ;-p
# string_of_Tree ;; - : int Tree -> string = <fun> # string_of_Tree (ArbreBinaire) ;; - : string = "((2*(0-(-1)))+(1+4))"
