The Zipper (函数式珍珠)

本文的作者Gérard Huet以简单明快的笔触优雅地呈现了zipper的想法.

Capsule Review

几乎每个程序员都曾遇到过表示一个带有作为注意力焦点的子树的树的问题, 其中焦点可以在树中左移, 右移, 上移, 下移. zipper是Huet为一种能够满足这种需求的精致数据结构取的巧妙的名字. 我多么希望我在曾经遇到这种任务时就知道这个数据结构啊, 因为当时我想到的方法和zipper比起来既不高效也不优雅.

第1章 引论

纯粹应用性的编程范式的主要缺陷在于许多高效的算法都依赖于数据结构的破坏性操作, 这些数据结构有位向量, 字符数组, 或者什么其他的可变按层次分类结构, 但是纯粹应用性的数据结构不能直接地模拟它们. 对于这种问题的一种著名解决方案是所谓的函数式数组 (Paulson, 1991). 对于树而言, 这相当于以如下方法非破坏性地修改树中的出现, 即复制从树的根到这个出现的路径. 当数据结构是只是局部于某个算法的对象时, 这被认为是可以忍受的, 因为相较于复制整个树的朴素方法而言, 其只需要对数的代价. 但是若数据结构表示了某种全局性的上下文, 例如文本编辑器的缓冲区, 或者是一个证明系统的公理和引理数据库, 那么这种技术就是不可接受的了. 在这个笔记里, 我们解释了一种简单的解决方案, 其中的树编辑完全是局部性的, 数据上的柄 (handle) 不是树的原本的根, 而是在树中的当前位置.

基本的想法是简单的: 树被从里翻到外, 就像手套一样, 在路径结构里, 从根到当前位置的指针被反转了. [译注: 虽然说其实反转的顺序就是自然的, 类似于栈.] 当前的位置不仅保存了向下的当前子树, 也保存了向上的路径. 所有的导航和修改原语都操作于位置结构上. 在结构中上和下可以类比于关闭和打开一个拉链 (zipper), 故取此名.

作者在设计一个结构编辑器的核心时想到了这种数据类型, 这个结构编辑器是作为一个证明助手的结构管理器使用的. 这个简单的想法肯定已被诸多程序员在无数场合下发明出来, 而我呈现这个应该算是口口相传的东西的唯一理由在于其似乎还没有被发表过, 更不用说为人熟知了.

第2章 zipper数据结构

基本的想法存在着诸多的变体. 首先让我们呈现一个版本, 其适用于具有可变元数的匿名树结点的树, 而树叶所注入的值来源于一个未加刻画的item类型.

第2.1节 树, 路径, 和位置

我们假定存在一个类型参数item, 其包含了我们想要层次性地操纵的元素; 树结构不过就是层次性的列表, 其将树组织为section. 例如, 在UNIX的文件系统中, item会是文件, 而section则是目录; 而在一个文本编辑器里, item会是字符, 而两个层次的section分别将缓冲区表示为行的列表以及将行表示为字符的列表. 推广这个概念至允许任意多个层次, 那么我们将得到层次性Turing机器的概念, 其纸带位置 (tape position) 可能包含一个符号, 或者是一个来源于更低层级的纸带.

这里所呈现的算法均以具体的编程语言OCaml写成 (Leroy et al., 1996). 这些代码很容易翻译为其他编程语言, 不论是否为函数式的, 不论是否是惰性的.

type tree =
    Item of item
  | Section of tree list;;

现在我们考虑tree中的path.

type path =
    Top
  | Node of tree list * path * tree list;;

一个path就像一条拉链 (zipper), 其允许人们撕开树结构到一个特定的位置. 一个Node(l,p,r)包含了其哥哥 (elder siblings) 的列表l (自其中最年轻的起), 其父路径p, 以及其弟弟 (younger siblings) 的列表r (自其中最年长的起). [译注: 我怀疑原文作者将最年轻和最年长搞反了, 于是改成了现在这样, 因为这里是越左越年长, 所以说l的开头实际上应该是比当前焦点 (见后文) 年长的里面最年轻的, 而r的开头实际上应该是比当前焦点年轻的里面最年长的.]

type location = Loc of tree * path;;

一个location由一个突出的tree (其是当前的焦点) 和其path (其代表了周围的上下文) 构成. 注意到一个位置并不对应于树中的一个出现, 而是一个指向某个特定子树与其周围上下文之间连接的弧的指针. [译注: 应该说是一种概念上的指针而非实际上的指针.]

Section[Section[Item "a"; Item "*"; Item "b"];
        Item "+";
        Section[Item "c"; Item "*"; Item "d"]];;

Loc(Item "*",
    Node([Item "c"],
         Node([Item "+"; Section [Item "a"; Item "*"; Item "b"]],
              Top,
              []),
         [Item "d"]))

第2.2节 树中导航的原语

let go_left (Loc(t,p)) = match p with
    Top -> failwith "left of top"
  | Node(l::left,up,right) -> Loc(l,Node(left,up,t::right))
  | Node([],up,right) -> failwith "left of first";;

let go_right (Loc(t,p)) = match p with
    Top -> failwith "right of top"
  | Node(left,up,r::right) -> Loc(r,Node(t::left,up,right))
  | _ -> failwith "right of last";;

let go_up (Loc(t,p)) = match p with
    Top -> failwith "up of top"
  | Node(left,up,right) -> Loc(Section((rev left) @ (t::right)),up);;

let go_down (Loc(t,p)) = match t with
    Item(_) -> failwith "down of item"
  | Section(t1::trees) -> Loc(t1,Node([],p,trees))
  | _ -> failwith "down of empty";;

我们可以利用这些原语编写访问当前树的第$n$个儿子的函数.

let nth loc = nthrec
  where rec nthrec = function
    1 -> go_down(loc)
  | n -> if n>0 then go_right(nthrec (n-1))
                else failwith "nth expects a positive integer";;

第2.3节 改变, 插入, 和删除

我们可以局部地改变当前位置的结构:

let change (Loc(_,p)) t = Loc(t,p);;

向左或者向右插入是自然且廉价的:

let insert_right (Loc(t,p)) r = match p with
    Top -> failwith "insert of top"
  | Node(left,up,right) -> Loc(t,Node(left,up,r::right));;

let insert_left (Loc(t,p)) l = match p with
    Top -> failwith "insert of top"
  | Node(left,up,right) -> Loc(t,Node(l::left,up,right));;

let insert_down (Loc(t,p)) t1 = match t with
    Item(_) -> failwith "down of item"
  | Section(sons) -> Loc(t1,Node([],p,sons));;

我们可能也想要实现一个删除原语. 我们可以选择可能的话就向右移动, 否则就向左移动, 以及在空表的情形下向上移动.

let delete (Loc(_,p)) = match p with
    Top -> failwith "delete of top"
  | Node(left,up,r::right) -> Loc(r,Node(left,up,right))
  | Node(l::left,up,[]) -> Loc(l,Node(left,up,[]))
  | Node([],up,[]) -> Loc(Section[],up);;

我们应该注意到delete并非一个简单的操作.

我们相信以上的数据类型和操作足以用来以应用性但高效的方式编写一个结构编辑器的内核.

第3章 基本想法的变体

第3.1节 伤疤

如果一个算法的某个频繁操作需要在树中先上再下到相同的位置, 那么总是闭合section是很浪费时间的 (也浪费空间和垃圾回收时间, 等等). 或许在结构中留下伤疤会比较好, 其允许直接访问之前记下来的已访问位置. 因此, 我们将(非空的)section替换为记忆了一个树和其兄弟的三元组:

type memo_tree =
    Item of item
  | Siblings of memo_tree list * memo_tree * memo_tree list;;

type memo_path =
    Top
  | Node of memo_tree list * memo_path * memo_tree list;;

type memo_location = Loc of memo_tree * memo_path;;

基于这些新的结构, 我们可以呈现简化了的上下操作.

let go_up_memo (Loc(t,p)) = match p with
    Top -> failwith "up of top"
  | Node(left,p',right) -> Loc(Siblings(left,t,right),p');;

let go_down_memo (Loc(t,p)) = match t with
    Item(_) -> failwith "down of item"
  | Siblings(left,t',right) -> Loc(t',Node(left,p,right));;

修改其他原语的任务则留给读者完成.

第3.2节 一阶项

到目前为止, 我们的结构完全是无类型的——甚至我们的树结点都没有标签. 我们有了某种LISP风格的结构编辑器, 但是更多地面向拼接 (splicing)操作而非通常的rplaca和rplacd原语.

如果我们想要为抽象句法树实现一种树操纵编辑器, 那么我们需要标记树结点以运算符名称. 如果我们为此目的使用item, 那么这意味着采用通常的LISP对于一阶项的编码方式: $F(T_1,\dots ,T_n)$被编码为树Section[Item(F); T1; ...; Tn]. 一种与之对偶的解决方案, 由组合子逻辑所启发, 其中的类组合子结构遵循应用的顺序: Section[Tn; ...; T1; Item(F)]. 然而, 这两种方案都不尊重元数 (arity).

这里我们不会再追究这种一般性变体形式的细节, 而是考虑如何使zipper的想法适应于特定的给定了元数的运算符的签名, 要求树编辑能够维护相对于元数的良形式性 (well-formedness).

基本上, 对于签名的每个$n$元构造子$F$, 我们都联系以$n$个路径运算符$\mathrm{Node}(F,i)$, 其中$1\le i\le n$且每个运算符的元数都是$n$, 它们是用来下到一个$F$项的第$i$个子项的. 更精确地说, 每个$\mathrm{Node}(F,i)$具有一个路径参数和$n-1$个项参数用于保存当前焦点的兄弟.

以下我们展示了对应于二叉树的结构:

type binary_tree =
    Nil
  | Cons of binary_tree * binary_tree;;

type binary_path =
    Top
  | Left of binary_path * binary_tree
  | Right of binary_tree * binary_path;;

type binary_location = Loc of binary_tree * binary_path;;

let change (Loc(_,p)) t = Loc(t,p);;

let go_left (Loc(t,p)) = match p with
    Top -> failwith "left of top"
  | Left(father,right) -> failwith "left of Left"
  | Right(left,father) -> Loc(left,Left(father,t));;

let go_right (Loc(t,p)) = match p with
    Top -> failwith "right of top"
  | Left(father,right) -> Loc(right,Right(t,father))
  | Right(left,father) -> failwith "right of Right";;

let go_up (Loc(t,p)) = match p with
    Top -> failwith "up of top"
  | Left(father,right) -> Loc(Cons(t,right),father)
  | Right(left,father) -> Loc(Cons(left,t),father);;

let go_first (Loc(t,p)) = match t with
    Nil -> failwith "first of Nil"
  | Cons(left,right) -> Loc(left,Left(p,right));;

let go_second (Loc(t,p)) = match t with
    Nil -> failwith "second of Nil"
  | Cons(left,right) -> Loc(right,Right(left,p));;

二叉树上高效的破坏性算法可以用这些全然应用性的原语编写. 这些原语都只需要常量时间, 因为它们都可以被归结为局部的指针操纵.