左折叠和右折叠

写了半天，信誓旦旦以为 haskell 的 fold 的表现和 lisp 里的是一致的，结果被打脸了……尴尬。但终究是学习到了。

fold 操作分为foldl和foldr，就理论上来说，它们的区别用一句话概括的话就是，foldl是尾递归，而foldr是递归。其中以 SICP 的语境来说，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
;;; 递归版
(define (factorial n)
  (if (= n 1) 
      1 
      (* n (factorial (- n 1)))))

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

;;; 迭代版
(define (factorial n)
  (define (helper acc n)
    (if (= n 1)
        acc
        (helper (* n acc) (- n 1))))
  (helper 1 n))

(factorial 6)
(helper 1 6)
(helper 6 5)
(helper 30 4)
(helper 120 3)
(helper 360 2)
(helper 720 1)
720

显然可以看到，递归版的阶乘函数先展开成1 * 2 * ... * n的形式才开始进行运算，而迭代版的看不到这种展开——它已经被运算完，作为新的参数进行下一次迭代了。

但是这是 lisp，haskell 由于其非严格求值的特性，表现和 lisp 不一样（甚至完全相反！）。

foldr表面上看起来无必要——既然都有尾递归操作了，为什么还要用浪费空间（可能还有时间）的普通递归操作呢？一个原因是，由于其参数被放到栈中，这意味着计算是被延迟了的，当它与 haskell 的非严格求值相结合，便导致了一个威力无比的特性——它能够处理无穷长度的列表。比如对一个[1..]，我们可以看做是1:2:3:4:...，这种结构显然是类似于那种递归结构的，如果我们构造出的结果符合这种形式，就可以利用 haskell 的特性进行部分取值。

下面是一个自己的 foldr 的实现——

1
2
myFoldr f zero [] = zero
myFoldr f zero (x:xs) = f x $ myFoldr f zero xs

当我们使用:进行调用时——

1
2
3
4
5
6
7
8
myFoldr (:) [] [1,2,3,4]
1:(myFoldr (:) [] [2,3,4])
1:(2:(myFoldr (:) [] [3, 4]))
1:(2:(3:(myFoldr (:) [] [4])))
1:(2:(3:(4:(myFoldr (:) [] []))))
1:(2:(3:(4:[]))) -- 这个括号形式很有意思
1:2:3:4:[] -- 考虑到：是右结合的，括号可以省略
[1,2,3,4]  -- 语法糖

bingo！容易认识到，无限的列表也能进行这种操作，因为 haskell 只要拿到需要的数据就 OK。

下面是foldl的实现——

1
2
3
4
5
6
7
8
9
10
myFoldl f zero [] = zero
myFoldl f zero (x:xs) = myFoldl f (f zero x) xs

myFoldl (-) 0 [1,2,3,4]
myFoldl (-) (0 - 1) [2,3,4]
myFoldl (-) ((0 - 1) - 2) [3, 4]
myFoldl (-) (((0 - 1) - 2) - 3) [4]
myFoldl (-) ((((0 - 1) - 2) - 3) - 4) []
((((0 - 1) - 2) - 3) - 4) -- 为什么这样表示？因为在 haskell 里，恐怕就要导致这样的结果！
-10

顺带一提，关于foldl和foldr的性质，下面这个实例很有趣，只消注意 zero 和括号的情况——

1
2
3
4
5
6
7
foldl (-) 0 [1,2,3,4]
((((0 - 1) - 2) - 3) - 4)
-10

foldr (-) 0 [1,2,3,4]
(1 - (2 - (3 - (4 - 0))))
-2

有趣的事情来了——在 haskell 里，foldr比foldl效率更高！foldl的计算会被延迟（foldl：老子不是尾递归吗！），导致递归般的效率，而foldr反而能够保证一定的效率。而且 foldl 因此不能对无穷列表进行折叠，因为其最左边的先计算，导致如果要生成列表则必定是反转的（除非用++，但 haskell 表示不是:它不认），这让foldl无法处理无限长列表——无限的东西可没法反转。而具体细节…嗯哼。

总之，在 haskell 中，对fold操作进行使用时，考虑遵循这些原则——

  1. 如果要进行 reduce 操作（即生成一个“原子”的值），则使用严格求值的foldl'。这是考虑到左折叠一般来说更易懂，更明显。
  2. 否则，用foldr。
  3. 不要使用foldl。

对其他语言来说，当然还是考虑多使用左折叠了。

Over~

FP

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 协议 ，转载请注明出处！