函数式思维
以函数式的方式思考,第 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 编程的大量文章。