Zipper数据结构是什么?我应该使用它吗？

Question

问题很简单:我无法理解Zipper数据结构。

我的问题与它在Tree中的使用有关。

我想知道如何使用zipper更改树节点。以及如何不复制整个树(或其中大部分)。

如果我的拉链有问题，请澄清。也许它不能帮助更新树？

或者，也许可以更新树，但我只是看不到方向？

Answer 1

让我们从列表的Zipper模拟开始。如果你想修改一个列表的第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))。

拉链是适用于树木的相同概念。您表示树中的某个焦点加上上下文(向上到父级，向下到子级)，这为您提供了整个树的形式，在这种形式下，可以很容易地在焦点处进行修改，并且可以轻松地上下移动焦点。

Answer 2

这里有一篇非常好的文章解释了using the zipper for a tiling window manager in Haskell。维基百科的文章不是一个很好的参考。

简而言之，拉链是指向树或列表结构中特定节点的指针或句柄。拉链提供了一种自然的方式来获取树结构，并将其视为树被关注的节点“拾取”-实际上，您可以获得第二棵树，而不需要对原始树进行额外的复制，也不会影响树的其他用户。

给出的示例展示了如何按屏幕上的位置对窗口进行排序，然后使用指向焦点窗口的拉链对焦点进行建模。您得到了一组很好的O(1)操作，例如插入和删除，而不必对焦点窗口进行特殊处理或编写额外的代码。

Answer 3

知道你一个Haskell也有a great chapter about zippers。