Zipper 数据结构

定义

Zipper(拉链)是一种在不可变数据结构中高效进行局部导航与更新的技术,由 Gérard Huet 于 1997 年发表。它把结构改写为"当前焦点 + 上下文"的序对:上下文记录从根到焦点沿途的所有"挖去焦点后的剩余部分",从而支持以常数时间在邻近位置移动并就地更新焦点。

原理

以列表为例,Zipper 把它拆成(已走过部分的逆序, 焦点及其后部分),左移右移只需在两段间搬动一个元素。树的 Zipper 则在上下文中保存父节点方向与兄弟子树。所有操作返回新 Zipper,原结构不变,与持久化数据结构自然契合。理论上,某结构 Zipper 的上下文类型恰是该结构类型的"导数",这一优美联系由 Conor McBride 阐明。

应用

Zipper 适合实现文本编辑器的光标与缓冲区、文件系统导航、XML/JSON 文档的游标式编辑;Clojure 的 clojure.zip、Haskell 的多种 zipper 库提供现成实现,XMonad 窗口管理器用它管理工作区焦点。