19.2　持久化数据结构

本节会探讨函数式编程中如何使用数据结构。这一主题有各种名称，比如函数式数据结构、不可变数据结构，不过最常见的可能还要算持久化数据结构（不幸的是，这一术语和数据库中的持久化概念有一定的冲突，数据库中它代表的是“生命周期比程序的执行周期更长的数据”）。

我们应该注意的第一件事是，函数式方法不允许修改任何全局数据结构或者任何作为参数传入的结构。为什么呢？因为一旦对这些数据进行修改，两次相同的调用就很可能产生不同的结构——这违背了引用透明性原则，我们也就无法将方法简单地看作由参数到结果的映射。

19.2.1　破坏式更新和函数式更新的比较

让我们看看不这么做会导致怎样的结果。假设你需要使用一个可变类TrainJourney（利用一个简单的单向链接列表实现）表示从A到B的火车旅行，你使用了一个整型字段对旅程的一些细节进行建模，比如当前路途段的价格。旅途中你需要换乘火车，所以需要使用几个由onward字段串联在一起的TrainJourney对象。直达火车或者旅途最后一段对象的onward字段为null：

  1. class TrainJourney {
  2.     public int price;
  3.     public TrainJourney onward;
  4.     public TrainJourney(int p, TrainJourney t) {
  5.         price = p;
  6.         onward = t;
  7.     }
  8. }

假设你有几个相互分隔的TrainJourney对象分别代表从X到Y和从Y到Z的旅行。你希望创建一段新的旅行，它能将两个TrainJourney对象串接起来（即从X到Y再到Z）。

一种方式是采用简单的传统命令式的方法将这些火车旅行对象链接起来，代码如下：

  1. static TrainJourney link(TrainJourney a, TrainJourney b){
  2.     if (a==null) return b;
  3.     TrainJourney t = a;
  4.     while(t.onward != null){
  5.         t = t.onward;
  6.     }
  7.     t.onward = b;
  8.     return a;
  9. }

这个方法是这样工作的，它找到TrainJourney对象a的下一站，将其由表示a列表结束的null替换为列表b（如果a不包含任何元素，你则需要进行特殊处理）。

这就出现了一个问题：假设变量firstJourney包含了从X到Y的线路，另一个变量secondJourney包含了从Y到Z的线路。如果你调用link(firstJourney, secondJourney)方法，那么这段代码会破坏性地更新firstJourney，结果secondJourney也会被加入到firstJourney，最终请求从X到Z的用户会如其所愿地看到整合之后的旅程，不过从X到Y的旅程也被破坏性地更新了。这之后，变量firstJourney就不再代表从X到Y的旅程，而是一个新的从X到Z的旅程了！这一改动会导致依赖原先的firstJourney代码失效！假设firstJourney表示的是清晨从伦敦到布鲁塞尔的火车，这趟车上后一段的乘客本来打算要去布鲁塞尔，可是发生这样的改动之后他们莫名地多走了一站，最终可能跑到了科隆。现在你大致了解数据结构修改的可见性会导致怎样的问题了，作为程序员，我们一直在与这种缺陷作斗争。

函数式编程解决这一问题的方法是禁止使用带有副作用的方法。如果你需要使用表示计算结果的数据结构，那么请创建它的一个副本而不要直接修改现存的数据结构。这一最佳实践也适用于标准的面向对象程序设计。不过，对这一原则，也存在着一些异议，比较常见的是认为这样做会导致过度的对象复制，有些程序员会说“我会记住那些有副作用的方法”或者“我会将这些写入文档”。但这些都不能解决问题，这些“坑”都留给了接受代码维护工作的程序员。采用函数式编程方案的代码如下：

  1. static TrainJourney append(TrainJourney a, TrainJourney b){
  2.     return a==null ? b : new TrainJourney(a.price, append(a.onward, b));
  3. }

很明显，这段代码是函数式的（它没有做任何修改，即使是本地的修改），它没有改动任何现存的数据结构。不过，也请特别注意，这段代码有一个特别的地方，它并未创建整个新TrainJourney对象的副本——如果a是n个元素的序列，b是m个元素的序列，那么调用这个函数后，它返回的是一个由n+m个元素组成的序列，这个序列的前n个元素是新创建的，而后m个元素和TrainJourney对象b是共享的。另外，也请注意，用户需要确保不对append操作的结果进行修改，因为一旦这样做了，作为参数传入的TrainJourney对象序列b就可能被破坏。图19-2和图19-3解释说明了破坏式append和函数式append之间的区别。

19.2　持久化数据结构 - 图6

图 19-2　以破坏式更新的数据结构

19.2　持久化数据结构 - 图7

图 19-3　函数式，不会对原有数据结构进行改动

19.2.2　另一个使用Tree的例子

转入新主题之前，再看一个使用其他数据结构的例子——我们想讨论的对象是二叉查找树，它也是HashMap实现类似接口的方式。我们的设计中Tree包含了String类型的键，以及int类型的键值，它可能是名字或者年龄：

  1. class Tree {
  2.     private String key;
  3.     private int val;
  4.     private Tree left, right;
  5.     public Tree(String k, int v, Tree l, Tree r) {
  6.       key = k; val = v; left = l; right = r;
  7.     }
  8. }
  9. class TreeProcessor {
  10.     public static int lookup(String k, int defaultval, Tree t) {
  11.         if (t == null) return defaultval;
  12.         if (k.equals(t.key)) return t.val;
  13.         return lookup(k, defaultval,
  14.                          k.compareTo(t.key) < 0 ? t.left : t.right);
  15.     }
  16.     // 处理Tree的其他方法
  17. }

你希望通过二叉查找树找到String值对应的整型数。现在，想想你该如何更新与某个键对应的值（简化起见，假设键已经存在于这个树中了）：

  1. public static void update(String k, int newval, Tree t) {
  2.     if (t == null) { /* 应增加一个新的节点 */ }
  3.     else if (k.equals(t.key)) t.val = newval;
  4.     else update(k, newval, k.compareTo(t.key) < 0 ? t.left : t.right);
  5. }

对这个例子，增加一个新的节点会复杂很多。最简单的方法是让update直接返回它刚遍历的树（除非你需要加入一个新的节点，否则返回的树结构是不变的）。现在，这段代码看起来已经有些臃肿了（因为update试图对树进行原地更新，它返回的是跟传入的参数同样的树，但是如果最初的树为空，那么新的节点会作为结果返回）。

  1. public static Tree update(String k, int newval, Tree t) {
  2.     if (t == null)
  3.         t = new Tree(k, newval, null, null);
  4.     else if (k.equals(t.key))
  5.         t.val = newval;
  6.     else if (k.compareTo(t.key) < 0)
  7.         t.left = update(k, newval, t.left);
  8.     else
  9.         t.right = update(k, newval, t.right);
  10.     return t;
  11. }

注意，这两个版本的update都会对现有的树进行修改，这意味着使用树存放映射关系的所有用户都会感知到这些修改。

19.2.3　采用函数式的方法

那么这一问题如何通过函数式的方法解决呢？你需要为新的键–值对创建一个新的节点，除此之外还需要创建从树的根节点到新节点的路径上的所有节点。通常而言，这种操作的代价并不太大，如果树的深度为d，并且保持一定的平衡性，那么这棵树的节点总数是2d，这样你就只需要重新创建树的一小部分节点了。

  1. public static Tree fupdate(String k, int newval, Tree t) {
  2.     return (t == null) ?
  3.         new Tree(k, newval, null, null) :
  4.           k.equals(t.key) ?
  5.             new Tree(k, newval, t.left, t.right) :
  6.           k.compareTo(t.key) < 0 ?
  7.             new Tree(t.key, t.val, fupdate(k,newval, t.left), t.right) :
  8.             new Tree(t.key, t.val, t.left, fupdate(k,newval, t.right));
  9. }

这段代码中，我们通过一行语句进行的条件判断，没有采用if-then-else这种方式，目的是希望强调一个思想，那就是该函数体仅包含一条语句，没有任何副作用。不过你也可以按照自己的习惯，使用if-then-else这种方式，在每一个判断结束处使用return返回。

那么，update和fupdate之间的区别到底是什么呢？我们注意到，前文中方法update有这样一种假设，即每一个update的用户都希望共享同一份数据结构，也希望能了解程序任何部分所做的更新。因此，无论什么时候，只要你使用非函数式代码向树中添加某种形式的数据结构，请立刻创建它的一份副本，因为谁也不知道将来的某一天，某个人会突然对它进行修改，这一点非常重要（不过也经常被忽视）。与之相反，fupdate是纯函数式的。它会创建一个新的树，并将其作为结果返回，通过参数的方式实现共享。图19-4对这一思想进行了阐释。你使用了一个树结构，树的每个节点包含了person对象的姓名和年龄。调用fupdate不会修改现存的树，它会在原有树的一侧创建新的节点，同时保证不损坏现有的数据结构。

19.2　持久化数据结构 - 图10

图 19-4　对树结构进行更新时，现存数据结构不会被破坏

这种函数式数据结构通常被称为持久化的——数据结构的值始终保持一致，不受其他部分变化的影响——这样，作为程序员的你才能确保fupdate不会对作为参数传入的数据结构进行修改。不过要达到这一效果还有一个附加条件：这个约定的另一面是，所有使用持久化数据结构的用户都必须遵守这一“不修改”原则。如果不这样，忽视这一原则的程序员就很有可能修改fupdate的结果（比如，修改Emily的年纪为20岁）。这会成为一个例外（也是我们不期望发生的）事件，为所有使用该结构的方法感知，并在之后修改作为参数传递给fupdate的数据结构。

通过这些介绍，我们了解到fupdate可能有更加高效的方式：基于“不对现存结构进行修改”规则，对仅有细微差别的数据结构（比如，用户A看到的树结构与用户B看到的就相差不多），我们可以考虑对这些通用数据结构使用共享存储。你可以凭借编译器，将Tree类的字段key、val、left以及right声明为final执行，“禁止对现存数据结构的修改”这一规则。不过也需要注意final只能应用于类的字段，无法应用于它指向的对象，如果你想要对对象进行保护，则需要将其中的字段声明为final，以此类推。

噢，你可能会说：“我希望对树结构的更新对某些用户可见（当然，这句话的潜台词是其他用户看不到这些更新）。”那么，要实现这一目标，你可以通过两种方式：一种是典型的Java解决方案（对对象进行更新时，你需要特别小心，慎重地考虑是否需要在改动之前保存对象的一份副本）。另一种是函数式的解决方案：逻辑上，你在做任何改动之前都会创建一份新的数据结构（这样一来就不会有任何的对象发生变更），只要确保按照用户的需求传递给他正确版本的数据结构就好了。这一想法甚至还可以通过API直接强制实施。如果数据结构的某些用户需要进行可见性的改动，那么它们应该调用API，返回最新版的数据结构。对于另一些客户应用，它们不希望发生任何可见的改动（比如，需要长时间运行的统计分析程序），就直接使用它们保存的备份，因为它知道这些数据不会被其他程序修改。

有些人可能会说这个过程很像更新刻录光盘上的文件，刻录光盘时，一个文件只能被激光写入一次，该文件的各个版本分别被存储在光盘的各个位置（智能光盘编辑软件甚至会共享多个不同版本之间的相同部分），你可以通过传递文件起始位置对应的块地址（或者名字中编码了版本信息的文件名）选择你希望使用哪个版本的文件。在Java中，情况甚至比刻录光盘还好很多，不再使用的老旧数据结构会被Java虚拟机自动垃圾回收掉。