octobre
2009
Un article de Cacophrene
Bonjour !
Il arrive parfois que l’on souhaite stocker des éléments de même type dans une structure qui permette ensuite de les parcourir dans n’importe quel ordre. Les listes définies dans le module List d’OCaml ne sont pas adaptées à ce cas de figure, car ce sont des listes chaînées non circulaires (on ne peut ni revenir en arrière ni recommencer après le dernier élément).
Je vous propose donc, dans ce billet, une implémentation (et la signature) des listes doublement chaînées circulaires en OCaml. Cette version est légèrement différente de celle du projet Extlib (la différence principale concerne la liste vide et le stockage de la longueur) . Voici un bref aperçu des fonctions disponibles :
- Accès à la longueur de la liste en temps constant.
- Fonctions usuelles (make, init, mem, copy…)
- Modification en place du contenu d’un élément de la liste.
- Itérateurs classiques (iter, iteri, map, mapi, fold_left, fold_right).
- Itérateurs inversés (rev_iter, rev_iteri, rev_map, rev_mapi).
- Itérateurs avec condition d’arrêt (loop_until).
- Itérateurs guidés par l’utilisateur (full_iter, full_iteri).
- Conversion avec ‘a list et ‘a array.
Quel intérêt les listes doublement chaînées présentent-elles ? Au-delà de leur utilisation pratique, elles permettent de présenter les valeurs récursives non fonctionnelles en OCaml. Une valeur récursive est une valeur qui s’appelle dans son propre corps de définition. Ces valeurs sont presque toujours des fonctions… mais il est cependant possible de créer des valeurs récursives qui n’en sont pas ! C’est une manière de créer des valeurs circulaires (ce n’est pas la seule).
Les listes doublement chaînées circulaires sont donc constituées d’éléments liés à leur prédécesseur et à leur successeur :
mutable data : 'a;
mutable prev : 'a node;
mutable succ : 'a node;
}
Elles-mêmes sont définies de la façon suivante :
type 'a t = Empty | Circ of int * 'a node
Une liste à un élément (ou singleton) est donc définie par Circ (1, node), où node est une valeur récursive non fonctionnelle obtenue par application de la fonction suivante :
let rec this = { prev = this; succ = this; data = x } in
this
Dernier point, et non des moindres : les listes doublement chaînées peuvent être parcourues dans n’importe quel sens en conservant le caractère tail-rec des fonctions.
| Empty -> ()
| Circ (n, head) ->
let rec loop node i =
if i < n then let () = f node.data in
loop node.succ (i + 1)
in loop head 0
let rev_iter f = function
| Empty -> ()
| Circ (n, head) ->
let rec loop node i =
if i < n then let () = f node.data in
loop node.prev (i + 1)
in loop head.prev 0
Par ailleurs, ces listes n’ayant ni « premier » ni « dernier » élément, il est envisageable de cycler autant de fois que nécessaire :
| Empty -> ()
| Circ (_, node) ->
let rec loop node = if f node.data then loop node.succ in
loop node
Enfin, on peut imaginer un mode de parcours totalement arbitraire choisi par l’utilisateur en fonction de ses besoins :
let full_iter f = function
| Empty -> ()
| Circ (_, node) ->
let rec loop node =
match f node.data with
| `SUCC -> loop node.succ
| `PREV -> loop node.prev
| `STOP -> ()
in loop node
C’est tout pour aujourd’hui. Ah non, j’oubliais : avec une implémentation de type impératif, il faut plus que jamais se méfier des effets de bord et utiliser la fonction de copie à bon escient (comme pour les tableaux) !
Édition : Ajout du rec manquant dans la définition de init, mise à jour des liens vers le code.
À bientôt,
Cacophrène
Salut !
D’abord je tiens à signaler que j’ai édité les trois messages afin de n’en faire qu’un seul contenant la version définitive avec make et init (plus le lien que je me suis permis de rendre cliquable). S’il y a un souci dans ce que j’ai fait n’hésite pas à m’en faire part.
Pour le filtrage, on pourrait même le faire avec cette implémentation sans changer grand chose (mais je doute que ce soit très pertinent). Il faudrait pour cela utiliser le mot-clef private :
type 'a t = private Empty | Circ of int * 'a node
puis :
| Cdll.Empty -> None <br />
| t -> Some (get t, remove (copy t))
Cela implique bien entendu d’écrire quelques fonctions simples de manipulation du type node… et de se prendre la tête sérieusement avec les problèmes de partage de la mémoire. Bref, ce n’est clairement pas l’implémentation de choix pour ce genre de choses. Je crois que c’est là un bon point pour la méthode à base de paresse.
J’avoue ne jamais avoir cherché à savoir ce que ça donnerait parce que le contexte dans lequel j’ai dû utiliser ces listes était toujours très favorable à une implémentation impérative. En tout cas merci pour ce lien que je vais consulter avec intérêt.
Pour la fonction remove, c’est clairement une erreur d’inattention que je vais m’empresser de corriger. Il n’y a en effet aucune raison que la liste vide ne lève pas l’exception
et renvoie toujours
! Merci aussi pour m’avoir signalé l’oubli du rec dans le billet… et dire que c’était le seul truc important
Pour to_array c’est vrai qu’on peut enlever le soupçon de magie noire (ici pas bien méchante). Ça présente même un avantage, c’est qu’on peut commencer le compteur à 1 (je sais, je pinaille).
Bref, je modifie ça tout de suite.
Le prochain billet fera une petite pause avec l’informatique, mais ce ne sera que pour mieux y revenir après.
Cordialement,
Cacophrène
Merci pour ton article.
On peut très bien créer des listes circulaires persistantes en utilisant la paresse:
http://www.haskell.org/haskellwiki/Tying_the_Knot
Avec une implantation persistante on pourrait implanter une facilité de filtrage:
let case = function <br />
| Empty -> None <br />
| Circ (n,node) -> Some(get node,remove node) <br />
Utilisable comme ceci:
match case cl with <br />
| None -> valeur si vide <br />
| Some(h,t) -> valeur si non vide <br />
Ce genre de considérations a au moins le mérite de te guider dans les choix d’implantation de la version mutable.
Par exemple, selon moi, remove devrait être:
let remove = function <br />
| Empty -> raise IsEmpty <br />
| Circ (1, _) -> Empty <br />
| Circ (n, node) -> ... <br />
Parce que remove renvoie la queue.
Autres petites remarques:
Petit oubli de rec dans la définition de init.
Pour la conversion en tableau on peut créer avec Array.make:
let to_array = function <br />
| Empty -> [||] <br />
| Circ (n, head) -> let t = Array.make n (head.data) in <br />
let rec loop node i = <br />
if i < n then (t.(i) <- node.data; loop node.succ (i + 1)) <br />
else t <br />
in loop head 0 <br />
Ou bien avec Array.init:
let to_array = function <br />
| Empty -> [||] <br />
| Circ (n, head) -> <br />
let node = ref head in <br />
let item i = <br />
let d = !node.data in node := !node.succ; d <br />
in Array.init n item <br />