Language

Haskell 的 fold 系列

分析 Haskell 中 fold 系列函数。

一年前刚接触 Haskell 时，以及半年前学习 sicp 时，fold 之间的转化和区别就曾让我纠结过一段时间。现在重新来看，有些概念还是模糊。所以把主要的区别记录下来以供日后查阅。

相关链接：

Data.Foldable 中的 foldl 和 foldr 均为非严格求值（惰性求值），最明显的差别在折叠方向不同，一个从左到右，一个从右到左。其次，foldl 的形式是尾递归，而 foldr 则需要在每折叠一个元素时在栈中重新开辟一块空间以进入下一层次的递归。因此 foldl 较 foldr 效率更高，但二者处理的列表长度均有限制（如果求值中不出现短路的情况）。

无限长列表处理

另一个显式的不同在于，foldr 能够处理无限列表，这是因为 foldr 在展开过程中可能出现表达式短路，例如下面的例子中，foldr 使用初值 True 对一个无限长的、元素均为 False 的列表求与，将立刻得到 False，因为其展开式为 a0 && (a1 && ( ... && (a. && True)))，虽然整个列表展开式是无穷的，但因为最外层 && 表达式的第一个操作数是 False，与操作表达式短路，因此运算随之结束。

1
2
foldr (&&) True (repeat False)
False && (False && (False && (... && (False && True) ... )))

而使用 foldl 时，其展开过程如下。整个展开式无穷，而最外层的 && 表达式的第一个操作数是一个子式，也是一个无穷的展开式，要求 foldl 表达式结果必须先求得子式的值，这个过程将永不会结束，也无法利用短路特性。

1
2
foldl (&&) True (repeat False)
((...(True && False) && False) && ...)

所以，foldr 能够处理无限长列表的原因在于，它从右向左折叠，展开式方向从左向右，所以能够利用某些表达式的短路特性。

二者处理长列表对比

在折叠操作无短路特性的情况下，两者处理的列表长度均有限。尽管 foldl 采取了尾递归，但由于 Haskell 默认使用惰性求值，所以和 foldr 一样，都会产生 *** Exception: stack overflow。

下面的例子来自上面的 Haskell Wiki。

foldr 处理 foldr (+) 0 [1..1000000] 的过程展开如下。因为 (+) 是严格求值符号，所以符号两边的参数都要求出才能对表达式求值。在例子中，要求 1 + (2 + (3 + (4 + (...))))，则： 1 被入栈，并对 2 + (3 + (4 + (...))) 求值； 2 被入栈，并对 3 + (4 + (...)) 求值； 3 被入栈，并对 4 + (...) 求值。当列表长度足够大时，栈满将引发栈溢出异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
foldr (+) 0 [1..1000000] -->
1 + (foldr (+) 0 [2..1000000]) -->
1 + (2 + (foldr (+) 0 [3..1000000])) -->
1 + (2 + (3 + (foldr (+) 0 [4..1000000]))) -->
1 + (2 + (3 + (4 + (foldr (+) 0 [5..1000000])))) -->
-- ...
1 + (2 + (3 + (4 + (... + (999999 + (foldr (+) 0 [1000000]))...)))) -->
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + ((foldr (+) 0 []))))...)))) -->
-- ...
1 + (2 + (3 + (4 + (... + (999999 + (1000000 + 0))...)))) -->
1 + (2 + (3 + (4 + (... + (999999 + 1000000)...)))) -->
1 + (2 + (3 + (4 + (... + 1999999 ...)))) -->
-- ...
1 + (2 + (3 + (4 + 500000499990))) -->
1 + (2 + (3 + 500000499994)) -->
1 + (2 + 500000499997) -->
1 + 500000499999 -->
500000500000

同样的表达式，用 foldl 解释过程如下（使用 foldl 尝试可能导致操作系统异常），因为 (+) 符号产生的整个表达式仍然不可约（即不具有短路特性，必须将最后一个元素计算后才可得出结果），所以仍然要展开整个列表。整个解释过程分三部分：

  • 第一部分是尾递归，因为 Haskell 的惰性求值，foldl f z (x:xs) 引出的 foldl f (f z x) xs 式中，f z x 不会被立刻求值，而是以 let 方式在堆中分配一块空间存储，而堆的空间取决于所使用机器的内存，如果列表足够长，可能在这一部分就会导致程序的崩溃，因为这部分的工作就是向堆中写入大量 let 产生的数据，这些数据会占用大量的内存。
  • 假设上一步成功执行，则堆中将充斥着 let 绑定，它们的数量和列表长度相同。在下面的例子中，表达式只剩下 z1000000。而要求 z1000000，必须求 z1000000 = z999999 + 1000000 中的 z999999。所以 1000000 入栈，并开始对 z999999 求值；之后 999999 入栈，并对 z999998 求值，以此类推。这一步和 foldr 的展开类似，只是列表展开方向上 foldl 从右到左，当列表长度足够长时，这一步将导致栈溢出，这也是为什么 foldl 对长列表做严格求值运算时，会产生 *** Exception: stack overflow 异常的原因，通常堆的空间足够大，第一步能够成功执行，而在此步，foldl 和 foldr 面临同样的困境。
  • 假设上一步成功执行，剩下的操作就是不断地出栈、求值。
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
foldl (+) 0 [1..1000000] -->
 
let z1 =  0 + 1
in foldl (+) z1 [2..1000000] -->
 
let z1 =  0 + 1
    z2 = z1 + 2
in foldl (+) z2 [3..1000000] -->
 
let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
in foldl (+) z3 [4..1000000] -->
 
-- ... after many foldl steps ...
 
let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
    ...
    z999997 = z999996 + 999997
    z999998 = z999997 + 999998
    z999999 = z999998 + 999999
in foldl (+) z999999 [1000000] -->
 
let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
    ...
    z999997 = z999996 + 999997
    z999998 = z999997 + 999998
    z999999 = z999998 + 999999
    z100000 = z999999 + 1000000
in foldl (+) z1000000 [] -->
 
let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
    ...
    z999997 = z999996 + 999997
    z999998 = z999997 + 999998
    z999999 = z999998 + 999999
    z100000 = z999999 + 1000000
in z1000000 -->
 
-- Now a large chain of +'s will be created:
 
let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
    ...
    z999997 = z999996 + 999997
    z999998 = z999997 + 999998
    z999999 = z999998 + 999999
in z999999 + 1000000 -->
 
let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
    ...
    z999997 = z999996 + 999997
    z999998 = z999997 + 999998
in  (z999998 + 999999) + 1000000 -->
 
let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
    z4 = z3 + 4
    ...
in  (((z999996 + 999997) + 999998) + 999999) + 1000000 -->
 
-- ...

let z1 =  0 + 1
    z2 = z1 + 2
    z3 = z2 + 3
in  ((((((z3 + 4) + 5) + ...) + 999997) + 999998) + 999999) + 1000000 -->
 
let z1 =  0 + 1
    z2 = z1 + 2
in  (((((((z2 + 3) + 4) + 5) + ...) + 999997) + 999998) + 999999) + 1000000 -->
 
let z1 =  0 + 1
in  ((((((((z1 + 2) + 3) + 4) + 5) + ...) + 999997) + 999998) + 999999) + 1000000 -->
 
(((((((((0 + 1) + 2) + 3) + 4) + 5) + ...) + 999997) + 999998) + 999999) + 1000000 -->

-- Now we can actually start reducing:

((((((((1 + 2) + 3) + 4) + 5) + ...) + 999997) + 999998) + 999999) + 1000000 -->
(((((((3 + 3) + 4) + 5) + ...) + 999997) + 999998) + 999999) + 1000000 -->
...
(499998500001 + 999999) + 1000000 -->
499999500000 + 1000000 -->
500000500000

由此可见，二者能够处理的列表长度其实相同，主要受栈空间的限制。foldr 受栈空间限制的原因是它本身并不采用尾递归，而 foldl 尽管使用了尾递归的形式，但因为惰性求值的特性：表达式仅在真正需要它们的值的时候才会被计算，故形式上的尾递归并没有真正起作用。所以 foldr 的限制是无法解除的，但 foldl 只要摒弃惰性求值，就可以摆脱限制，从形式上的尾递归变成真实意义上的尾递归。

另外，我们还能看出， foldl 隐含了堆列表做一个逆序操作，而 foldr 则保持了列表的顺序 。

这两者因为效率低下，在生产代码中均不会出现。

Foldl’

使用 seq 可以使表达式被立刻求值。foldl' 的定义如下，每次进入尾递归前都要计算出参数 z' 的值，而不是将表达式的绑定入堆，之后再入栈、出栈。生产代码中只会出现 foldl'。

1
2
3
foldl' f z []     = z
foldl' f z (x:xs) = let z' = z `f` x 
                    in seq z' $ foldl' f z' xs

现在上面例子的计算过程如下，运算将不会导致栈溢出。

1
2
3
4
5
6
7
8
9
foldl' (+) 0 [1..1000000] -->
foldl' (+) 1 [2..1000000] -->
foldl' (+) 3 [3..1000000] -->
foldl' (+) 6 [4..1000000] -->
foldl' (+) 10 [5..1000000] -->
-- ...
foldl' (+) 499999500000 [1000000] -->
foldl' (+) 500000500000 [] -->
500000500000

通常，我们会在 foldr 和 foldl' 之间选择。

但使用 foldl' 也存在缺陷，考虑下面的例子，foldl 将返回 0（foldr 也一样），而 foldl' 将产生一个 undifined 错误。这是因为 (*) 具有短路特性，如果 (*) 符号右侧的子式为 0 ，则左式不必计算。在 foldl 中，最终展开式为 ((((1 * 2) * 3) * undefined) * 5) * 0，直接求出结果为 0；在 foldr 中，最终展开式为 2 * (3 * (undifined * (5 * (0 * 1))))，可以看出，首先 5 * (0 * 1) 计算出　0，之后变为 2 * (3 * (undifined * 0))，此时短路，因此求出 0。

1
2
foldl (*) 1 [2,3,undefined,5,0]
foldl' (*) 1 [2,3,undefined,5,0]

Foldr 和 Foldl 的转化

foldl 和 foldr 可以互相表示。

用 foldr 表示 foldl 如下。这个转化其实并不完全正确，因为 foldr 可以处理无穷列表，而 foldl 本身并不具有这一特性。

1
2
3
foldl'' :: (a -> b -> a) -> a -> [b] -> a
foldl'' f z xs = foldr step id xs z
    where step x g acc = g (f acc x)

类似的，用 foldl 表示 foldr 如下。

1
2
3
foldr'' :: (b -> a -> a) -> a -> [b] -> a
foldr'' f z xs = foldl step id xs z
    where step g acc x = g (f acc x)

这里我将试图把自己的理解表述出来：

以 foldr 表示 foldl 为例。foldr 看上去似乎接收了四个参数，但经过部分施用，foldr step id xs 实际产生了一个类型签名为 a -> a 的结果，这里的 a 即为 foldl 传入的零值 z 的类型。因此 foldr 的作用即是产生了这样一个函数，这个函数的格式类似上面例子中的 1 + (2 + (3 + (4 + (... + (999999 + (1000000 + 0))...))))，但它接收一个参数，这个参数就是式中的 0，即它接收传入的零值 z，返回对这个零值作用的结果。

下面观察函数是如何产生的。step 作为折叠函数，接收三个参数，参数 x 是剩余列表的最后一个元素（因为是 foldr，方向从右向左），参数 acc 是累积值。我们知道 foldr 中的折叠函数实际只接收两个参数，因此 step 是一个部分施用的函数。观察 step 的类型签名，因为在 foldr 中，它接受一个函数 id 作为零值，所以它的类型是 a -> (b -> b) -> (b -> b)。因为 step 每次只能获得两个参数（剩余列表中的最后一个值和 acc），所以它将返回一个 (b -> b) 作为下一次的 acc。

用一个例子演示 foldr 具体的展开过程。考虑 foldl'' f zero [a1, a2, a3]，这里 foldl'' 是用 foldr 表示的 foldl。其展开过程如下：

1
2
3
4
5
6
7
8
9
10
foldl'' f zero [a1, a2, a3]
= (foldr step id [a1, a2, a3]) zero
= (step a1 (step a2 (step a3 id))) zero
= (step a1 (step a2 (\z -> id (f z a3)))) zero
= (step a1 (\y -> (\z -> id (f z a3)) (f y a2))) zero
= (\x -> (\y -> (\z -> id (f z a3)) (f y a2)) (f x a1)) zero
= (\x -> (\y -> (\z -> f z a3) (f y a2)) (f x a1)) zero
= (\x -> (\y -> f (f y a2) a3) (f x a1)) zero
= (\x -> f (f (f x a1) a2) a3) zero
= f (f (f zero a1) a2) a3

在上面的展开过程中，首先按 foldr 过程展开成一系列 step 的叠加，之后从内向外逐步嵌套，成为一系列 foldl 传入的折叠函数 f 的组合：这个组合要计算的第一个直接子式（无需经过入栈、出栈即可计算出结果）接收 foldl 传入的零值 zero。

同理，可以写出用 foldl 实现 foldr'' 具体的展开过程，仍以 foldr'' f zero [a1, a2, a3] 为例，其展开过程如下：

foldr’’ f z xs = foldl step id xs z
where step g acc x = g (f acc x)

1
2
3
4
5
6
7
8
9
foldr'' f zero [a1, a2, a3]
= (foldl step id [a1, a2, a3]) zero
= (step (step (step id a1) a2) a3) zero
= (step (step (\z -> id (f z a1)) a2) a3) zero
= (step (\y -> (\z -> id (f z a1)) (f y a2)) a3) zero
= (\x -> (\y -> (\z ->id (f z a1)) (f y a2)) (f x z3)) zero
= (\x -> (\y -> f (f y a2) a1) (f x a3)) zero
= (\x -> f (f (f x a3) a2) a1) zero
= f (f (f zero a3) a2) a1

尽管二者可以互相表示，但仅仅是显式形式上的，其它隐式的性质仍然是形式所无法表征的。

原创作品，允许转载，转载时无需告知，但请务必以超链接形式标明文章原始出处(http://blog.forec.cn/2016/11/18/haskell-fold/) 、作者信息（Forec）和本声明。

分享到