Comment naviguer à l'intérieur d'un HUET Zipper

Je lis Huet Zipper, je ne peux pas comprendre la méthode de go_up:Comment naviguer à l'intérieur d'un HUET Zipper

let go_up (Loc(t,p)) = match p with 
Top -> failwith "up of top" 
| Node(left,up,right) -> Loc(Section((rev left) @ (t::right)),up);;

La source complète d'autres types de définitions se trouvent dans le document lié, si vous comprenez Zipper , Je pense que cela n'a pas d'importance de répondre à ma question. D'après ce que je sais à propos de Zipper, un Location contient le nœud actuel et son Path ou le Context. Le Path a tout autre que le nœud actuel et ses sous-nœuds, ou certaines personnes l'ont appelé a one-hole-context. Eh bien, en déplaçant la mise au point, le nœud parent du nœud actuel deviendra le nouveau nœud actuel. Mais ici, l'auteur concatène les nœuds actuels et ses frères et soeurs. Mais ce n'est pas un nœud parent, seulement les enfants du nœud parent. Je suis bloqué ici lors de l'implémentation de ma propre méthode moveUp dans Scala, et j'ai échoué à représenter correctement le nœud parent du nœud actuel.

Source

2012-08-26 Sawyer

Vous pouvez vous inspirer d'une ancienne implémentation de zipper n-aire de la mienne: http://gist.github.com/3477576 – ron

@ron Votre contexte contient toujours une référence aux données du nœud parent, le contexte de ce document ne 't. J'en ai vu d'autres, au lieu de tenir un contexte parent, ils possèdent un emplacement parent, ce qui vous donne également la possibilité d'accéder au nœud parent. – Sawyer

Vous ne pouvez pas vous soucier du portage vers une autre langue, mais 'rev foo @ bar' aurait avantage à être écrit' List.rev_append foo bar', qui traversera 'foo' une fois au lieu de deux fois. – gasche

La fermeture à glissière est ici pour le type de données d'arbre suivant:

type tree = 
    Item of item 
| Section of tree list;;

Et le chemin du papier type de données est la suivante:

type path = 
    Top 
| Node of tree list * path * tree list;;

Le Node contient trois composants. Les enfants du nœud parent situés à gauche du trou (left), le chemin le plus haut (up) et les enfants du nœud parent situés à droite du trou (right). Lors du déplacement vers le haut, afin de produire le nœud parent réel, nous devons brancher l'ancien arbre t à la bonne position entre left et right. Comme les enfants à gauche sont stockés dans l'ordre inverse, nous devons d'abord les inverser.

Source

2012-08-26 10:45:54 kosmikus

'afin de produire le nœud parent réel, nous devons brancher l'ancien arbre t à la bonne position entre la gauche et la droite'. mais plugin t dans la bonne position entre la gauche et la droite, seulement produire un enfant du parent, pas le parent. Je sais que Section est le type d'arbre, mais cela ne veut pas dire que si vous descendez d'un nœud parent unique, et que vous naviguez vers le haut, vous avez une section de nœuds comme nœud parent. – Sawyer

@Sawyer Si vous descendez, vous obtiendrez un 'Section', car le seul autre choix serait' Item', mais 'Item' n'a pas d'enfants donc vous n'auriez pas pu descendre en premier lieu. – gasche

@Sawyer Comme gasche le dit dans son autre réponse, il n'y a rien de plus à un nœud dans cette définition de 'tree' que sa liste d'enfants. Si nous pouvons reconstruire la liste des enfants du nœud parent, nous pouvons également reconstruire le nœud parent en lui appliquant 'Section'. (Notez que cela se produit dans un contexte fonctionnel, il n'y a pas d'identité d'objet.) – kosmikus

l'auteur concatène les nœuds actuels et ses frères et sœurs. Mais ce n'est pas un nœud parent, seulement les enfants du nœud parent

Avec la définition de papier cité par kosmikus, un nœud non-feuille Section est définie par rien d'autre que ses enfants. Si vous avez ajouté des informations supplémentaires, vous devez l'ajouter à la définition de la fermeture à glissière.

Source

2012-08-26 16:36:02 gasche

Comment naviguer à l'intérieur d'un HUET Zipper

Répondre

Questions connexes