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

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

我的问题与它在树上的用法有关.

我想了解如何使用zipper更改树节点.以及如何不复制整棵树(或大部分).

请澄清拉链是否有问题.也许它无法帮助树更新？
或者,也许,有可能更新树,我只是看不到路？

1> namin..：

---

让我们从列表的Zipper-analog开始.如果您想修改列表的第n个元素,则需要O(n),因为您必须复制n-1个第一个元素.相反,您可以将列表保持为结构((第一个n-1个元素反转)第n个元素(其余元素)).例如,(1 2 3 4 5 6)可修改为3 的列表将表示为((2 1) 3 (4 5 6)).现在,您可以轻松地将3更改为其他内容.您也可以轻松地左右移动对焦((1) 2 (3 4 5 6))和正确的((3 2 1) 4 (5 6)).

拉链与树木相同.你在树中加上一个特定的焦点加上一个上下文(由父母决定,直到孩子),它以一种形式为你提供整个树,它可以在焦点处轻松修改,并且可以轻松地上下移动焦点.

---

@eSKay:周到的问题.如果需要花费不变的时间来获取列表中的任何元素,则不需要.但通常情况下,列表具有头部和其余部分的原始访问器,因此反转前n-1个元素的基本原理很明确:您很快就想要获得前一个元素,这就是它的头部.

---

@namin:一个问题:为什么我们需要反转第一个`n-1`元素？我完全不知道它的用途是什么.请解释.

2> 1800 INFORMA..：

---

这是一篇非常好的文章,解释了如何在Haskell中使用拉链作为平铺窗口管理器.维基百科的文章不是一个很好的参考.

简而言之,拉链是树或列表结构中特定节点的指针或句柄.拉链提供了一种自然的方式来获取树结构并对其进行处理,就像树被聚焦节点"拾取"一样 - 实际上,您获得第二棵树而不需要由原始树构成的额外副本或影响其他用户那个树.

给出的示例显示了如何根据屏幕上的位置对窗口进行最初排序,然后使用指向焦点窗口的拉链来建模焦点.您可以获得一组很好的O(1)操作,例如插入和删除操作,而无需特殊情况下的焦点窗口或编写其他代码.

---

也许你可以编辑维基百科文章？

---

我正在获得链接的403s,这是相同文章的更新链接:http://donsbot.wordpress.com/2007/05/17/roll-your-own-window-manager-tracking-focus-with -a拉链/

3> thSoft..：

---

了解一个Haskell还有一个关于拉链的伟大章节.