多年来，我一直在 Java 应用程序中使用域对象树。最近，我开始在 Clojure 中使用域对象树。无论使用哪种语言，访问者模式都是操作树形数据的一种可靠工具。但这种模式在函数语言和面向对象语言中的工作方式不同，所得到的结果也有所不同。

在这篇文章中，我回顾了域树（domain trees）和 Java 语言的访问者模式，随后介绍了使用 Clojure 的几种访问者实现。作为一种函数式语言，Clojure 为数据查询和操作提供了新方法。具体来说，我发现将函数式 zippers 集成到访问者模式之中会带来效率方面的优势，我将对此加以讨论。

操作符号树

符号树的一个示例就是 SQL 查询计划的表示形式，该查询提供筛选、连接、联合和 project 等操作。这些操作共同构成了从源数据开始的一系列计算，最终得到查询结果。

举例来说，清单 1 中的查询描述了 Dept 和 Employee 表的连接。该查询筛选了部门名称为 “IT” 的部分结果，并返回了一名员工姓氏和名字的连接。其结果应为 IT 部门中所有员工的全名。

				
SELECT Employee.First || ' ' || Employee.Last
FROM Dept, Employee
WHERE Dept.ID = Employee.Dept_ID
  AND Dept.Name = 'IT'

随后，我们可以查看 图 1，其中展示了这个查询计划的等效符号树表示形式。从概念上来说，关系数据行（元组）按照自下向上的方式流过查询计划中的操作节点。随后自顶向下地提取本查询的最终结果。

在使用类似于此的节点树时，我们需要对树整体执行操作。可能的操作包括：

• 集合查询计划中引用的所有表。
• 集合一个子树中使用的所有列。
• 查找一个查询计划中的顶级连接节点。
• 匹配树中的模式，并修改树。

最后一项操作尤为有用，因为它允许我们在树上执行符号操作。我们将首先利用 Filter Pushdown 模式来匹配图中的某个模式，随后在匹配的点对树进行修改。要匹配的 Filter Pushdown 模式如下所示：

• Filter 节点 F 在 Join 节点 J 的上方。
• F 的过滤条件仅涉及一个表。
• J 是一个内部连接。

随后，我们可以应用一项树操作，将 Join 节点下方的 Filter 节点朝着相关 Table 节点的方向移动。此类操作（由恰当的关系理论作为支持）是数据库查询优化器的核心所在。所得到的树如图 2 所示：

访问者模式往往用于将数据结构（本例中是树）与通过数据结构操作的算法分离开来。在本文稍后的内容中，我将演示使用 Java 代码的面向对象的实现以及 Clojure 中的函数式变体。

回页首

Java 语言中的访问者

在 Java 中，如果希望实现访问者模式，首先需要将节点表示为 Java 类。我们可以构建一个基本的层次结构，如图 3 所示。大多数这种类都是简单的数据容器。举例来说，Join 类包含一个左连接表达式、一个右连接表达式、一个连接类型和一个连接标准。

请注意，域层次结构中的所有对象都实现了 Visitable 接口和 acceptVisitor 方法，如下所示：

public void acceptVisitor(Visitor visitor) {
  visitor.visit(this);
}

这个 acceptVisitor 方法实现了双重分派，允许选择使方法调用不仅依赖具体的对象类型，还依赖于访问者类型。

访问者类如图 4 所示。基本 Visitor 接口为域中的每个具体类型都提供了一个访问方法。AbstractVisitor 实现所有这些方法的空版本，以便简化具体访问者的编写。

访问者导航

除了访问各节点之外，访问者还必须决定应将哪些节点作为当前节点的子节点访问。可以在每个访问者内包含导航，但最好将导航和操作这两个关注点分隔开来。实际上，您可以将按照类型查找子节点的操作视为可封装在访问者自身中的访问者操作。NavigationVisitor 可捕捉树导航操作，并带来更加轻量级的访问者。

请查看 NavigationVisitor 的方法：

public void visit(Join j) {
    visitor.visit(j);
    j.getCriteria().acceptVisitor(this);
    j.getLeft().acceptVisitor(this);
    j.getRight().acceptVisitor(this);
  }

NavigationVisitor 从属于另一个访问者实例，但嵌套了一些子导航。一个示例访问者可收集整个树内的全部 Column 实例，如 清单 2 中所示：

				
package visitors;

import java.util.HashSet;
import java.util.Set;

import visitors.domain.Column;

public class CollectColumnsVisitor extends AbstractVisitor {
  private final Set<Column> columns = new HashSet<Column>();
  
  public Set<Column> getColumns() {
    return this.columns;
  }
  
  @Override
  public void visit(Column c) {
    columns.add(c);
  }
}

这个访问者在树中发现一个 Column 时，它会将其存储在目前已经发现的所有列的集合中。在访问者完成后，我们可以检索 Column 的完整集合，如清单 3 所示：

				
Node tree = createTree();
CollectColumnsVisitor colVisitor = new CollectColumnsVisitor();
NavigationVisitor v = new NavigationVisitor(colVisitor);
tree.acceptVisitor(v);
System.out.println("columns = " + colVisitor.getColumns());

有了这个基本结构之后，就可以添加以下任何优化：

• 导航访问者，执行向前、向后或自定义导航
• 避免遍历整个树
• 在访问树的同时改变树

回页首

Java 访问者中附带的复杂性

Java 语言中的访问者模式专门解决经典的表达式问题。表达式问题这个词是由 Philip Wadler 定义的，它将一个程序的数据定义为一组用例（类型）和对于这些用例的一组操作。假设它们是表的两个维度。那么您能否在不需重新编译而且保持静态类型的前提下添加新数据类型和新操作？

访问者模式将创建一个场景，简化对现有数据类型集合添加操作（新访问者）的过程。然而，通过访问者添加新数据类型（类）较为困难，因为访问者模式要求所有具体类型都具有一个 visit() 方法。您可以使用一个抽象超类，在其中包含所有访问者的所有类的空实现，从而略微缓解难度。在这种情况下，您仅需修改抽象类，代码将完成编译。访问者不满足无需重新编译的标准，但确实能够将添加新操作所需的更改降低至最低限度。如果您认为，需要添加新类型的情况比添加新操作要少得多，那么整体模式就能达到良好的权衡：无疑比在所有具体类型上在一个新方法内编写一个新操作要容易得多。

尽管 Java 语言中的访问者模式实现允许我们满足一些基本的目标，但也会带来一些无法避免的复杂性：所有具体类中的样板 visit() 方法、定义导航访问者等等。利用 Clojure 的函数式编程工具来实现访问者模式是消除这种附带的复杂性的一种方法，而且仍然是在 JVM 上编程。

回页首

Clojure 中的树

Clojure 提供了一组核心的持久、不可变的数据结构：列表、矢量、映射、集合和队列。请注意，这里的持久 表示的是数据修改的一种属性，而并非数据存储。

在一个持久数据结构 “被修改” 时，数据不会改变。而是返回该数据结构的一个新的不可变版本。结构共享 这种技术使 Clojure 的持久数据结构更加高效。结构共享依靠数据的不可变性使数据新旧实例之间的共享成为可能。

不可变性还允许我们简化有关并发性的推理，并提供读取共享数据的低成本方法。如果数据不可变，则可在无需获得锁的前提下读取该数据。如果其他某些线程 “更改了” 数据，则结果将得到该数据的不同实例，这种实例可能共享大体相同的内部结构。在函数式编程语言中，持久数据结构对于编写纯粹的函数（无负面作用）的意义也是十分重要的。

Clojure 的持久数据结构

持久化基本链表数据结构是最简单的；在这里，Clojure 中的一个列表绑定到一个名为 “a” 的变量：

(def a (list 1 2 3))

Clojure 是一种 Lisp 变体，因此计算过程首先将一个表达式读取为 Clojure 数据结构（通常是一个列表），随后计算数据结构中的各表达式。最后，我们将列表中的第一个项作为函数调用，并将其他项作为参数。特殊形式 “def” 将创建一个带有名称空间的变量，该变量使用第一个符号标识，值是紧随其后的表达式。这个链表中的每个值都保存在包含一个值和指向下一个单元格的指针的（或者标记列表末尾的 nil）的单元格中，如图 5 所示：

如果我们随后在列表头部添加了一个新值，则称为构造一个新列表。新列表将共享原始链表中的所有单元格：

(def b (cons 4 a))

我们可以使用 rest 或其他函数来访问列表的其他部分，但通过原始列表创建的新列表仍然共享原始结构。对列表（以及其他值序列）进行操作的两个关键函数是 first（返回第一项）和 rest（返回其余项的清单）。

(def c (cons 5 (rest a)))

与 Java 数据结构相比，我们使用 Clojure 数据结构的方式的主要差异在于不会原地更改它们，而是描述一个更新，并获得对一个体现了变更的不可变结构的新引用。在考虑每个节点都是一个不可变数据结构的节点树时，我们必须考虑如何修改树内的一个节点或多个节点，而不必更改整个树。

树节点

在考虑树操作问题之前，让我们来看看将用于定义树的各个节点的数据结构。我们需要为每种节点类型提供一组定义良好的属性。树的每个节点最好具有一个对于 Clojure 可见的类型，以便在运行时选择函数实现时使用。

在考虑一组键和值的时候，Clojure 中最显而易见的选择就是 map，map 中存储着键值对。清单 4 中的代码示例展示了如何创建一个 map、为其添加值以及从中获 map：

				
user> (def alex {:name "Alex" :eyes "blue"})
#'user/alex
user> alex
{:name "Alex", :eyes "blue"}
user> (:name alex)
"Alex"
user> (assoc alex :married true)
{:married true, :name "Alex", :eyes "blue"}
user> alex
{:name "Alex", :eyes "blue"}

该 map 中的每个键都是一个 Clojure 关键字，计算结果始终得到自身，并且与其他任何位置所用的相同关键字完全相同。在 map 中将关键字作为键使用是合乎常理的。关键字也是函数。在通过 map 调用时，关键字函数将在 map 中查找自身，并返回自己的值。

为 map 添加项是通过 assoc（“associate”）实现的，而移除项是通过 dissoc（“dissociate”）实现的。如果打印一个 map，您可以看到 map 项之间的逗号，但这些逗号纯粹是为了可读性而添加的；在 Clojure 中，逗号将被作为空格处理。在 清单 4 的末尾处，assoc 将返回并打印一个新 map，但原始 map 将保持不变。两个 map 将在结构上共享大多数相同的数据。

有类型的 map

清单 5 展示了一些 helper 函数，这些函数可用于创建带有众所周知的 :type 键的 map。稍后，我们将利用这种类型来分派多态行为。node-type 函数根据 :type 键提取一个节点的 “类型”。

				
(ns zippers.domain
  (:require [clojure.set :as set]))

(defn- expected-keys? [map expected-key-set]
  (not (seq (set/difference (set (keys map)) expected-key-set))))

(defmacro defnode
  "Create a constructor function for a typed map and a well-known set of
   fields (which are validation checked). Constructor will be
     (defn new-&node-type> [field-map])."
  [node-type [& fields]]
  (let [constructor-name (symbol (str "new-" node-type))]
    `(defn ~constructor-name [nv-map#]
       {:pre [(map? nv-map#)
              (expected-keys? nv-map# ~(set (map keyword fields)))]}
       (assoc nv-map# :type (keyword '~node-type)))))

(defn node-type [ast-node] (:type ast-node))

您可能在 清单 5 中看到了许多新增的高级特性，但不必烦恼！本文提出这段代码只是供高级 Lisp 或 Clojure 程序员参考，这些代码并不是理解所有细节所必不可少的。这个清单的核心是 defnode 宏，它获取一个节点类型和一个字段名矢量，并创建一个构造函数来创建该类型的映射。在调用此构造函数时，字段将被传入，构造函数将检查字段来确定其是否与预期字段匹配，如果不匹配则抛出一个错误。作为 Lips 的一种变体，Clojure 的优势之一就是代码即数据（也称为同像（homoiconicity））。宏利用这种事实，在求值之前将代码作为数据操作。

清单 6 实现了与 Java 域类同等的 Clojure 域类型：

				
(defnode column [table column])
(defnode compare-criteria [left right])
(defnode concat [args])
(defnode filter [criteria child])
(defnode join [type left right])
(defnode project [projections child])
(defnode table [name])
(defnode value [value])

遍历树

我们现在的挑战在于获得一个 Clojure map 树，并遍历或操作该树。由于 Clojure 树是不可变的数据结构，因此任何操作都需要返回一个经过修改的新树。第一步，我们可以回顾访问者模式的 Java 语言实现，并尝试进行类似的实现。我们需要定义一个操作来遍历映射树、在树中搜索一个模式，并在该点应用一项操作。

举例来说，我们可以搜索带有全部字符串值的 concat 函数，随后将参数连接为一个字符串值，如图 8 所示：

与 Java 访问者解决方案相似，我们可以利用一个多重方法（multimethod），为树中的每一个节点类型实现一个 eval-concat 操作。在 Clojure 中，多重方法 是一种特殊的函数类型，它能将调用拆分为两个步骤。在函数被调用时，使用该函数的参数对一个自定义的分派函数求值。随后，利用所得到的 dispatch-value 在多种可能的函数实现中选择一种。

(defmulti <function-name> <dispatch-function>)
(defmethod <function-name> <dispatch-value> [<function-args>] <body>)

多重方法由两个宏定义：defmulti 和 defmethod。这些宏由 <function-name> 绑定在一起。defmulti 宏指定在初次调用时要使用的分派函数，另外还有其他一些可选特性。defmethod 实现将有多个，每个实现指定触发执行的一个 dispatch-value，另外还包含一个将在触发时执行的函数体。

按照类型分派

Clojure 最常见的分派函数就是 class 函数，函数调用的实现基于传递给多重方法的独立函数参数的类型。

在我们的示例中，每个节点都是一个 map，我们希望使用 node-type 函数来区分代表各节点的不同类型的映射。随后，我们利用 defmethod 为希望处理的每种类型创建多重方法的实现。

如果分派函数无法确定任何匹配多重方法的可能性，则将调用一个 :default 分派值（假设存在）。在我们的示例中，我们使用 :default 实现来指定所有未加入列表的节点都应无修改地返回自身。这将作为一种有用的基本用例，类似于经典访问者模式中的基本 Visitor 类。

清单 7 是 eval-concat 多重方法的完整实现。在本例中，您看到了 new-concat 和 new-compare-criteria 等函数的用法，它们是由我们在 清单 5 中调用的 defnode 宏创建的。

				
(defmulti eval-concat node-type)
(defmethod eval-concat :default [node] node)
(defmethod eval-concat :concat [concat]
           (let [arg-eval (map eval-concat (:args concat))]
             (if (every? string? arg-eval)
               (string/join arg-eval)
               (new-concat {:args arg-eval}))))
(defmethod eval-concat :compare-criteria [{:keys (left right) :as crit}]
           (new-compare-criteria {:left (eval-concat left)
                                  :right (eval-concat right)}))

清单 8 是 eval-concat 多重方法的一个应用示例。该示例构建了一个小的节点树，随后对这些节点执行多重方法 eval-concat，以查找字符串的 concat。随后又使用连接后的字符串替换这些字符串。

				
(def concat-ab (new-concat {:args ["a" "b"]}))
(def crit (new-compare-criteria {:left concat-ab
                                 :right "ab"}))

(eval-concat crit)

请注意， 清单 7 中的 eval-concat 仅仅是解决了我们的部分问题。为了获得完整的解决方法，我们需要为可能包含表达式的每个类创建一个 defmethod，从而得到一个 concat 节点。这并不困难，但十分繁琐。

具体来说，解决方案的最大 “重头戏” 在于遍历数据结构。所有实际的树修改操作均隔离在 :concat defmethod 中。将数据结构的遍历作为独立、一般的操作将更为理想。

使用 clojure.walk 进行数据遍历

Clojure 的核心 API 包含一个库，即 clojure.walk，这个库专门用于遍历数据结构。该库的功能基于名为 walk 的核心函数，但很少直接调用 walk。最常见的情况是通过 prewalk 和 postwalk 函数访问此功能。这两个函数均按照深度优先的顺序遍历树，但两者的差异在于先访问一个节点还是先访问其子节点。两个版本均在各节点应用一个函数来返回替换的节点（或原始节点）。

举例来说，清单 9 展示了一个异构数据树上的 postwalk 操作。我们首先遍历树，传递一个仅打印所访问的节点并返回该节点的函数。随后调用 postwalk，传入查找整数并将其递增 1 的函数，其他内容保持不变。

				
user> (def data [[1 :foo] [2 [3 [4 "abc"]] 5]])
#'user/data

user> (require ['clojure.walk :as 'walk])
nil

user> (walk/postwalk #(do (println "visiting:" %) %) data)
visiting: 1
visiting: :foo
visiting: [1 :foo]
visiting: 2
visiting: 3
visiting: 4
visiting: abc
visiting: [4 abc]
visiting: [3 [4 abc]]
visiting: 5
visiting: [2 [3 [4 abc]] 5]
visiting: [[1 :foo] [2 [3 [4 abc]] 5]]
[[1 :foo] [2 [3 [4 "abc"]] 5]]

user> (walk/postwalk #(if (number? %) (inc %) %) data)
[[2 :foo] [3 [4 [5 "abc"]] 6]]

利用 postwalk 和 prewalk 会获得很多好处，因为它们已经理解了如何遍历大多数核心 Clojure 数据结构，例如矢量、列表、集合和映射（例外包括排序映射和记录）。在使用 clojure.walk 时，我们不需要指定任何导航代码，只需提供查找要修改的节点并做出修改的重要代码即可。

让我们将 postwalk 应用于 清单 10 中的 eval-concat 问题。找到一个类型为 :concat 的节点时，我们将检查是否可对它进行求值，并返回一个新的值节点来取代原始的 :concat 节点。

				
(defn eval-concat [node]
  (if (and (= :concat (node-type node))
            (every? string? (:args node)))
     (string/join (:args node))
     node))

(defn walk-example
  [node]
  (walk/postwalk eval-concat node))

这种实现更令人满意。所有遍历操作均在 postwalk 内得到处理，我们只需提供查找和修改现有树的函数即可。

访问者模式中的递归

无论是原始的访问者模式，还是这种使用 postwalk 的实现，它们共有的问题就是模式是递归的（请参见 图 9）。在对一个节点的修改函数求值时，所有父节点的遍历都将进入堆栈。在访问者实现中可以清楚地看到这一点，您可以看到对 eval-concat 函数的所有递归调用。但即便这些调用在 postwalk 中得到了隐藏，结构仍然是相同的。

递归并不一定是坏事，它易于理解，在较小的树中也不易引起问题。但对于较大的树来说，我们更希望以迭代的方式遍历，从而节约内存。问题在于，我们能否在不使用递归的前提下实现访问者模式？

Clojure 的函数式 zippers

在函数式编程中，解决遍历和修改树的问题的一种知名的解决方法就是 zippers （zipper），因 Gérard Huet（参见 参考资料）的描述而闻名于世。 zippers 是使用本地上下文表示数据结构的一种方法，这使当前上下文中的导航（迭代）和修改在很大程度上具有常量时间的特点。所有更改都是在上下文本地做出的。

树 zippers 通常包含从根到树中当前位置的一条路径，另外还有关注节点的子树上下文。“ zippers ” 这个名称表示像拉链一样沿树上下移动，将关注节点上方的部分作为 zippers 的开口部分，本地状态作为闭合部分。

在典型的树中，常量时间访问仅可在根（其他代码引用的节点）处可用。 zippers 允许关注节点沿树移动，使您可在任意位置获得常量时间访问（不包括到达节点的遍历时间）。在考虑 zippers 时，通常可以将其视为由橡皮筋组成的树：您可以在任意节点 “拾取” 树，而该节点将成为类似于根的节点，具有连接关注节点的左路径、右路径和父路径。

关注节点数据结构通常引用为一个位置，或 “loc”。该位置包含当前子树和通往根的路径。考虑一个简化版的小型树结构，如 图 8 所示。这一次，我们将使用矢量而非 map，以便简化示例。

图 10 展示了在我们遍历树时位置结构发生了怎样的变化，在这里向下（始终下移至左侧第一个子节点），随后向右，然后再向下。在每一种情况下，新节点都会成为关注节点，而树的其他部分则表示为与关注节点相关的左节点、右节点和父节点。

遍历树时，更改是在当前关注节点的本地做出的，也就是说除了向上移动之外，所有操作都是常量时间的。这是 zippers 的关键优势。

Clojure 中的 zippers

Clojure 核心 API 的 clojure.zip 中包含一个出色的 zippers 实现，API 如 清单 11 中所示。我将 API 功能划分为几个类别：构造、上下文、导航、枚举和修改。

构造 函数允许您新建一个 zippers （即一个位置）。新建 zippers 的核心函数是 zipper，它基于三个关键函数：

• branch? 获取一个节点，并返回对该节点是否可能有子节点的判断。
• children 获取一个节点，并返回该节点的子节点。
• make-node 获取一个节点、一个新的子节点集合，并返回一个新的节点实例。

seq-zip、vector-zip 和 xml-zip 函数均为帮助函数，可使用预先定义的实现为序列、矢量和 XML 树调用 zipper。（这种实现不会解析 XML，而是希望得到由 clojure.xml/parse 产生的一种表示 XML 的数据结构。）

				
;; Construction
(zipper [branch? children make-node root]) - creates new zipper
(seq-zip [root]) - creates zipper made from nested seqs
(vector-zip [root]) - creates zipper made from nested vectors
(xml-zip [root]) - creates zipper from xml elements 

;; Context
(node [loc]) - return node at current location
(branch? [loc]) - return whether the location is a branch in the tree
(children [loc]) - return the children of a location’s node
(make-node [loc node children]) - make a new node for loc with the old node and the new 
   children
(path [loc]) - return a seq of nodes leading to this location from the root
(lefts [loc]) - return a seq of nodes to the left 
(rights [loc]) - return a seq of nodes to the right

;; Navigation
(left [loc]) - move to left sibling or return nil if none
(right [loc]) - move to right sibling or return nil if none
(leftmost [loc]) - move to leftmost sibling or self
(rightmost [loc]) - move to rightmost sibling or self
(down [loc]) - move to the leftmost child of the current location
(up [loc]) - move to the parent of the current location
(root [loc]) - move all the way to the root and return the root node 

;; Enumeration
(next [loc]) - move to the next node in a depth-first walk 
(prev [loc]) - move to the previous node in a depth-first walk
(end? [loc]) - at end of depth-first walk

;; Modification
(insert-left [loc item]) - insert a new left sibling
(insert-right [loc item]) - insert a new right sibling
(insert-child [loc item]) - insert a new leftmost child under current node
(append-child [loc item]) - inserts a new rightmost child under current node
(replace [loc node] - replaces the current node with a new node 
(edit [loc edit-fn args]) - replace the current node with the results of edit-fn
(remove [loc]) - remove the current node and moves to the previous node in a depth-first 
   walk

上下文 功能提供了有关树中当前位置的信息，导航 功能应直接基于之前的讨论。清单 12 展示了一个如何利用上下文和导航功能进入并检查树的示例：

				
> (def vz (zip/vector-zip [:compare [:concat "a" "b"] "ab"]))
> (println (zip/node (zip/down vz)))
:compare
> (println (zip/rights (zip/down vz)))
([:concat a b] ab)
> (println (zip/node (zip/right (zip/down vz))))
[:concat a b]
> (println (zip/node (zip/down (zip/right (zip/down vz)))))
:concat

zippers 迭代

zippers 的枚举 函数允许您按照深度优先的顺序遍历整个树，如 图 11 所示。这种遍历非常有趣，因为它是迭代的，而不是递归的，这是 zippers 遍历与之前的 clojure.walk 实现之间的主要差别。

使用 zippers 的树访问者

zippers 枚举和 zippers edit 函数为我们提供了构建基于 zippers 的访问者的工具，这包括迭代树并在各节点执行 visitor 函数。我们可以将这些工具整合在一起，如清单 13 所示：

				
(defn tree-edit [zipper matcher editor]
  (loop [loc zipper]
    (if (zip/end? loc)
      (zip/root loc)
      (if-let [matcher-result (matcher (zip/node loc))]
        (recur (zip/next (zip/edit loc (partial editor matcher-result))))
        (recur (zip/next loc))))))

tree-edit 函数获取一个 zipper 结构、一个 matcher 函数和一个 editor 函数。此函数从 Clojure 特殊形式的 loop 开始，它将为函数末尾处的 recur 创建一个目标。在 Clojure 中，loop/recur 表示尾递归，不像其他递归调用那样占用堆栈帧。在深度优先的树遍历中，zip/next 调用将迭代至下一个节点。

在 zip/end? 返回 true 时，迭代将终止。此时，zip/root 将 zip/up 至树顶端，在此过程中应用所有更改，并返回根节点。如果未终止，matcher 函数将应用于当前的 loc。如果匹配，则节点和 matcher 函数的结果将传递至 editor 函数，进行可能存在更改，迭代将从修改后的节点处继续。否则，迭代将从原始节点处继续。partial 函数局部地应用使用其参数子集的一个函数，并返回一个获取更少参数的新函数。在本例中，我们局部应用了 editor，使得 edit 能够获得具有恰当签名的一个新函数。

我们还需要一种 zippers 实现，它应能够在遍历过程中处理标准 Clojure 数据结构。清单 14 中的 tree-zipper 实现的函数支持核心集合类型，允许将通过这些类型构建的任何 Clojure 数据结构作为 zippers ：branch?、children 和 make-node。我选择为每个 zippers 函数使用一个多重方法，稍后，这将允许我动态地将此 zippers 扩展至其他类型，方法非常简单，只需添加新的 defmethod 实现即可。

				
(defmulti tree-branch? class)
(defmethod tree-branch? :default [_] false)
(defmethod tree-branch? IPersistentVector [v] true)
(defmethod tree-branch? IPersistentMap [m] true)
(defmethod tree-branch? IPersistentList [l] true)
(defmethod tree-branch? ISeq [s] true)

(defmulti tree-children class)
(defmethod tree-children IPersistentVector [v] v)
(defmethod tree-children IPersistentMap [m] (seq m))
(defmethod tree-children IPersistentList [l] l)
(defmethod tree-children ISeq [s] s)

(defmulti tree-make-node (fn [node children] (class node)))
(defmethod tree-make-node IPersistentVector [v children]
           (vec children))
(defmethod tree-make-node IPersistentMap [m children]
           (apply hash-map (apply concat children)))
(defmethod tree-make-node IPersistentList [_ children]
           children)
(defmethod tree-make-node ISeq [node children]
           (apply list children))
(prefer-method tree-make-node IPersistentList ISeq)

(defn tree-zipper [node]
  (zip/zipper tree-branch? tree-children tree-make-node node))

Concat 求值

在 清单 15 中，我们创建了一个 match 函数（用于查找具有字符串参数的连接节点）和一个 editor 函数（用于对连接求值），再次遇到了对 concat 函数求值的问题。can-simplify-concat 函数作为匹配函数，simplify-concat 函数则作为编辑器。

				
(defn can-simplify-concat [node]
  (and (= :concat (node-type node))
       (every? string? (:args val))))

(defn simplify-concat [_ node]
  (string/join (:args node)))

(defn simplify-concat-zip [node]
  (tree-edit (tree-zipper node) 
             can-simplify-concat 
             simplify-concat))

(simplify-concat-zip crit)

至此，我们已经达到了与 清单 10 中的 clojure.wal 实现几乎相同的复杂性水平。清单 10 与 清单 15 的差别之一就是遍历版本结合了 “匹配” 与 “编辑” 部件，这两个部件在 zippers 版本中是分离开来的。另外一项差异在于，在 zippers 版本内部使用的是数据结构的线性尾递归遍历，而非递归遍历。这减少了迭代过程中的内存占用，因为堆栈深度始终保持一致，而不依赖于树的高度。

更好的树访问者

在实践中，有用的访问者可分为几种常见的类别，具体取决于访问者的目标：

• Finder 搜索匹配某些标准的第一个节点，并返回该节点。
• Collector 搜索匹配某些标准的所有节点，并返回这些节点。
• Transformer 搜索树中的匹配项，在该点更改树，并返回该点。
• Event generator 遍历树并触发事件（设想 SAX 的 DOM）。

当然，在您开始实际使用并操作树时，您可能会发现这些类别的其他许多有趣的组合和扩展。我们目前的 tree-edit 函数不允许访问者指示迭代应停止，也不允许访问者在遍历过程中携带任何状态，因此在不使用外部状态容器的前提下创建 Finder 或 Collector 访问者较为困难。

在编写了大量访问者之后，另外一项观察发现就是功能的某些通用片段应可被多个访问者重用。举例来说，finder 和 collector 都需要在一个节点上评估一项条件，确定该节点是否匹配该条件。理想情况下，我们最好能为两种情况重用同一个完成此任务的函数。与此相似，创建能够检查将导致跳转到下一个节点或彻底取消迭代的情况的访问者也是非常有用的。

清单 16 展示了一个经过增强的访问者，它在各节点应用了一组访问者、在迭代过程中传递状态，并允许一个节点或整个迭代在早期退出。请注意这里使用的两个函数：

• tree-visitor 类似于前文所述的 tree-edit 函数。它通过 zippers 遍历树，并使用 end? 终止。在每个节点处，tree-visitor 都会调用我们的第二个函数 visit-node。tree-visitor 中的主要差别在于，visit-node 函数返回多个项目：一个 new-node、一个 new-state 和一个 stop 标记。如果 stop 为 true，则迭代将立即退出。状态通过 initial-state 预设，并在整个迭代过程中传递，允许访问者函数按照所需的任何方式操作状态。tree-visitor 结束时将同时返回最终状态和最终树。
• visit-node 获取一个访问者函数列表，其中每个函数都有一个返回上下文映射的签名（fn [node state]），上下文映射中可能包含键 :node、:state、:stop 或 :jump。如果返回了 :node 或 :state，则将取代传入的节点或状态。传递 :jump 表示迭代应跳转到下一个节点，并跳过此节点的所有剩余访问者。传递 :stop 表示应终止全部迭代。

				
(defn visit-node 
  [start-node start-state visitors]
  (loop [node start-node
         state start-state
         [first-visitor & rest-visitors] visitors]
    (let [context (merge {:node node, :state state, :stop false, :next false}
                         (first-visitor node state))
          {new-node :node
           new-state :state
           :keys (stop next)} context]
      (if (or next stop (nil? rest-visitors))
        {:node new-node, :state new-state, :stop stop}
        (recur new-node new-state rest-visitors)))))

(defn tree-visitor
  ([zipper visitors]
     (tree-visitor zipper nil visitors))
  ([zipper initial-state visitors]
     (loop [loc zipper
            state initial-state]
       (let [context (visit-node (zip/node loc) state visitors)
             new-node (:node context)
             new-state (:state context)
             stop (:stop context)          
             new-loc (if (= new-node (zip/node loc))
                       loc
                       (zip/replace loc new-node))
             next-loc (zip/next new-loc)]
         (if (or (zip/end? next-loc) (= stop true))
           {:node (zip/root new-loc) :state new-state}
           (recur next-loc new-state))))))

使用增强的访问者函数

利用全新、改进的访问者，我们可以做些什么？清单 17 展示了一个示例收集器，它将在我们的树中查找字符串。string-visitor 函数查找字符串节点，并返回捕捉该节点的更新后状态。string-finder 调用 tree-visitor 与 string-visitor，并返回最终状态。

				
(defn string-visitor
  [node state]
  (when (string? node)
    {:state (conj state node)}))

(defn string-finder [node]
  (:state
   (tree-visitor (tree-zipper node) #{} [string-visitor])))

我们也可以轻松地创建一个查找器，让我们来创建一个查找器，查找 清单 18 中某种类型的第一个节点。所匹配的函数类似于我们之前的访问者函数，但在开始时会获取一个要搜索的节点类型。在 find-first 调用访问者时，它会局部地应用类型 matched，得到一个仅获取 node 和 state 的函数。请注意，匹配的函数返回了 stop=true 以便退出迭代。

				
(defn matched [type node state]
  (when (of-type node type)
    {:stop true
     :state node}))

(defn find-first [node type]
  (:state
   (tree-visitor (tree-zipper node) [(partial matched type)])))

传递多个函数

至此，我们还没有真正用到传递多个函数的能力。此处的关键在于，我们希望将访问者中的功能分解为多个较小的片段，随后重新组合它们来构建复合功能。举例来说，在 清单 18 中，我们重写了 concat 求值程序，以便查找具有全部字符串（函数 2）的 :concat 节点（函数 1），随后对 concat 求值（函数 3）。

第一个类型求值程序访问器是在通用 “on” 函数中生成的。此函数返回一个匿名访问者函数，如果节点的类型不正确，则该函数将跳转到下一个节点。此函数完全可供可能需要按照类型对链接的其他部分求值的任何访问者链接重用。第二个 all-strings 函数生成了一个条件访问者，它将查找带有全部字符串参数的 concat 节点。

最后，我们创建一个多重方法来处理求值，即 eval-expr。在本例中，我们为所有内容采用的默认求值方式是返回其自身。我们添加了额外的 :concat 和 :compare-criteria 实现。这种多重方法又转为一个具有 node-eval 函数的访问者。

随后，即可在 chained-example 中轻而易举地将这个访问者链接组合为一个复合访问者，如 清单 19 所示：

				
(defn on [type]
  (fn [node state]
    (when-not (of-type node type)
      {:jump true})))

(defn all-strings []
  (fn [{args :args} _]
    (when-not (every? string? args)
      {:jump true})))

(defmulti eval-expr node-type)
(defmethod eval-expr :default [x] x)
(defmethod eval-expr :concat [{args :args :as node}]
           (string/join args))
(defmethod eval-expr :compare-criteria [{:keys (left right) :as node}]
           (if (= left right) true node))

(defn node-eval [node state]
  {:node (eval-expr node)})

(defn chained-example [node]
  (:node
   (tree-visitor (tree-zipper node)
                 [(on :concat)
                  (all-strings)
                  node-eval])))

可以轻松在其他访问者链接中使用此实现的某些片段（例如 on 和 node-eval 函数）。访问者链接的概念为在树中构造和重用访问者提供了一种具有丰富选项的灵活框架。

回页首

Clojure 访问者可帮助您事半功倍

这篇文章仅仅是涉及了在访问者模式中使用 zippers 的一些浅显问题；目的在于激发您进一步探索的兴趣。举例来说，您可能已经注意到，清单 18 中 on 和 all-strings 的结构非常相似。这两个函数均在访问者中包装了一个筛选器。我们不必将包含筛选器的函数链接在一起，只需在使用普通 Clojure 连接器建立的条件中包装一个筛选器访问者即可。用于创建和组合这些条件的自定义宏的添加将使代码编写过程更加轻松。

实际上，模式匹配库（例如全新的 Clojure core.match 库；参见 参考资料）允许您指定包含可在数据结构中找到匹配的通配符的模式。您可以轻松集成模式匹配库与树访问者，使访问者能够利用树模型。这进一步贴近了就事论事地讨论问题的目标，让语言本身不再成为阻碍。

就访问者模式而言，本文未加详述的另一各方面就是迭代顺序。在 Revelytix 中，我们始终按照 zippers 枚举深度优先的顺序遍历节点。在某些情况下，我们实际可能希望按照相反的顺序遍历这些节点、跳过某些节点或子树或其他一些内容。迭代实际上包含三种操作：start（从根节点处查找 start loc）；next（给定一个 loc，查找下一个 loc），以及 end?（当前 loc 是否是迭代的结尾？）。在我们当前的树访问者函数中可以轻松抽象这些函数，并支持预构建和自定义的迭代策略。

在 Clojure 中，所有代码均是存储为 s 表达式 树的数据。因此，您可以利用本文中所述的全部技术，不仅可修改您的数据，还可修改您的代码。在核心 Clojure API 的较为高级的宏实用工具中，您可以找到这些技术的一些示例。

希望您可以利用本文介绍的概念，在 Clojure 或您选择的语言中构建自己的访问者，并继续探索构造和操作数据的新方法。在 参考资料 部分中可以找到下载本文所用全部代码和示例的链接，这些内容都存在 Github 中。

致谢

我要感谢 Revelytix 的多位同事，他们开发了与本文所述代码相似的代码，并在我们自己的产品中使用这些代码。特别要感谢 David McNeil 抽出许多宝贵时间，在白板上与我探讨思路和解决方案，并在 Emacs 中进行配对，他还承担了扩展 clojure.walk、clojure.zip 和 matchure 等库的重任。

我还要感谢我的同事 Alex Hall，他注意到了我们的需要，并完成了后序迭代增强的实现。

参考资料

学习

• 在 developerWorks 上进一步了解 Clojure：
  • “Clojure 编程语言”（Michael Galpin，2009 年）
  • “Clojure 与并发性”（Michael Galpin，2010 年）
  • “通过 Clojure 1.2 解决表达式问题”（Stuart Sierra，2010 年）
  • “使用 CouchDB 与 Clojure”（Ryan Senior，2011 年）
  
  
• 查看 Wikipedia 中有关 zippers 的条目 以及 Haskell 的文档，获得关于 zippers 的概述。
  
  
• Gérard Huet 在文章 “函数式 Pearl： zippers ”（函数编程期刊，第 7 卷，Cambridge University Press，1997 年）中介绍了 zippers 的概念。
  
  
• 如需了解 有关 Clojure zippers 的更多信息，请观看 Luke VanderHart 在 Blip.tv 上做的视频演示（2010 年）。
  
  
• Brian Marick 所撰写的 “使用 clojure.zip 在 Clojure 中 ‘编辑’ 树”（Exploration Through Example，2010 年）是一份简单介绍 clojure.zip 的教程。
  
  
• 在 “模式匹配与预测分派”（David Nolen，NYC Clojure 用户组，2011 年）中获得关于 core.match 的简介。
  
  
• Philip Wadler 是一位 Haskell 首席设计师，他于 1998 年定义了 表达式问题，他还是贝尔实验室的一名研究人员。
  
  
• “理想的哈希树”（Philip Bagwell，Es Grands Champs，第 1195 卷，2001 年）介绍了 Clojure 持久数据结构的核心数据结构。
  
  
• developerWorks Java 技术专区：这里有数百篇关于 Java 编程各个方面的文章。
  
  

获得产品和技术

• 下载 本文的源代码和示例。
  
  
• 下载 core.match：经过优化的 Clojure 模式匹配和预测分派库。
  
  

讨论

• 加入 developerWorks 中文社区。查看开发人员推动的博客、论坛、组和维基，并与其他 developerWorks 用户交流。
  
  

关于作者

Alex Miller 是 Revelytix 的一名高级工程师，致力于开发联邦语义 Web 查询技术。他全职使用 Clojure 的经验已有两年。在加入 Revelytix 之前，Alex 曾任 Terracotta 的技术主管、BEA Systems 的工程师以及 MetaMatrix 的首席架构师。他的兴趣包括 Java、并发性、分布式系统、语言和软件设计。Alex 喜欢以 @puredanger 的身份发表微博，还喜欢在 http://tech.puredanger.com 上写博客。Alex 是 Strange Loop 开发人员会议的创办者，他还成立了 Lambda Lounge 小组来研究函数和动态语言。他喜欢吃墨西哥玉米饼。

为本文评分

评论

回页首

内容

• 操作符号树
• Java 语言中的访问者
• Java 访问者中附带的复杂性
• Clojure 中的树
• 遍历树
• Clojure 的函数式 zippers
• 使用 zippers 的树访问者
• 更好的树访问者
• Clojure 访问者可帮助您事半功倍
• 参考资料
• 关于作者
• 评论