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

Question

问题很简单：我无法理解 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

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

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

给出的示例显示了如何让窗口最初按屏幕上的位置排序，然后使用指向焦点窗口的拉链来模拟焦点。 您可以获得一组很好的 O(1) 操作，例如插入和删除，而无需对焦点窗口进行特殊处理或编写额外的代码。

Answer 3

Learn You a Haskell 还有关于拉链的精彩章节。

Answer 4

该代码重点关注如图所示的单元格。 有上方、下方、左侧和右侧区域。 我们在这个网格上移动。 焦点是绿色方块。

基本哈斯克尔

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)
;;

left 函数将焦点移至左侧。 类似地，其他功能将焦点转移到其他网格单元。