The question is simple: I cannot understand the Zipper data structure.
问题很简单:我无法理解Zipper数据结构。
My question is related to its uses with a Tree.
我的问题与它在树上的用途有关。
I want to understand how can I change the tree node using zipper. And how not to copy the whole tree (or the most part of it).
我想了解如何使用zipper更改树节点。以及如何不复制整棵树(或大部分)。
Please, clarify if I'm wrong with zipper. Maybe it cannot help with the tree update?
Or, maybe, it is possible to update the tree and I just cannot see the way?
请澄清拉链是否有问题。也许它无法帮助树更新?或者,也许,有可能更新树,我只是看不到路?
4 个解决方案
#1
Let's start with the Zipper-analog for lists. If you'd like to modify the nth element of a list, it takes O(n) because you have to copy the n-1 first elements. Instead, you can keep the list as a structure ((first n-1 elements reversed) nth element (remaining elements)). For example, the list (1 2 3 4 5 6) modifiable at 3 would be represented as ((2 1) 3 (4 5 6)). Now, you can easily change the 3 to something else. You can also easily move the focus left ((1) 2 (3 4 5 6)) and right ((3 2 1) 4 (5 6)).
让我们从列表的Zipper-analog开始。如果您想修改列表的第n个元素,则需要O(n),因为您必须复制n-1个第一个元素。相反,您可以将列表保持为结构((第一个n-1个元素反转)第n个元素(其余元素))。例如,可修改为3的列表(1 2 3 4 5 6)将表示为((2 1)3(4 5 6))。现在,您可以轻松地将3更改为其他内容。您也可以轻松地向左移动焦点((1)2(3 4 5 6))和右移((3 2 1)4(5 6))。
A zipper is the same idea applied to trees. You represent a certain focus in the tree plus a context (up to parents, down to children) which gives you the whole tree in a form where it's easily modifiable at the focus and it's easy to move the focus up and down.
拉链与树木应用的理念相同。你在树中加上一个特定的焦点加上一个上下文(由父母决定,直到子项),它以一种形式为你提供整个树,它可以在焦点处轻松修改,并且可以轻松地上下移动焦点。
#2
Here is a very nice article explaining using the zipper for a tiling window manager in Haskell. The Wikipedia article is not a good reference.
这是一篇非常好的文章,解释了如何在Haskell中使用拉链作为平铺窗口管理器。*的文章不是一个很好的参考。
In short, the zipper is a pointer or handle to a particular node in a tree or list structure. The zipper gives a natural way of taking a tree structure and treating it as though the tree was "picked up" by the focused node - in effect, you get a second tree without requiring additional copies made of the original tree or affecting other users of the tree.
简而言之,拉链是树或列表结构中特定节点的指针或句柄。拉链提供了一种自然的方式来获取树结构并对其进行处理,就像树被聚焦节点“拾取”一样 - 实际上,您得到第二棵树而不需要由原始树构成的额外副本或影响其他用户那个树。
The example given shows how you have the windows originally sorted by location on the screen, and then to model focus you use a zipper pointed at the focus window. You get a nice set of O(1) operations such as insert and delete without having to special case the focus window or write additional code.
给出的示例显示了如何在窗口上按位置对窗口进行最初排序,然后使用指向焦点窗口的拉链来建模焦点。您可以获得一组很好的O(1)操作,例如插入和删除,而无需特殊情况下的焦点窗口或编写其他代码。
#4
This article is related to Haskell, but it also explains zippers fairly well and it should be easy to abstract from the Haskell-specifics.
本文与Haskell有关,但它也很好地解释了拉链,并且应该很容易从Haskell特定的内容中抽象出来。
#1
Let's start with the Zipper-analog for lists. If you'd like to modify the nth element of a list, it takes O(n) because you have to copy the n-1 first elements. Instead, you can keep the list as a structure ((first n-1 elements reversed) nth element (remaining elements)). For example, the list (1 2 3 4 5 6) modifiable at 3 would be represented as ((2 1) 3 (4 5 6)). Now, you can easily change the 3 to something else. You can also easily move the focus left ((1) 2 (3 4 5 6)) and right ((3 2 1) 4 (5 6)).
让我们从列表的Zipper-analog开始。如果您想修改列表的第n个元素,则需要O(n),因为您必须复制n-1个第一个元素。相反,您可以将列表保持为结构((第一个n-1个元素反转)第n个元素(其余元素))。例如,可修改为3的列表(1 2 3 4 5 6)将表示为((2 1)3(4 5 6))。现在,您可以轻松地将3更改为其他内容。您也可以轻松地向左移动焦点((1)2(3 4 5 6))和右移((3 2 1)4(5 6))。
A zipper is the same idea applied to trees. You represent a certain focus in the tree plus a context (up to parents, down to children) which gives you the whole tree in a form where it's easily modifiable at the focus and it's easy to move the focus up and down.
拉链与树木应用的理念相同。你在树中加上一个特定的焦点加上一个上下文(由父母决定,直到子项),它以一种形式为你提供整个树,它可以在焦点处轻松修改,并且可以轻松地上下移动焦点。
#2
Here is a very nice article explaining using the zipper for a tiling window manager in Haskell. The Wikipedia article is not a good reference.
这是一篇非常好的文章,解释了如何在Haskell中使用拉链作为平铺窗口管理器。*的文章不是一个很好的参考。
In short, the zipper is a pointer or handle to a particular node in a tree or list structure. The zipper gives a natural way of taking a tree structure and treating it as though the tree was "picked up" by the focused node - in effect, you get a second tree without requiring additional copies made of the original tree or affecting other users of the tree.
简而言之,拉链是树或列表结构中特定节点的指针或句柄。拉链提供了一种自然的方式来获取树结构并对其进行处理,就像树被聚焦节点“拾取”一样 - 实际上,您得到第二棵树而不需要由原始树构成的额外副本或影响其他用户那个树。
The example given shows how you have the windows originally sorted by location on the screen, and then to model focus you use a zipper pointed at the focus window. You get a nice set of O(1) operations such as insert and delete without having to special case the focus window or write additional code.
给出的示例显示了如何在窗口上按位置对窗口进行最初排序,然后使用指向焦点窗口的拉链来建模焦点。您可以获得一组很好的O(1)操作,例如插入和删除,而无需特殊情况下的焦点窗口或编写其他代码。
#3
Learn You a Haskell also has a great chapter about zippers.
了解一个Haskell还有一个关于拉链的伟大章节。
#4
This article is related to Haskell, but it also explains zippers fairly well and it should be easy to abstract from the Haskell-specifics.
本文与Haskell有关,但它也很好地解释了拉链,并且应该很容易从Haskell特定的内容中抽象出来。