Using zippers to handle huge trees › zipper 的解释 Explanation of zippers [#261]

zipper 可以被视为一种“函数式指针”，因为它能够提供：
  • 纯 ( purely ) 的函数式和类型化的操作
  • O(1) 的访问指针元素
  • O(1) 的指针移动
 
Zippers may be seen as 'functional pointers' since they offer :
- purely functional and typed operations
- O(1) access to the pointed element
- O(1) pointer movements

限制是数据结构只允许有一个指针，且每次指针移动都会分配内存。 
The restrictions are that only one pointer is allowed by data structure and every pointer movement allocates memory.

采用二叉搜索树的经典类型声明 
Take a classical type declaration for binary search trees

type 'a tree = E | N of 'a tree * 'a * 'a tree * int

考虑一棵二叉搜索树和一个你想要指向的内部节点。要对指向的子树进行 O(1) 访问，它必须可以直接从数据结构的基础中获取。然后，树的其余部分必须保存在单独的地方。我们将沿着从根到指向的节点的路径来解构它 
Consider a binary search tree and an inner node to which you want to
point. To have a 0(1) access to the pointed subtree, it has to be
directly available from the base of the data structure. Then, the
rest of the tree must be kept in a separate place. We will deconstruct
it along the path from the root to the pointed node

type 'a path =
  | Root
  | Left of 'a * 'a tree * 'a path
  | Right of 'a tree * 'a * 'a path

type 'a zipper = 'a tree * 'a path

zipper 约束 ( constraints ) 声明如下：
  • 指向的子树
  • 沿着通往根的路径断开的树 的其余部分
 
The zipper constraint as announced :
- the pointed subtree
- the rest of the tree breaked along the path to the root

接着我们定义指针的移动（数据结构中的每个指针各一个）： 
Then we define the pointer movements (one for each pointer in the data structure) :

exception Bottom

(* To be replaced by a balancing constructor *)
let makeDTree = fun l v r -> N (l, v, r, 0)

let move_left = fun (tree, path) ->
  match tree with
    | E -> raise Bottom
    | N (l, v, r, _) -> (l, Left (v, r, path))

let move_right = fun (tree, path) ->
  match tree with
    | E -> raise Bottom
    | N (l, v, r, _) -> (r, Right (l, v, path))

let move_up = fun (tree, path) ->
  match path with
    | Root -> raise Top
    | Left (v, r, tail) -> (makeDTree tree v r, tail)
    | Right (l, v, tail) -> (makeDTree l v tree, tail)

现在我们可以通过以下过程构建任意大的树：
  • 构建一棵有界深度的树
  • 选择下一个要发展的节点
  • 移动当前指针到那个节点
  • 继续构建这课树
 
Now we can build an arbitrary large tree by the following procedure :
- build a tree of bounded depth
- choose the node which will be developed next
- move the current pointer to that node
- continue building the tree

该过程使用有界的堆栈空间。 
This procedure uses a bounded stack space