为了派生 zipper,我们首先编写更熟悉的深度优先遍历例程:
To derive zipper, we first write the familiar depth-first traversal routine:
Welcome to Scheme 48 1.1
> ,open srfi-9
> ,open escapes signals
> ,load /usr/local/lib/scheme48/misc/shift-reset.scm
; deterministic, left-to-right map
(define (map* f l)
(if (null? l) l
(cons (f (car l)) (map* f (cdr l)))))
(define (depth-first handle tree)
(cond
((null? tree) tree)
((handle tree) => (lambda (new-tree) new-tree))
; the node was not handled -- descend
((not (pair? tree)) tree) ; an atom
(else
(cons (car tree) ; node name
(map* (lambda (kid) (depth-first handle kid)) (cdr tree))))))
函数 handle
,作为 depth-first
的第一个参数,接受一个 node
并应该返回一个 node
或 #f
。在第一种情况下,返回的 node
替换结果树中的现有节点。如果 handle
返回 #f
,则表明它已拒绝处理该节点,因此我们保留该节点,在可能的情况下继续处理该节点的子节点。
The function handle, the first-argument of depth-first, receives a node and should yield either a node or #f. In the first case, the return node replaces the existing node in the result tree. If the handle returned #f, it has declined to handle that node, so we keep that node and descend into it, if possible.
为了解其工作原理,我们定义两个示例树并打印出它们的节点:
To see how this works, we define two sample trees and print out their nodes:
(define tree1 '(a (b) (c (d 1 2)) e))
(define tree2 '(z (u) (v (w 10 12)) y))
(depth-first (lambda (node) (display node) (newline) #f) tree1)
==> prints
(a (b) (c (d 1 2)) e)
(b)
(c (d 1 2))
(d 1 2)
1
2
e
==> yields
'(a (b) (c (d 1 2)) e)
我们现在可以定义数据类型 zipper:
We can now define the zipper data structure:
(define-record-type zzipper
(zipper curr-node k)
zipper?
(curr-node z-curr-node)
(k z-k))
它包含两个字段:树的当前节点和延续。延续应该接收一个 node
或 #f
。在前一种情况,接收到的节点将替换现有节点。在后一种情况,我们保留现有节点并继续遍历。这个延续返回一个新的 zipper
或一课树(如果遍历完成)。可以看出,zipper 在某种意义上是函数 handle
的“逆”。
It contains two fields: the current node of a tree, and the continuation. The continuation should receive a node or #f. In the former case, the received node will replace the existing node. In the latter case, we keep the existing node and continue the traversal. The continuation returns either a new zipper, or a tree (if the traversal is finished). One can see that zipper is in a sense an 'inverse' of the function handle.
(define (zip-tree tree)
(reset (depth-first (lambda (tree) (shift f (zipper tree f))) tree)))
正如所承诺的,zipper 确实是定界延续的一种表现形式。
As promised, zipper is indeed a manifestation of a delimited continuation.
我们应该指出,record zipper
和构造函数 zip-tree
都是 generic 的。它们本身既不依赖树的表示,也不依赖遍历策略。有关树数据结构及其遍历的所有信息都被封装在一个函数 depth-first
中。我们可以通过改变深度优先策略从深度优先策略切换到广度优先策略,或者从嵌套列表切换到树的嵌套向量实现。无论是 zipper
、zip-tree
还是任何使用 zipper
的代码(见下文)都不需要任何修改。我们的 zipper 的这一特性与 Gerard Huet 的 zipper 派生形成了鲜明的对比。在 Gerard Huet 的形式中,zipper 确实取决于数据类型的具体实现:zipper 是从数据类型 derived(双关语)的(译者按:派生和求导)。不同的数据类型(以及抽象数据类型的不同实现)将具有不同的对应 zipper 结构。在我们的形式中,zipper 是遍历函数的 generic
derivation(双关语)(译者按:派生和导数)。zipper 是遍历函数的导数——就只是机械的导数。因此,shift/reset 可以被视为遍历函数的导数运算符。
We should point out that both the zipper record and the constructor function zip-tree are _generic_. They by themselves depend neither on the representation of the tree nor on the traversal strategy. All the information about the tree data structure and its traversal is encapsulated in one single function depth-first. We can switch from depth-first to breadth-first strategy or from a nested list to a nested vector realization of trees just by changing depth-first. Neither zipper, nor zip-tree, nor any code that uses zipper (see below) will require any modifications. This property of our zipper is in a marked contrast with Gerard Huet's derivation of zipper. In Gerard Huet's formulation, zipper does depend on the concrete realization of the data type: zipper is derived (pun intended) from the data type. Different data types (and different realizations of an abstract data type) will have different corresponding zipper structures. In our formulation, zipper is a _generic_ derivation (pun intended) on the traversal function. Zipper is a derivative of the traversal function -- mechanical derivative at that. So, shift/reset can be considered traversal function derivative operators.