fold right与fold left的相互转化

发表于 | 分类于
字数统计: 852 字

阅读本文请自备纸、笔、头痛药。

序

fold left和fold right是函数式编程里表达遍历求值的其中一种重要表达式。在此不过多介绍，本文假设读者熟悉并能熟练使用fold left与fold right进行遍历求值。
问题来源于Scala小红书里一个小习题。大致意思是，如何利用fold left来实现fold right。一般人，包括我，第一直觉就是反转list，然后flip一下二元函数。

Fig.1 - 我和我的小伙伴都是这样想的

但是原文中还说了一句：

用fold left来实现fold right很有用，因为可以用尾递归的方式实现，意味着无论列表有多长都不会产生栈溢出。

那用reverse显然是不符合题意的，因为会导致栈溢出。好奇心驱使着我去寻找这个问题的正确解答，果不其然，我又被惊艳到了。

解

1
2
3
4
5
6
7
// 用foldl实现foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldr f z xs = foldl (\g x -> \z -> g (f x z)) id xs z
// 用foldr实现foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl f z xs = foldr (\x g -> \z -> g (f z x)) id xs z

如果能一下子看懂并理解，敬你是个天才。一开始看不懂、被绕晕也是正常的。欢迎参考我接下来的解析。

形状

fold left

foldl f z [1..10]的求值形状如下：

1
(f (f (f (f (f (f (f (f (f (f z 1) 2) 3) 4) 5) 6) 7) 8) 9) 10)

fold right

foldr f z [1..10]的求值形状如下；

1
(f 1 (f 2 (f 3 (f 4 (f 5 (f 6 (f 7 (f 8 (f 9 (f 10 z))))))))))

上述用foldl实现foldr本质上就是利用foldl生成foldr那样的一个求值形状（闭包），然后apply到初始值z上，求值那一长串得到最后结果，而用foldr实现foldl亦同理。

以foldl实现foldr为例。

1
2
3
4
5
6
7
8
9
10
11
    foldr f z xs = foldl (\g x -> \z -> g (f x z)) id xs z
    foldr (:) [] [1..5] = 
    foldl (\g x -> \z -> g ((:) x z)) id                                         [1..5] []
<=> foldl (\g x -> \z -> g ((:) x z)) (\z -> id (1 : z))                         [2..5] []
<=> foldl (\g x -> \z -> g ((:) x z)) (\z -> id (1 : (2 : z)))                   [3..5] []
<=> foldl (\g x -> \z -> g ((:) x z)) (\z -> id (1 : (2 : (3 : z))))             [4..5] []
<=> foldl (\g x -> \z -> g ((:) x z)) (\z -> id (1 : (2 : (3 : (4 : z)))))       [5]    []
<=> foldl (\g x -> \z -> g ((:) x z)) (\z -> id (1 : (2 : (3 : (4 : (5 : z)))))) []     []
<=> (\z -> id (1 : (2 : (3 : (4 : (5 : z)))))) []
<=> id (1 : (2 : (3 : (4 : (5 : [])))))
<=> [1, 2, 3, 4, 5]

以上应该能够为你建立起一些intuition了，不过对于我来说其实还不够，更重要的是建立起对fold的求值结果是一个函数的直观感受。

重新审视

fold right to fold left

现在重新看foldl的正常递归实现：

1
2
3
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs

换一种等价写法（关键）

1
2
3
foldl f z xs = g xs z
  where g []     z = z
        g (x:xs) z = g xs (f z x)

再进一步

1
2
3
foldl f z xs = g xs z
  where g []     = \z -> z = id
        g (x:xs) = \z -> g xs (f z x)

假设我们有这样一个cons实现：

1
2
3
cons :: [a] -> [a]
cons []     = []
cons (x:xs) = x : (cons xs)

cons用foldr实现：

1
2
cons = foldr (\x r -> x : r) []
// 其中r替换原来的cons xs

经过对比，g一样可以用foldr实现：

1
2
g = foldr (\x r -> \z -> r (f z x)) id
// 其中r替换原来的g xs

因此，将g代入foldl f z xs = g xs z，得到：

1
foldl f z xs = foldr (\x r -> \z -> r (f z x)) id xs z