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

Question

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

我的问题与它与树的使用有关。

我想了解如何使用 zipper 更改树节点。以及如何不复制整个树（或大部分）。

请澄清我是否对拉链有误。也许它无法帮助更新树？
或者，也许，可以更新树而我只是看不到路？

Answer 1

让我们从列表的拉链模拟开始。如果您想修改列表的第 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))。

拉链与应用于树木的想法相同。您代表树中的某个焦点加上一个上下文（上至父级，下至子级），它以一种形式为您提供整个树，它可以在焦点处轻松修改，并且可以轻松上下移动焦点。

Answer 2

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

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

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

Answer 3

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

Answer 4

这篇文章与 Haskell 相关，但它也很好地解释了 zippers，并且应该很容易从 Haskell-specifics 中抽象出来。

Answer 5

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

基本的 Haskell

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 函数将焦点移到左侧。类似地，其他功能将焦点转移到其他网格单元。