Quelle est la structure de données de Zipper et devrais-je l’utiliser?

La question est simple: je ne peux pas comprendre la structure de données de Zipper .

Ma question est liée à ses utilisations avec un arbre.

Je veux comprendre comment je peux changer le nœud d’arbre en utilisant la fermeture à glissière. Et comment ne pas copier l’arbre entier (ou la plus grande partie de celui-ci).

S’il vous plaît, clarifiez si je me trompe avec la fermeture à glissière. Peut-être que cela ne peut pas aider avec la mise à jour de l’arbre?
Ou, peut-être, il est possible de mettre à jour l’arbre et je ne peux pas voir le chemin?

    Commençons par l’analogue Zipper pour les listes. Si vous souhaitez modifier le nième élément d’une liste, il faut O (n) car vous devez copier les n-1 premiers éléments. Au lieu de cela, vous pouvez conserver la liste en tant que structure ((n-1 premiers éléments inversés) nième élément (éléments restants)). Par exemple, la liste (1 2 3 4 5 6) modifiable à 3 serait représentée par ((2 1) 3 (4 5 6)) . Maintenant, vous pouvez facilement changer le 3 en autre chose. Vous pouvez également déplacer facilement le focus vers la gauche ((1) 2 (3 4 5 6)) et vers la droite ((3 2 1) 4 (5 6)) .

    Une fermeture à glissière est la même idée appliquée aux arbres. Vous représentez une certaine focalisation dans l’arbre et un contexte (jusqu’aux parents, jusqu’aux enfants) qui vous donne l’arbre entier sous une forme facilement modifiable au niveau du focus et il est facile de déplacer le focus de haut en bas.

    Voici un très bel article expliquant l’ utilisation de la fermeture à glissière pour un gestionnaire de fenêtres en mosaïque dans Haskell . L’article de Wikipedia n’est pas une bonne référence.

    En bref, la fermeture à glissière est un pointeur ou un handle vers un nœud particulier dans une arborescence ou une structure de liste. La fermeture à glissière offre un moyen naturel de prendre une structure arborescente et de la traiter comme si l’arbre était «capté» par le nœud ciblé. En effet, vous obtenez un deuxième arbre sans nécessiter de copies supplémentaires de l’arbre l’arbre.

    L’exemple donné montre comment les fenêtres ont été initialement sortingées par emplacement sur l’écran, puis pour modéliser le focus, vous utilisez une fermeture à glissière pointant vers la fenêtre de mise au point. Vous obtenez un bon ensemble d’opérations O (1), telles que l’insertion et la suppression, sans avoir à placer de cas particulier la fenêtre de focus ou à écrire du code supplémentaire.

    Learn You a Haskell a également un excellent chapitre sur les fermetures à glissière .

    Cet article est lié à Haskell, mais il explique également assez bien les fermetures à glissière et il devrait être facile de les extraire des spécificités de Haskell.