Quelle est la structure de données Zipper et dois-je l'utiliser ?

Question

La question est simple : Je ne peux pas comprendre le Fermeture éclair structure de données.

Ma question est liée à son utilisation avec un arbre.

Je veux comprendre comment je peux changer le nœud de l'arbre en utilisant la fermeture éclair. 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 éclair. Peut-être ne peut-il pas aider à la mise à jour de l'arbre ?
Ou, peut-être, est-il possible de mettre à jour l'arbre et je n'en vois pas le moyen ?

Answer 1

Commençons par l'analogue de Zipper pour les listes. Si vous souhaitez modifier le nième élément d'une liste, cela prend O(n) car vous devez copier les n-1 premiers éléments. Au lieu de cela, vous pouvez garder la liste comme une structure ((les 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 comme ((2 1) 3 (4 5 6)) . Maintenant, vous pouvez facilement changer le 3 pour quelque chose d'autre. Vous pouvez aussi facilement déplacer le focus à gauche ((1) 2 (3 4 5 6)) et à droite ((3 2 1) 4 (5 6)) .

Une fermeture éclair est la même idée appliquée aux arbres. Vous représentez un certain centre d'intérêt dans l'arbre plus un contexte (vers le haut vers les parents, vers le bas vers les enfants) qui vous donne l'arbre entier sous une forme où il est facilement modifiable au centre d'intérêt et il est facile de déplacer le centre d'intérêt vers le haut et vers le bas.

Answer 2

Voici un très bel article expliquant utilisation de la fermeture éclair pour un gestionnaire de fenêtres en mosaïque en Haskell . La personne qui a écrit l'article de wikipedia devrait être abattue.

En bref, la fermeture éclair est un pointeur ou une poignée vers un nœud particulier dans un arbre ou une structure de liste. La fermeture éclair offre un moyen naturel de prendre une structure arborescente et de la traiter comme si l'arbre était "ramassé" par le nœud ciblé - en effet, vous obtenez un deuxième arbre sans avoir à faire des copies supplémentaires de l'arbre original ou à affecter les autres utilisateurs de l'arbre.

L'exemple donné montre comment les fenêtres sont triées à l'origine par emplacement sur l'écran, puis, pour modéliser la mise au point, vous utilisez une fermeture éclair pointée sur la fenêtre de mise au point. Vous obtenez un bel ensemble d'opérations O(1) telles que l'insertion et la suppression sans avoir à mettre en place un cas particulier de la fenêtre de focus ou à écrire du code supplémentaire.

Answer 3

Apprendre un Haskell a aussi un grand chapitre sur les fermetures éclair .

Answer 4

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

Answer 5

Le code se concentre sur une cellule comme le montre cette image. Il y a des zones au-dessus, au-dessous, à gauche et à droite. On se déplace sur cette grille. Le focus est le carré vert.

Haskell de base

type cell = { alive : bool ; column : int ; row : int }
;;

type grid = {gamegrid : cell list list}
;;

type gridzipper  =
             { above : grid
             ; below : grid
             ; left  : cell list
             ; right : cell list
             ; focus : cell }

let left g =
match g.left with
 [] -> None 
| hd::tl ->  let newgridzipper = { g  with focus = hd; left = tl; right = g.right @ [g.focus] } in
             Some(newgridzipper)
;;

La fonction gauche déplace le focus vers la gauche. De même, les autres fonctions déplacent le focus vers d'autres cellules de la grille.