函数式的思考

函数式的思考

一. 引文

函数式编程是一种新的编程风格,核心就是把函数作为值。利用函数式编程可以用更少的时间,写出更清晰、简洁的代码。函数所指的这部分代码,可以被来回传递并加以组合,从而产生强大的编程语汇。

二. 实现和维护系统

假设我们需要接手一个不熟悉项目,如果我们比较有经验可能会先搜索一下代码中是否有使用synchronized关键字,如果有就意味着要面对修复并发导致的缺陷的可能。为了让程序易于使用,希望最好项目的类结构能直接反映出系统的结构,具有良好的耦合性(软件系统各组件之间是否相互独立)和内聚性(系统的各相关部分之间如何协作)。对于程序员来说,大部分日常工作应该是代码维护时的调试:代码遭遇无法预测的情况而崩溃,为什么这样?如何进入这种状态的?而函数式编程的无副作用不变性对于这一问题大有裨益。

2.1 共享的可变数据

无法预知的变量修改问题源自于共享的数据结构被你所维护的代码中的多个方法读取和更新。正式由于使用了这种结构导致我们很难追踪到程序的各个组成部分所发生的变化。如果一个方法既不修改它内嵌类的状态,也不修改其他对象的状态,使用return返回所有的计算结果,那么我们就可以称其为纯粹的无副作用的

多个类同时共享一个可变对象,很难说到底哪个类真正拥有对象,如下图所示。

多个类同时共享一个可变对象,很难说到底哪个类真正拥有对象

副作用就是函数的效果超过了其自身的范畴,一些例子:

  • 除了构造器内的初始化操作,还对类中数据结构的任何修改,包括字段的赋值操作(如setter)
  • 抛出一个异常
  • 进行输入/输出操作,比如向文件写数据

所以为了实现无副作用,我们应该考虑不可变对象,可以放心的共享,不需要创建任何副本。但真正的生产系统是否能够由这种设计来实现?答案是可以,并且如何系统的各个组件能够遵守这一原则,系统就可以在无锁的情况下适用多核的并发机制,任何一个方法都不会对其他方法造成干扰。

2.2 声明式编程

编程实现系统有两种思考方式:一种专注于如何实现,一种专注于要做什么。前者适合经典的面向对象编程,特点就是和计算机底层词汇相似,如赋值、条件分支以及循环,这种编程会被叫做命令式编程。后者则将如何实现的细节留给函数库,这种思想叫内部迭代,我们的语言看起来会更像问题陈述,这种风格的编程被称为声明式编程

2.3 为什么要采用函数式编程

函数式编程具体实践了声明式编程和无副作用计算,可以使我们更容易的构建和维护系统。实现函数式编程必要的一些特性,如构造操作和传递行为可以使我们的程序更便于阅读、易于编写。

三. 什么是函数式编程

一种使用函数进行编程的方式。函数式编程中的函数对应一个数学函数,接收参数返回结果但不会有副作用,不同于Java中常见的函数,没有可变共享变量的参与。当我们定义函数式时,想要表达的是像数学函数那样没有副作用,我们能否在函数内部执行一些非函数式操作,只要其结果不会暴露出来?或者程序可以存在副作用但不会被其它调用者感知?为了准确的区别二者,我们称第一种为纯粹的函数式编程,第二种为函数式编程

我们可以把函数式编程看作一个黑盒模型:输入->函数->输出。下图分别为带有副作用的函数和没有副作用的函数。

带有副作用的函数

没有副作用的函数

3.1 函数式Java编程

实际Java编程中,我们无法以纯粹的函数式编程来实现一个程序,但可以为系统的核心组件编写接近纯粹式函数式的实现。首先,要确保代码的副作用不能被感知到。比如有一个函数在进入方法体执行时会对一个字段值+1,退出方法体前会对字段值-1。对于单线程来说,这个函数没有副作用。但多线程时,其他线程可以查看该字段的值,甚至并发调用它,那么此函数就不能称为函数式的实现了。当然我们可以通过加锁来对方法体进行封装,从而掩盖这一问题,但同时也失去了在多核处理器上的两个核并发执行两个方法调用的能力。虽然最终符合了函数式的定义,但实际上降低了运行效率。

所以我们的准则是,被称为函数式的函数或方法都只能修改本地变量。除此之外,引用的对象都只能是不可修改的对象(期望所有字段都是final)。但实际上也会允许对方法中全新创建的对象中的字段进行更新,不过这些字段对于其他对象是不可见的,也不会因为保存而对后续调用造成影响。

如果被称为函数式,函数或方法不能抛出任何异常。一旦抛出异常就意味着结果被终止了,但这点其实和数学函数也有冲突,这些数学操作可以被称作局部函数式,当输入正常返回确定的结果,但对于一些输入其结果是未定义的,甚至不返回结果(比如除法除数为0)。所以有些人认为通过抛出异常来对这类情况建模是合理的,但捕获异常是一种非函数式的控制流,这种操作违背了我们定义的黑盒模型,从而增加了一组代表异常处理的箭头:->异常。

抛出一个异常的方法

不使用异常的方案就是使用 Optional<T> 类型,避免直接使用原始或引用类型作为函数返回值,而是 Optional<T> 包装返回值。当然我们需要检查函数返回值是否为一个空的Optional对象,这种方式似乎很繁琐,所以我们可以像非纯粹的函数式那样选择在本地局部地使用异常,避免通过接口将结果暴露给其他方法,这样既利用了函数式的优点,也不会过度的使代码膨胀。

当我们实现的函数存在副作用时,请隐藏这些非函数式行为,否则就不要调用这些方法(换句话说,你要确保它们对数据结构的任何修改对于调用者都是不可见的,可以通过首次复制,或者捕获任何可能抛出的异常来实现这一目的)。如后续3.4的实战代码中我们隐藏了方法insertAll调用库函数List.add所产生的副作用。

3.2 引用透明性

没有可感知的副作用隐含着引用透明性,如果一个函数只要传递同样的参数值,必定会返回同样的结果,可以称这个函数是引用透明的。比如String.replace方法总是返回同样的结果,而不是更新它的this对象,就是引用透明的,可以被看作函数式。所以引用透明性可以看作是函数式的特征,相对的Random.nextInt方法就不会被看作函数式方法。

一种复杂的情况是,比如一个方法会返回一个集合,但如果调用两次会返回两个不同的集合对象,虽然它们有相同的元素值。如果我们把集合当作可变的对象值,那么这个方法就是不透明的。但如果我们把这些结合作为单纯的值(不可修改),这时两个集合被看作是相同集合是合理的,那么这个方法就是透明的。通常,在函数式编程中,你应该选择使用引用透明的函数

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

Java 8认为这些函数式风格只是面向对象的一个极端,由硬件发展和程序员的期望而带来了这些从面向对象到函数式的变化,实际上Java程序员经常会混用两种编程风格,可能会使用包含了可变内部状态的迭代器遍历某个数据结构,同时又通过函数式的方式计算数据结构中变量之和。

3.4 函数式编程实战

假设我们需要对给定的一个集合求其所有子集思路就是通过归纳法递归进行元素间的排列组合,实现方法subsets,递归的每一次都会拿出一个元素并求剩余集合元素的子集,再和拿出的元素排列组合得出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
public class ActualCombat {
public static void main(String[] args) {
List<Integer> list = Arrays.asList(1,4,9);
subsets(list);
}

/**
* 给定一个集合,求集合所有子集
* @param list 集合
* @return 子集数组
*/
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);
System.out.println("first: " + first);
List<Integer> rest = list.subList(1, list.size());

//否则就取出一个元素first,找出剩余部分的所有子集,并将其赋予subans。subans构成了结果的另一半。
List<List<Integer>> subans = subsets(rest);
//答案的另一半是subans2,它包含了subans中的所有集合,但是经过调整,在每个列表的第一个元素之前添加了first
List<List<Integer>> subans2 = insertAll(first,subans);
//将两个答案整合一起完成任务
return concat(subans,subans2);
}

/**
* 将移出元素和当前子集组合
* @param first 移出的当前首元素
* @param lists 已生成的子集数组
* @return 当前子集数组
*/
static List<List<Integer>> insertAll(Integer first,
List<List<Integer>> lists){
List<List<Integer>> result = new ArrayList<>();
for(List<Integer> list : lists){
//复制列表,从而使你有机会对其进行添加操作。
//即使底层是可变的,你也不应该复制底层的结构(不过Integer底层是不可变的)
List<Integer> copyList = new ArrayList<>();
copyList.add(first);
copyList.addAll(list);
result.add(copyList);
}
System.out.println("insertAll: ");
result.forEach(System.out::println);
return result;
}

/**
* 合并子集数组元素
* @param a 数组a
* @param b 数组b
* @return 最终结果
*/
static List<List<Integer>> concat(List<List<Integer>> a,
List<List<Integer>> b){
List<List<Integer>> r = new ArrayList<>(a);
r.addAll(b);
System.out.println("concat: ");
r.forEach(System.out::println);
return r;
}
}

运行结果如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
first: 1
first: 4
first: 9
insertAll:
[9]
concat:
[]
[9]
insertAll:
[4]
[4, 9]
concat:
[]
[9]
[4]
[4, 9]
insertAll:
[1]
[1, 9]
[1, 4]
[1, 4, 9]
concat:
[]
[9]
[4]
[4, 9]
[1]
[1, 9]
[1, 4]
[1, 4, 9]

首先实现insertAll时会有一个坑,如果直接list.add(first),库函数List.add会修改传递的参数。为了使insertAll函数式的运行,我们利用Integer对象无法修改这一优势,否则需要为每个元素创建一个副本,将复制操作放入insertAll内,而不是调用者中。

concat方法的简单实现如下,但为了实现纯粹的函数式我们最终如上实现,虽然会在函数内部对对象进行修改,但基于参数返回的结果却未修改任意一个参数。简单实现版本只能基于这样一个条件:参数a不会再被使用,否则就可能会造成影响。

1
2
3
4
5
static List<List<Integer>> concat(List<List<Integer>> a,
List<List<Integer>> b){
a.addAll(b);
return a;
}

四. 递归和迭代

纯粹的函数式编程通常不包含while或for这样的迭代构造器,因为这样的构造器通常隐藏着陷阱,诱使我们修改对象。比如while循环的条件状态必须要更新,但很多情况下循环是非常有用的,而我们也可以在不被感知的情况下修改局部变量。我们通常使用的for-each循环可以用迭代器的方式重写。

1
2
3
4
5
6
7
8
9
for(Apple a : apples){
......
}

Iterator<Apple> it = apples.iterator();
while(it.hasNext()){
Apple apple = it.next();
......
}

当改变发生时,包括使用next方法对迭代器状态的改变,以及while循环内部对apple变量的赋值,这些对于方法的调用者是不可见的。但如果使用for-each循环,如下搜索算法时会带来问题,因为循环体会对调用方共享的数据结构进行修改。

1
2
3
4
5
6
7
public void searchForGold(List<String> list, Stats stats){
fot(String s : list){
if("gold".equals(s)){
stats.incrementFor("gold");
}
}
}

对于函数式而言,循环体带来乐一个无法避免的副作用:它会修改stats对象的状态,而这和程序的其他部分是共享的。为了解决这种副作用,正确的方案是用无需修改的递归重写来避免迭代。通过递归可以消除每步都需要更新的迭代变量,如实现一个计算阶乘的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 迭代式阶乘计算
*/
static int factorialIterative(int n){
int r = 1;
for(int i = 1;i <= n;i++){
r *= i;
}
return r;
}

/**
* 递归式阶乘计算
*/
static long factorialRecursive(long n){
return n == 1 ? 1 : n * factorialRecursive(n-1);
}

/**
* Stream式阶乘计算
*/
static long factorialStreams(long n){
return LongStream.rangeClosed(1,n)
.reduce(1, (long a, long b) -> a * b);
}

当然我们也可以使用Stream流来实现阶乘计算。递归方式在Java中效率相比迭代会差一些,递归式方法调用的开销会比迭代执行单一机器级的分支指令大很多,因为每次执行factorialRecursive方法调用都需要在调用栈上创建一个新的栈帧,用于保存每个方法调用的状态,这个操作会一直指导程序运行直到结束,意味着递归迭代方法会依据它接收到的输入成比例的消耗内存。

函数式语言提供了一个方案来解决这个效率问题:尾—调优化(tail-call optimization),基本思想是你可以编写阶乘的一个迭代定义,不过迭代调用会发生在函数的最后,这种新型的迭代调用经过优化后的执行速度会快很多。

1
2
3
4
5
6
7
8
9
/**
* 递归式阶乘计算: 尾-调优化
*/
static long factorialTailRecursive(long n){
return factorialHelper(1,n);
}
static long factorialHelper(long acc, long n){
return n == 1 ? acc : factorialHelper(acc * n, n-1);
}

factorialHelper是尾-递类型的函数,递归调用会发生在方法的最后。factorialRecursive递归会先进行递归,递归结果最后进行运算;而factorialHelper则先运算,将运算结果直接作为参数进行递归。factorialRecursive方法会每次调用创建一个栈帧,而factorialHelper不需要在不同的栈帧上保存每次递归运算的中间值,编译器能够自行决定复用某个栈帧进行计算,阶乘的中间值直接被用作参数传递给此方法,也就不用为每个递归调用分配单独的栈帧用于跟踪每次调用的中间值——通过方法的参数可以直接访问直接值。

栈帧和尾递阶乘的差异

但Java 8版本时还未能支持这种优化,而一些现代的语言如Scala或Groovy都支持了这种递归优化,最终的效果和迭代不相上下。这意味着坚持纯粹的函数式编程既能享受其好处,也不会损失执行的效率。所以在Java 8时,建议使用Stream代替迭代操作,如果采用递归能够不带来副作用且更容易实现那应该采用递归,毕竟开发的效率往往比执行的细微差异在大多数时候要更重要。


参考:

🔗 《Java8实战》