函数式思维
以函数式的方式思考，第 1 部分
学习如何像函数式程序员一样思考
系列内容：
此内容是该系列 # 部分中的第 # 部分： 函数式思维
此内容是该系列的一部分：函数式思维
敬请期待该系列的后续内容。
假如您是位伐木工人，如果您拥有最好的斧子，那您将会是林场中最能干的伐木工人。忽然有一天，有人向您展示并推荐一个新型伐木工具，电锯。这个销售人员很善于推销，于是您购买了电锯，但不知道如何使用。于是您就参照以前的模式来用，举起电锯用力地挥向树木。您很快就会得出结论，电锯这种新工具只不过是一种时尚，最后还是改用斧子来砍树。这时，有人过来告诉您如何正确使用电锯。
您可以参考这个故事，但是要把电锯 替换为函数式编程。这是个全新的编程范式，并不像学习一门新语言那么简单。毕竟，语言语法只是细节问题。难点在于学习不同的思维 方式。这就是我的切入点 — 电锯使用者与函数式程序员。
欢迎关注 函数式思维。本系列文章将介绍函数式编程相关主题，但内容不仅限于函数式编程语言。相关内容包括，以 “函数式” 方式来编写代码将会涉及设计、权衡、不同的可重用构建模块、以及一些其他见解。我会尽量多地在 Java（或者与 Java 类似的语言）中展示函数式编程的概念，然后会转向其他语言，来展示在 Java 语言中所没有的功能。我不会立即对 monads（见 参考资料）这类新知识进行深入的介绍。相反，我会逐步地向您展示一种新的思考问题方式（可能您已在某些地方采用了，只不过没有留意）。
本期及下一期将会对函数式编程的一些相关主题做一简单介绍，其中包括一些核心概念。有些概念将在后续部分做详细介绍。作为主体部分的开始，我将向您介绍一个问题的两种不同实现方式，一个采用命令式编写，另一个采用函数式编写。
数字分类器
当谈到不同编程风格时，必须有可供对比的代码。第一个例子是在 The Productive Programmer（见 参考资料）一书，和 “演化架构与紧急设计：测试驱动设计，第 1 部分”，以及 “演化架构与紧急设计：测试驱动设计，第 2 部分”（ developerWorks 系列文章 演化架构与紧急设计 中的两部分内容）中出现的另一种形式的编码问题。选取这些内容是由于这两篇文章深入地描述了代码设计问题。这些文章中有关设计的内容没有错误，但是我想在此处给出一个采用不同设计的理由。
要求是，给出任何大于 1 的正整数时，必须将其分类为 perfect、abundant、或者 deficient。perfect 数是其因子（factor）（不包括该数本身）加起来等于该数。类似地，abundant 数是其所有因子的和大于该数，而 deficient 数是其因子的和小于该数。
命令式数字分类器
满足该要求的命令式分类如清单 1 所示：
清单 1. NumberClassifier，对该问题的命令式解决方案
public class Classifier6 {
private Set<Integer> _factors;
private int _number;
public Classifier6(int number) {
if (number < 1)
throw new InvalidNumberException(
"Can't classify negative numbers");
_number = number;
_factors = new HashSet<Integer>>();
_factors.add(1);
_factors.add(_number);
}
private boolean isFactor(int factor) {
return _number % factor == 0;
}
public Set<Integer> getFactors() {
return _factors;
}
private void calculateFactors() {
for (int i = 1; i <= sqrt(_number) + 1; i++)
if (isFactor(i))
addFactor(i);
}
private void addFactor(int factor) {
_factors.add(factor);
_factors.add(_number / factor);
}
private int sumOfFactors() {
calculateFactors();
int sum = 0;
for (int i : _factors)
sum += i;
return sum;
}
public boolean isPerfect() {
return sumOfFactors() - _number == _number;
}
public boolean isAbundant() {
return sumOfFactors() - _number > _number;
}
public boolean isDeficient() {
return sumOfFactors() - _number < _number;
}
public static boolean isPerfect(int number) {
return new Classifier6(number).isPerfect();
}
}针对该代码需要注意的问题：
- 它具有丰富的单元测试（因为我编写的目的是用于探讨测试驱动开发）。
- 类中包含大量的方法，这是采用测试驱动开发进行构建的副作用。
- 在
calculateFactors()方法中包含了性能优化功能。类中包含了对因子的搜集，因此可以进行累加并最终进行分类。因子可以是成对的。比如，如果问题中的数字是 16，那么当获取因子 2 时，也就获取了 8，因为 2 x 8 = 16。如果成对获取因子，那么仅需要检查目标数的平方根个因子，这正是calculateFactors()方法所采用的方式。
（更多）函数式分类器
采用相同的测试驱动开发技术，可以创建该分类器的可替换版本，如清单 2 所示：
清单 2. 函数式数字分类器
public class NumberClassifier {
static public boolean isFactor(int number, int potential_factor) {
return number % potential_factor == 0;
}
static public Set<Integer> factors(int number) {
HashSet<Integer> factors = new HashSet<Integer>();
for (int i = 1; i <= sqrt(number); i++)
if (isFactor(number, i)) {
factors.add(i);
factors.add(number / i);
}
return factors;
}
static public int sum(Set<Integer> factors) {
Iterator it = factors.iterator();
int sum = 0;
while (it.hasNext())
sum += (Integer) it.next();
return sum;
}
static public boolean isPerfect(int number) {
return sum(factors(number)) - number == number;
}
static public boolean isAbundant(int number) {
return sum(factors(number)) - number > number;
}
static public boolean isDeficient(int number) {
return sum(factors(number)) - number < number;
}
}这两个分类器的区别很小但很重要。主要区别是 清单 2 中有目的的共享状态缺乏。共享状态的消除（至少是减少）是函数式编程中的抽象方式之一。与将方法之间的共享状态作为中间结果不同（见 清单 1 中的 factors 字段），我直接调用方法，消除了状态。从设计角度来看，这使得 factors() 方法变长了，但这避免了 factors 字段从方法中漏出。还要注意 清单 2 版本可以完全由静态方法组成，因此就不太需要通过 scoping 来封装。如果输入正确类型的参数，这些方法将会工作的很好。（这就是纯函数 的一个例子，在后续部分会对此做详细介绍。）
函数
函数式编程是一种宽泛的、跨领域的计算机科学，并在最近受到广泛关注。新的基于 JVM 的函数式语言（比如 Scala 与 Clojure）和框架（比如 Functional Java 与 Akka）都有提供（见 参考资料），通常都声称具有更少的错误、产能更高、视觉效果更好、更高的开发效率等等。我不是一开始就要介绍函数式编程的所有相关主题，而是关注几个关键概念，以及这些概念所产生的有趣的影响。
函数式编程的核心是函数，就像面向对象语言的主要抽象方法是类。函数为流程构建了功能模块，并具有传统命令式语言中所不具有的一些功能。
高阶（Higher-order）函数
高阶函数可以将其他函数作为参数或者返回结果。在 Java 语言中不存在这一构造。最接近的方式是利用类（经常是匿名类）作为想要执行的方法的 “holder”。Java 没有单独的函数（或者方法），因此无法从函数中返回或者作为参数来传递。
函数式语言的这一功能很重要，原因至少有两个。首先，具有高阶函数意味着您可以假设如何将语言部分组合成一个整体。例如，可通过构建一个通用机制，遍历清单并向每个元素应用一个（或多个）高阶函数，来在类层次结构中消除方法的整个分类（categories）（下面将会展示相关示例）。其次，通过支持函数作为返回值，就可支持构建动态性与适应性更高的系统。
适合采用高阶函数来解决的问题不仅限于函数式语言中。然而，如果您有函数式思维，问题的解决方法会有所不同。考虑清单 3 中保护数据访问方法的示例（来自更大的代码库）：
清单 3. 潜在可重用代码模板
public void addOrderFrom(ShoppingCart cart, String userName,
Order order) throws Exception {
setupDataInfrastructure();
try {
add(order, userKeyBasedOn(userName));
addLineItemsFrom(cart, order.getOrderKey());
completeTransaction();
} catch (Exception condition) {
rollbackTransaction();
throw condition;
} finally {
cleanUp();
}
}清单 3 中的代码执行初始化，执行一些工作，如果一切顺利，则事务完成，否则会回滚，并最终会清空资源。很显然，该代码的样板文件可重复使用，我们通常会在面向对象语言中通过创建架构来实现。在本例中，我将会组合 Gang of Four Design Patterns 的两个部分（见 参考资料）：the Template Method 和 Command patterns。Template Method 模式建议，应当将公共模板代码移到继承层次结构之上，将算法细节推迟到子类。公共设计模式提供了利用常规执行语句来在类中封装行为的方法。清单 4 展示了在 清单 3 中的代码中应用这些模式的结果：
清单 4. 重构 order 代码
public void wrapInTransaction(Command c) throws Exception {
setupDataInfrastructure();
try {
c.execute();
completeTransaction();
} catch (Exception condition) {
rollbackTransaction();
throw condition;
} finally {
cleanUp();
}
}
public void addOrderFrom(final ShoppingCart cart, final String userName,
final Order order) throws Exception {
wrapInTransaction(new Command() {
public void execute() {
add(order, userKeyBasedOn(userName));
addLineItemsFrom(cart, order.getOrderKey());
}
});
}
在 清单 4 中，将代码的通用部分提取到 wrapInTransaction() 方法中（您可能熟悉该语义 — 这只是 Spring TransactionTemplate 的简单版本），将 Command 对象作为工作单元来传递。addOrderFrom() 方法成为公共类的匿名内部类创建的定义，将这两个工作项目包装起来。
在公共类中包装所需的行为，纯粹是一个 Java 设计方案，不包括任何类型单独的行为。Java 中所有的行为必须在类的内部。即使是语言设计者也很快看到了这种设计缺陷 — 事后看来，认为不存在不需要附加到类的行为有点天真。JDK 1.1 通过增加匿名内部类来弥补这方面的不足，这至少为利用纯函数（而非结构化）方法来创建大量小类提供了语法糖（syntactic sugar）。这类有关 Java 的文章，见 Steve Yegge 的 “Execution in the Kingdom of Nouns”（见 参考资料）。
Java 要求为 Command 类创建一个实例，即使我真正想要的是类中的方法。类本身不提供任何效益：它没有字段，没有构造函数（除了 Java 自动生成的），没有状态。它只是作为方法内部的行为的包装程序。在函数式语言中，可利用高阶函数来处理。
如果不采用 Java 语言，可利用闭包来获取与函数式编程接近的语义。清单 5 展示了相同的重构例子，但是使用的是 Groovy（见 参考资料）而不是 Java：
清单 5. 使用 Groovy 闭包而不是命令类
def wrapInTransaction(command) {
setupDataInfrastructure()
try {
command()
completeTransaction()
} catch (Exception ex) {
rollbackTransaction()
throw ex
} finally {
cleanUp()
}
}
def addOrderFrom(cart, userName, order) {
wrapInTransaction {
add order, userKeyBasedOn(userName)
addLineItemsFrom cart, order.getOrderKey()
}
}
在 Groovy 中，在大括号 {} 内的所有内容都是代码块，代码块可作为参数来传递类似于高阶函数。Groovy 实施了 Command 设计模式。Groovy 中的每个闭包块实际上是 Groovy 闭包类型的一个实例，其中包括 call() 方法，当您将空集括号放在持有闭包实例的变量后时，该方法将会自动调用。Groovy 已经通过构建适当的函数结构，利用相应的语法糖，来在语言本身中支持一些与函数式编程类似的行为。在后续的部分中会介绍到，Groovy 还包含其他优于 Java 的函数式编程功能。后续内容还会对闭包与高阶函数做一些有趣的对比。
一级函数
函数式语言中的函数称为一级函数，这意味着函数可在任何其他语言结构（比如变量）可能出现的地方出现。一级函数的存在使得可以以意想不到的方式来使用一级函数，并不得不以不同的方式来思考解决方案，比如在标准数据结构上应用相对一般的操作（加上细节）。这反过来揭示了函数式语言的根本性转变：关注结果，而不是步骤。
在命令式编程语言中，我们必须在算法中考虑每个原子步骤。清单 1 中的代码显示了这一问题。要解决数字分类器问题，必须准确辨别如何搜集因子，这意味着必须编写特定代码来遍历数字，从而确定因子。但是遍历清单，在每个元素上执行操作，听起来比较平常。考虑利用 Functional Java 框架重新实现数字分类代码，见清单 6：
清单 6. 函数式数字分类器
public class FNumberClassifier {
public boolean isFactor(int number, int potential_factor) {
return number % potential_factor == 0;
}
public List<Integer> factors(final int number) {
return range(1, number+1).filter(new F<Integer, Boolean>() {
public Boolean f(final Integer i) {
return number % i == 0;
}
});
}
public int sum(List<Integer> factors) {
return factors.foldLeft(fj.function.Integers.add, 0);
}
public boolean isPerfect(int number) {
return sum(factors(number)) - number == number;
}
public boolean isAbundant(int number) {
return sum(factors(number)) - number > number;
}
public boolean isDeficiend(int number) {
return sum(factors(number)) - number < number;
}
}清单 6 与 清单 2 的主要区别在于两个方法：sum() 与 factors()。方法 sum() 充分利用了 Functional Java 中 List 类的优势，foldLeft() 方法。这是一个称为 catamorphism 的列表操作概念的变异，这是在列表 folding 上的泛化。在本例中，“fold left” 意味着：
- 获取初始化值，并通过在列的首个元素上的操作来与其结合。
- 获取结果并对下一个元素实施同样的操作。
- 持续进行该操作直到类结束。
注意，这正是当您对一列数求和时所要做的：从零开始，加上第一个元素，获取结果并将其加到第二个上，持续操作直至列结束。函数式 Java 提供高阶函数（在本例中，Integers.add 枚举）并进行应用。当然，Java 并不真的具有高阶函数，但如果严格限制特定的数据结构与类型，就可以编写很好的模拟。）
清单 6 中另一个有趣的方法是 factors()，这说明了 “关注结果，而不是步骤” 的建议。找到一个数的因子的实质是什么？换句话说，列出所有可能成为目标数的数字，如何确定哪一个才是该数的因子？建议使用一种过滤操作 — 可以过滤列出的所有数字，排除那些不满足条件的数。该方法可以这样描述：获取从 1 到该数范围内的所有数字（范围是 noninclusive ，因此 +1）；根据 f() 方法中的代码来过滤清单，这是 Functional Java 方法，支持创建具有特定数据类型的类，并返回值。
作为编程语言的总趋势，此代码还演示了一个更大的概念。从前，开发人员不得不处理所有烦人的问题，比如内存分配、垃圾搜集、和指针。随着时间的推移，语言必须负担更多责任。由于计算机变得越来越强大，我们对语言与运行时间的要求越来越高。作为 Java 开发人员，我已经习惯于让语言来解决所有的内存问题。函数式编程扩展了该任务、包括更具体的细节。随着时间的推移，我们仅需花费更少的时间来考虑需要解决问题的步骤，而更多地区考虑流程。在本系列内容中，我会展示很多相关例子。
结束语
函数式编程不只是一组工具或者语言，更是一种心态。在第 1 部分中，我首先简要介绍了函数式编程中的一些主题，内容从简单的设计决策到一些重大问题的重新思考。我编写了示例 Java 类，来使其更具功能性，然后开始进入其他主题，来区分函数式编程与传统命令式语言。
两个重要的、长远的概念首次在这里出现。第一，关注结果，而不是步骤。函数式编程尝试以不同的方式来呈现问题，因为有不同的构建模块来支持该解决方案。我将在本系列中展示的第二个主题是，将琐碎的细节放到编程语言和运行时，我们只关注编程问题的特定方面。下一期，我将继续关注函数式编程的常见问题，以及如何将其应用到当前的软件开发中。
相关主题
- The Productive Programmer（Neal Ford，O'Reilly Media，2008 年）：Neal Ford 有关这一主题的最新书籍。
- Monads: Monads，有关函数式语言的相关主题，将会在本系列文章中介绍。
- Scala：Scala 是在 JVM 上运行的现代函数式言语。
- Clojure：Clojure 是在 JVM 上运行的现代的函数式 Lisp。
- Podcast: Stuart Halloway on Clojure：深入了解 Clojure，并找出为何它能够被快速接受并快速流行的两个主要原因。
- Akka：Akka 是用于 Java 的框架，它允许复杂的，基于 actor 的并发。
- Functional Java：函数式 Java 是个框架，可向 Java 增加很多函数式语言结构。
- Design Patterns: Elements of Reusable Object-Oriented Software（Erich Gamma et al.，Addison-Wesley，1994 年）：The Gang of Four 有关设计模式的经典之作。
- “Execution in the Kingdom of Nouns”（Steve Yegge，2006 年 3 月）： 有关 Java 语言设计的有趣内容。
- developerWorks 中国网站 Java 技术专区：找出有关 Java 编程的大量文章。