18.2　什么是函数式编程

对于“什么是函数式编程”这一问题最简化的回答是“它是一种使用函数进行编程的方式”。那什么是函数呢？

我们很容易想象这样一个方法，它接受一个整型和一个浮点型参数，返回一个浮点型的结果——它也有副作用，随着调用次数的增加，它会不断地更新共享变量，如图18-2所示。

图 18-2　带有副作用的函数

在函数式编程的上下文中，一个函数对应于一个数学函数：它接受零个或多个参数，生成一个或多个结果，并且不会有任何副作用。你可以把它看成一个黑盒，它接收输入并产生一些输出，如图18-3所示。

图 18-3　一个没有任何副作用的函数

这种类型的函数和你在Java编程语言中见到的函数之间的区别是非常重要的（我们无法想象，log或者 sin这样的数学函数会有副作用）。尤其是，使用同样的参数调用数学函数，它所返回的结果一定是相同的。这里暂时不考虑Random.nextInt这样的方法，稍后在介绍引用透明性时会讨论这部分内容。

当谈论函数式时，我们想说的其实是“像数学函数那样——没有副作用”。由此，编程上的一些精妙问题随之而来。我们的意思是，每个函数都只能使用函数和像if-then-else这样的数学思想来构建吗？或者，我们也允许函数内部执行一些非函数式的操作，只要这些操作的结果不会暴露给系统中的其他部分？换句话说，如果程序有一定的副作用，不过该副作用不会被其他的调用者感知，那么是否能假设这种副作用不存在呢？调用者不需要知道，或者完全不在意这些副作用，因为这对它完全没有影响。

当我们希望能界定这二者之间的区别时，会将前者称为纯粹的函数式编程（在本章的最后会讨论这部分内容），后者称为函数式编程。

18.2.1　函数式Java编程

编程实战中，你是无法用Java语言以纯粹的函数式来完成一个程序的。比如，Java的I/O模型就包含了带副作用的方法（调用Scanner.nextLine就有副作用，它会从一个文件中读取一行，通常情况两次调用的结果完全不同）。不过，你还是有可能为你系统的核心组件编写接近纯粹函数式的实现。在Java语言中，如果你希望编写函数式的程序，那么首先需要做的是确保没有人能觉察到你代码的副作用，这也是函数式的含义。假设这样一个函数或者方法，它没有副作用，进入方法体执行时会对一个字段的值加一，退出方法体之前会对该字段的值减一。对一个单线程的程序而言，这个方法是没有副作用的，可以看作函数式的实现。换个角度而言，如果另一个线程可以查看该字段的值——或者更糟糕的情况，该方法会同时被多个线程并发调用——那么这个方法就不能称之为函数式的实现了。当然，你可以用加锁的方式对方法的方法体进行封装，掩盖这一问题，你甚至可以再次声称该方法符合函数式的约定。但是，这样做之后，你就失去了在你的多核处理器的两个核上并发执行两个方法调用的能力。它的副作用对程序可能是不可见的，但对于程序员而言是可见的，因为程序运行的速度变慢了！

我们的准则是，被称为函数式的函数或方法都只能修改本地变量。除此之外，它引用的对象都应该是不可修改的对象。通过这种规定，我们期望所有的字段都为final类型，所有的引用类型字段都指向不可变对象。后续的内容中，你会看到我们实际也允许对方法中全新创建的对象中的字段进行更新，不过这些字段对于其他对象都是不可见的，也不会因为保存对后续调用结果造成影响。

我们前述的准则是不完备的，要成为真正的函数式程序还有一个附加条件，不过它在最初时不太被大家所重视。要被称为函数式，函数或者方法不应该抛出任何异常。关于这一点，有一个极为简单而又极为教条的解释：你不应该抛出异常，因为一旦抛出异常，就意味着结果被终止了；不再像之前讨论的黑盒模式那样，由return返回一个恰当的结果值。这里存在着一定的争执，有的作者认为抛出代表严重错误的异常是可以接受的，但是捕获异常是一种非函数式的控制流，因为这种操作违背了我们在黑盒模型中定义的“传递参数，返回结果”的规则，引出了代表异常处理的第三支箭头，如图18-4所示。

图 18-4　抛出一个异常的方法

函数式和局部函数式

在数学中，虽然合法的数学函数为每个合法的参数值返回一个确定的结果，但是很多通用的数学操作在严格意义上称之为局部函数式（partial function）可能更为妥当。这种函数对于某些输入值，甚至是大多数的输入值都返回一个确定的结果；不过对另一些输入值，它的结果是未定义的，甚至不返回任何结果。这其中一个典型的例子是除法和开平方运算，如果除法的第二操作数是0，或者开平方的参数为负数就会发生这样的情况。以Java那样抛出一个异常的方式对这些情况进行建模看起来非常自然。

那么，如果不使用异常，你该如何对除法这样的函数进行建模呢？答案是使用Optional类型：你应该避免让sqrt使用double sqrt(double)这样的函数签名，因为这种方式可能抛出异常；与之相反我们推荐你使用Optional sqrt(double)——这种方式下，函数要么返回一个值表示调用成功，要么返回一个对象，表明其无法进行指定的操作。当然，这意味着调用者需要检查方法返回的是否为一个空的Optional对象。这件事听起来代价不小，依据我们之前对函数式编程和纯粹的函数式编程的比较，从实际操作的角度出发，你可以选择在本地局部地使用异常，避免通过接口将结果暴露给其他方法，这种方式既取得了函数式的优点，又不会过度膨胀代码。

最后，作为函数式的程序，你的函数或方法调用的库函数如果有副作用，你必须设法隐藏它们的非函数式行为，否则就不能调用这些方法（换句话说，你需要确保它们对数据结构的任何修改对于调用者都是不可见的，你可以通过首次复制，或者捕获任何可能抛出的异常实现这一目的）。在18.2.4节中，你会看到这样的例子，我们通过复制列表的方式，有效地隐藏了方法insertAll调用库函数List.add所产生的副作用。

这些方法通常会使用注释或者使用标记注释声明的方式进行标注——符合我们规定的函数，我们可以将其作为参数传递给并发流处理操作，比如在第4~7章介绍过的Stream.map方法。

为了各种各样的实战需求，你最终可能会发现即便对函数式的代码，我们还是需要向某些日志文件打印输出调试信息。是的，这意味着严格意义上说，这些代码并非函数式的，但是你已经在实际中享受了函数式程序带来的大多数好处。

18.2.2　引用透明性

“没有可感知的副作用”（不改变对调用者可见的变量、不进行I/O、不抛出异常）的这些限制都隐含着引用透明性。如果一个函数只要传递同样的参数值，总是返回同样的结果，那这个函数就是引用透明的。String.replace方法就是引用透明的，因为像"raoul".replace('r', 'R')这样的调用总是返回同样的结果（replace方法返回一个新的字符串，用大写的R替换掉所有小写的r），而不是更新它的this对象，所以它可以被看成函数式的。

换句话说，函数无论在何处、何时调用，如果使用同样的输入总能持续地得到相同的结果，那么就具备了函数式的特征。这也解释了我们为什么不把Random.nextInt看成函数式的方法。Java语言中，使用Scanner对象从用户的键盘读取输入也违反了引用透明性原则，因为每次调用nextLine时都可能得到不同的结果。不过，将两个final int类型的变量相加总能得到同样的结果，因为在这种声明方式下，变量的内容是不会被改变的。

引用透明性是理解程序的一个重要属性。它还包含了对代价昂贵或者需长时间计算才能得到结果的变量值的优化（通过保存机制而不是重复计算），我们通常将其称为记忆化或者缓存。虽然重要，但是现在讨论还是有些跑题，19.5节会对此进行介绍。

Java语言中，关于引用透明性还有一个比较复杂的问题。假设你对一个返回列表的方法调用了两次。这两次调用会返回内存中的两个不同列表，不过它们包含了相同的元素。如果这些列表被当作可变的对象值（因此是不相同的），那么该方法就不是引用透明的。如果你计划将这些列表作为单纯的值（不可修改），那么把这些值看成相同的是合理的，这种情况下该方法是引用透明的。通常情况下，在函数式编程中，你应该选择使用引用透明的函数。现在我们想探讨从更大的范围看是否应该修改对象的值。

18.2.3　面向对象的编程和函数式编程的对比

我们由函数式编程和（极端）典型的面向对象编程的对比入手进行介绍，最终你会发现Java 8认为这些风格其实只是面向对象的一个极端。作为Java程序员，毫无疑问，你一定使用过某种函数式编程，也一定使用过某些我们称之为极端面向对象的编程。正如第1章中所介绍的那样，由于硬件（比如多核）和程序员期望（比如使用类数据库查询式的语言去操纵数据）的变化，促使Java的软件工程风格在某种程度上愈来愈向函数式的方向倾斜，本书的目的之一就是要帮助你应对这种潮流的变化。

关于这个问题有两种观点。一种支持极端的面向对象：任何事物都是对象，程序要么通过更新字段完成操作，要么调用对与它相关的对象进行更新的方法。另一种观点支持引用透明的函数式编程，认为方法不应该有（对外部可见的）对象修改。实际操作中，Java程序员经常混用这些风格。你可能会使用包含了可变内部状态的迭代器遍历某个数据结构，同时又通过函数式的方式（我们曾经讨论过，可以使用可变局部变量实现这一目标）计算数据结构中的变量之和。本章接下来的一节以及下一章中主要的内容都围绕着函数式编程的技巧展开，帮助你编写更加模块化、更适应多核处理器的应用程序。这些技巧和思想会成为你编程武器库中的秘密武器。

18.2.4　函数式编程实战

让我们从解决一个函数式的编程练习题入手：给定一个List，比如{1, 4, 9}，构造一个List>，要求该列表的成员都是初始列表{1, 4, 9}的子集，此外暂时不考虑元素的顺序。{1, 4, 9}的子集分别是{1, 4, 9}、{1, 4}、{1, 9}、{4, 9}、{1}、{4}、{9}以及{}。

这样的子集，包括空子集在内，总共有八个。每个子集都用List表示，这意味着答案所期望的类型是List>。

通常新手碰到这个问题都会觉得无从下手，对于“{1, 4, 9}的子集可以划分为包含1和不包含1的两部分”也需要特别解释2。不包含1的子集很简单，就是{4, 9}，包含1的子集可以通过将1插入到{4, 9}的各子集得到。不过，有一点很微妙：必须牢记空集实际上也含有一个子集，那就是它自身。这样我们就能利用Java，以一种简单、自然、自顶向下的函数式编程方式实现该程序了。3

2偶尔会有些麻烦（机智！）的学生指出另一种解法，这是一种纯粹的代码把戏，它利用二进制来表示数字（Java解决方案的代码分别对应于000,001,010,011,100,101,110,111）。我们告诉这些学生要通过计算得出结果，而不是通过列出所有列表的排列组合，比如对{1,4,9}而言，它就有六种排列组合。

3为了便于理解，这里给出的示例代码使用了具体类型List，不过你可以使用泛型List在方法定义中替换掉它，之后就可以应用新的subsets方法，同时处理List和List了。

static List<List<Integer>> subsets(List<Integer> list) {
    if (list.isEmpty()) {       ←---- 如果输入为空，它就只包含一个子集，既空列表自身
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(Collections.emptyList());
        return ans;
    }
    Integer first = list.get(0);
    List<Integer> rest = list.subList(1,list.size());
    List<List<Integer>> subans = subsets(rest);    ←---- 否则就取出一个元素first，找出剩余部分的所有子集，并将其赋予subans。subans构成了结果的另外一半
    List<List<Integer>> subans2 = insertAll(first, subans);    ←---- 答案的另一半是subans2，它包含了subans中的所有列表，但是经过调整，在每个列表的第一个元素之前添加了first
    return concat(subans, subans2);    ←---- 将两个子答案整合在一起就完成了任务，简单吗？
}

如果给出的输入是{1, 4, 9}，那么程序最终给出的答案是{{}, {9}, {4}, {4, 9}, {1}, {1, 9}, {1, 4}, {1, 4, 9}}。当你完成了缺失的两个方法之后可以实际运行下这个程序。

我们一起回顾下你已经完成了哪些工作。你假设缺失的方法insertAll和concat自身都是函数式的，并依此推断你的subsets方法也是函数式的，因为该方法中没有任何操作会修改现有的结构（如果你熟悉数学的话，大概对此很熟悉，这就是著名的归纳法啊）。

现在，让我们看看如何定义insertAll方法。这是第一个可能出现的“坑”。假设你已经定义好了insertAll，它会修改传递给它的参数，也许是通过更新包含first的subans的所有元素的方式来进行。那么，该程序会以修改subans2同样的方式，错误地修改subans，最终导致答案中莫名地包含了{1, 4, 9}的八个副本。与之相反，你可以像下面这样实现insertAll的功能：

static List<List<Integer>> insertAll(Integer first,
                                     List<List<Integer>> lists) {
    List<List<Integer>> result = new ArrayList<>();
    for (List<Integer> list : lists) {
        List<Integer> copyList = new ArrayList<>();    ←---- 复制列表，从而使你有机会对其进行添加操作。即使底层是可变的，你也不应该复制底层的结构（不过Integer底层是不可变的）
        copyList.add(first);
        copyList.addAll(list);
        result.add(copyList);
    }
    return result;
}

注意到了吗？你现在已经创建了一个新的List，它包含了subans的所有元素。你聪明地利用了Integer对象无法修改这一优势，否则你需要为每个元素创建一个副本。由于聚焦于让insertAll像函数式那样工作，你很自然地将所有的复制操作放到了insertAll中，而不是它的调用者中。

最终，你还需要定义concat方法。这个例子中，我们提供了一个简单的实现，但是希望你不要这样使用（展示这段代码的目的只是为了便于你比较不同的编程风格）。

static List<List<Integer>> concat(List<List<Integer>> a,
                                  List<List<Integer>> b) {
    a.addAll(b);
    return a;
}

不过，我们真正建议你采用的是下面这种方式：

static List<List<Integer>> concat(List<List<Integer>> a,
                                  List<List<Integer>> b) {
    List<List<Integer>> r = new ArrayList<>(a);
    r.addAll(b);
    return r;
}

为什么呢？第二个版本的concat是纯粹的函数式。虽然它在内部会对对象进行修改（向列表r添加元素），但是它返回的结果基于参数没有修改任何一个传入的参数。与此相反，第一个版本基于这样的事实，执行完concat(subans, subans2)方法调用后，没人需要再次使用subans的值。对于我们定义的subsets，这的确是事实，所以使用简化版本的concat是个不错的选择。不过，这也取决于你如何审视你的时间，你是愿意为定位诡异的缺陷费尽心机耗费时间呢？还是花费些许的代价创建一个对象的副本呢？

无论你怎样解释这个不太纯粹的concat方法，“只会用于第一参数可以被强制覆盖的场景，或者只会使用在这个subsets方法中，任何对subsets的修改都会遵照这一标准进行代码评审”，一旦将来的某一天，某个人发现这段代码的某些部分可以复用，并且似乎可以工作时，你未来调试的梦魇就开始了。19.2节会继续讨论这一问题。

请牢记：考虑编程问题时，采用函数式的方法，关注函数的输入参数以及输出结果（即你希望做什么），通常比设计阶段的早期就考虑如何做、修改哪些东西要卓有成效得多。下一节会详细讨论递归。