19.5　杂项

本节会探讨两个关于函数式和引用透明性的比较复杂的问题，一个是效率，另一个关乎返回一致的结果。这些都是非常有趣的问题，直到现在才讨论是因为它们通常都由副作用引起，并非我们要介绍的核心概念。我们还会探究结合器的思想——即接受两个或多个方法（函数）做参数且返回结果是另一个函数的方法。这一思想直接影响了新增到Java 8中的许多API和最近以来Java 9中的Flow API。

19.5.1　缓存或记忆表

假设你有一个无副作用的方法omputeNumberOfNodes(Range)，它会计算一个树形网络中给定区间内的节点数目。让我们假设该网络不会发生变化，即该结构是不可变的，然而调用computeNumberOfNodes方法的代价是非常昂贵的，因为该结构需要执行递归遍历。不过，你可能需要多次地计算该结果。如果你能保证引用透明性，那么有一种聪明的方法可以避免这种冗余的开销。解决这一问题的一种比较标准的方案是使用记忆表（memoization）——为方法添加一个封装器，在其中加入一块缓存（比如，利用一个HashMap）——封装器被调用时，首先查看缓存，看请求的“(参数,结果)对”是否已经存在于缓存中。如果已经存在，那么方法直接返回缓存的结果；否则，你会执行computeNumberOfNodes调用，不过从封装器返回之前，你会将新计算出的“(参数,结果)对”保存到缓存中。严格地说，这种方式并非纯粹的函数式解决方案，因为它会修改由多个调用者共享的数据结构，不过这段代码的封装版本的确是引用透明的。

实际操作上，这段代码的工作如下：

  1. final Map<Range,Integer> numberOfNodes = new HashMap<>();
  2. Integer computeNumberOfNodesUsingCache(Range range) {
  3.     Integer result = numberOfNodes.get(range);
  4.     if (result != null){
  5.         return result;
  6.     }
  7.     result = computeNumberOfNodes(range);
  8.     numberOfNodes.put(range, result);
  9.     return result;
  10. }

注意　Java 8改进了Map接口，提供了一个名为computeIfAbsent的方法来处理这样的情况。附录B会介绍这一方法。但是，我们在这里也提供一些参考，你可以用下面的方式调用computeIfAbsent方法，以编写出结构更加清晰的代码：

  1. Integer computeNumberOfNodesUsingCache(Range range) {
  2.     return numberOfNodes.computeIfAbsent(range,
  3.                                          this::computeNumberOfNodes);
  4. }

很明显，方法computeNumberOfNodesUsingCache是引用透明的（假设computeNumberOfNodes也是引用透明的）。不过，事实上，numberOfNodes处于可变共享状态，并且HashMap也没有同步 4，这意味着该段代码不是线程安全的。如果多个核对numberOfNodes执行并发调用，即便不用HashMap，而是用（由锁保护的）Hashtable或者（并发无锁的）ConcurrentHashMap，可能都无法达到预期的性能，因为这中间又存在由于发现某个值不在Map中，需要将对应的“(参数,结果)对”插回到Map而引起的竞态条件。这意味着多个核上的进程可能算出的结果相同，又都需要将其加入到Map中。

4这是极其容易滋生缺陷的地方。我们很容易随意地使用HashMap，却忘记了Java文档中的提示，这一数据结构不是线程安全的（或者简单地说，由于我们的程序是单线程的，而毫无顾忌地使用）。

从刚才讨论的各种纠结中，我们能得到的最大收获可能是，一旦并发和可变状态的对象揉到一起，它们引起的复杂度要远超我们的想象，而函数式编程能从根本上解决这一问题。当然，这也有一些例外，比如出于底层性能的优化，可能会使用缓存，而这可能会有一些影响。另一方面，如果不使用缓存这样的技巧，如果你以函数式的方式进行程序设计，那就完全不必担心你的方法是否使用了正确的同步方式，因为你清楚地知道它没有任何共享的可变状态。

19.5.2　“返回同样的对象”意味着什么

再次回顾一下19.2.3节中二叉树的例子。图19-4中，变量t指向了一棵现存的树，依据该图，调用fupdate(fupdate("Will",26, t)会生成一棵新树，假设该树会被赋给变量t2。通过该图，我们非常清楚地知道变量t，以及所有它可达的数据结构都是不会变化的。现在，假设你在新增的赋值操作中执行一次字面上和上一操作完全相同的调用，如下所示：

  1. t3 = fupdate("Will", 26, t);

这时t3会指向第三个新创建的节点，该节点包含了和t2一样的数据。那么，问题来了：fupdate是否符合引用透明性原则呢？引用透明性原则意味着“使用相同的参数（即这个例子的情况）产生同样的结果”。问题是t2和t3属于不同的对象引用，所以(t2==t3)这一结论并不成立，这样说起来你只能得出一个结论：fupdate并不符合引用透明性原则。虽然如此，使用不会改动的持久化数据结构时，t2和t3在逻辑上并没有差别。对于这一点我们已经辩论了很长时间，不过最简单的概括可能是函数式编程通常不使用==（引用相等），而是使用equal对数据结构值进行比较，由于数据没有发生变更，因此这种模式下fupdate是引用透明的。

19.5.3　结合器

函数式编程时编写高阶函数是非常普通且自然的事。高阶函数接受两个或多个函数，并返回另一个函数，实现的效果在某种程度上类似于将这些函数进行了结合。术语结合器通常用于描述这一思想。Java 8中的很多API都受益于这一思想，比如CompletableFuture类中的thenCombine方法。该方法接受两个CompletableFuture方法和一个BiFunction方法，返回另一个CompletableFuture方法。

虽然深入探讨函数式编程中结合器的特性已经超出了本书的范畴，但是了解结合器使用的一些特例还是非常有价值的，它能让我们切身体验函数式编程中构造接受和返回函数的操作是多么普通和自然。下面这个方法就体现了函数组合（function composition）的思想：

  1. static <A,B,C> Function<A,C> compose(Function<B,C> g, Function<A,B> f) {
  2.     return x -> g.apply(f.apply(x));
  3. }

它接受函数f和g作为参数，并返回一个函数，实现的效果是先做f，接着做g。你可以接着用这种方式定义一个操作，通过结合器完成内部迭代的效果。让我们看这样一个例子，你希望接受一个参数，并使用函数f连续地对它进行操作（比如n次），类似循环的效果。我们将你的操作命名为repeat，它接受一个参数f，f代表了一次迭代中进行的操作，它返回的也是一个函数，其会在n次迭代中执行。像下面这样一个方法调用

  1. repeat(3, (Integer x) -> 2*x);

形成的效果是x ->(2*(2*(2*x)))或者x -> 8*x。

你可以通过下面这段代码进行测试：

  1. System.out.println(repeat(3, (Integer x) -> 2*x).apply(10));

输出的结果是80。

你可以按照下面的方式编写repeat方法（请特别留意0次循环的特殊情况）：

  1. static <A> Function<A,A> repeat(int n, Function<A,A> f) {
  2.     return n==0 ? x -> x    ←---- 如果n的值为0，直接返回“什么也不做”的标识符
  3.                          : compose(f, repeat(n-1, f));    ←---- 否则执行函数f，重复执行n-1次，紧接着再执行一次
  4. }

将这个想法稍作变更便可以对迭代概念的更丰富外延进行建模，甚至包括在迭代之间传递可变状态的函数式模型。不过，由于篇幅有限，我们就不再继续展开讨论了。本章的目标只是做一个概率的总结，让大家对Java 8的基石函数式编程有一个全局的观念。市面上还有很多优秀的书，其对函数式编程进行了更深入的介绍，大家可以选择适合的进一步学习。