Instructions
Créer un zipper pour un arbre binaire.
Les zippers offrent une façon purement fonctionnelle de naviguer à l'intérieur d'une structure de données et de la manipuler.
Ils contiennent essentiellement une structure de données et un pointeur dans cette structure de données (appelé le focus).
Par exemple, avec un rose tree (où chaque nœud contient une valeur et une liste de nœuds enfants), un zipper peut prendre en charge les opérations suivantes :
-
from_tree (obtenir un zipper à partir d'un rose tree, le focus étant sur le nœud racine)
-
to_tree (extraire le rose tree du zipper)
-
value (obtenir la valeur du nœud focus)
-
prev (déplacer le focus vers l'enfant précédent du même parent,
renvoie un nouveau zipper)
-
next (déplacer le focus vers l'enfant suivant du même parent, renvoie un
nouveau zipper)
-
up (déplacer le focus vers le parent, renvoie un nouveau zipper)
-
set_value (définir la valeur du nœud focus, renvoie un nouveau zipper)
-
insert_before (insérer un nouveau sous-arbre avant le nœud focus, il
devient le prev du nœud focus, renvoie un nouveau zipper)
-
insert_after (insérer un nouveau sous-arbre après le nœud focus, il devient
le next du nœud focus, renvoie un nouveau zipper)
-
delete (supprime le nœud focus et tous ses sous-arbres, le focus passe au
nœud next si possible, sinon au nœud prev si possible,
sinon au nœud parent, renvoie un nouveau zipper)
Il y a de nombreuses façons de résoudre cet exercice, mais nous avons conçu celui-ci pour les personnes qui souhaitent s'entraîner à écrire leurs propres [gestionnaires d'ability][ability-handler-docs].
Écris une ability Zipper qui permet de se déplacer dans une structure de données en arbre binaire.
L'ability Zipper elle-même est déjà définie, mais tu devras implémenter le gestionnaire qui lui permet de se déplacer dans la structure de données en arbre binaire que nous avons choisie.
Étant donné l'arbre binaire suivant, si on appelle Zipper.right, Zipper.right, Zipper.up, puis Zipper.left, on devrait se trouver sur le nœud dont la valeur est 5.
1
/ \
2 4
/ / \
3 5 7
Pour les besoins de cet exercice, si tu appelles left ou right sur un arbre binaire qui ne contient pas de branche gauche ou droite, tu peux renvoyer la valeur du nœud courant.
Points à méditer
En quoi un gestionnaire d'ability est-il lui-même comparable à un zipper ? Peux-tu considérer la continuation d'une fonction comme un pointeur vers le prochain « nœud » de ton programme ? Pourrais-tu stocker les appels passés à la continuation dans ton gestionnaire afin de revenir à un état antérieur ?
Quelles autres structures de données pourrais-tu parcourir de cette façon ? Pourrais-tu écrire un Zipper sur du JSON, ou un autre sur l'arbre DOM HTML ?
