0%

Haskell右折叠实现左折叠

发表于 更新于 分类于

在《Real World Hashell》一书里，有一段通过foldr表示foldl的代码

1
2
3
4
myFoldl :: (a -> b -> a) -> a -> [b] -> a

myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

刚看到这的时候，感觉特别难懂，尤其是之前没有函数式编程的经历，对柯里化了解不深的情况下，更加一头雾水

如果是顺序读这本书的话，我们应该已经知道了foldr的签名

1
2
Prelude> :type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

困惑

这里最让人感到奇怪的有两点

  1. foldr的签名是接受三个参数，如下

    1. 一个函数，这个函数接受两个参数，类型a和类型b，返回一个类型b的值
    2. 一个类型b的初始值
    3. 一个可折叠类型a，这里我们简单当作一个列表

    但是，实际上我们传递了四个参数

  2. 上面说了，foldr的第一个参数是个函数，接受两个参数，但传递过去的step函数，有三个参数

上述两点，也可以总结成一点：参数个数不匹配。

Currying

要理解这个问题，我们需要一些其他知识，也就是“部分函数应用和柯里化”(Currying)

这部分内容在原书后续有讲到

这两部分是相辅相成的，理解了部分函数应用和柯里化，会更容易弄明白foldr表示foldl；而弄清楚foldr表示foldl，则会对部分函数应用和柯里化有更深刻的理解

在说部分函数应用和柯里化之前，我们先看看一般命令式语言中的现象

比如有如下Java代码，两数相加

1
2
3
private int add(int a, int b) {
    return a + b;
}

这个函数需要两个参数a和b，然后返回两数之和

我们可以通过add(1, 2)的方式调用这个函数，但是，add(1)则是不合法的，因为没有此种方法签名

与Java不同的是，在Haskell中，这是允许的

1
2
3
4
5
Prelude> add a b = a + b
Prelude> :type add
add :: Num a => a -> a -> a
Prelude> :type add 1
add 1 :: Num a => a -> a

在Haskell中，本质上，所有的函数都只接受一个参数

上面的add函数，看上去接受两个类型为a的参数，返回一个类型为a的值，实际上是先接受一个类型为a的参数，返回一个函数，这个函数再接受一个类型为a的参数，返回类型为a的值

就像我们有一个机床，可以将一堆铁疙瘩制作成各种机器，然后我们可以用制造出的机器，将原料加工成成品

现在我们要做衣服，做衣服需要布料，需要使用缝纫机，我们还没缝纫机，不过我们有机床，有铁疙瘩，可以造一个出来，在Haskell里可以表示为

1
2
3
4
5
type Iron = String
type Cloth = String
type Clothes = String

machineTool :: Iron -> Cloth -> Clothes

如果用类似Java语言解释这个签名的话，就是machineTool这个函数需要两个参数，铁和布，将这两个参数同时放进去，会出来一个衣服

在Haskell里，并不需要同时传两个参数，我们可以只传一个

1
sewMachine = machineTool "a piece of iron"

这是合法的，表示给机床一块铁，做出了一台缝纫机，缝纫机是个函数，可以继续接受参数，它现在接受一个Cloth类型的参数，返回Clothes类型的结果

1
2
*Main> :type sewMachine 
sewMachine :: Cloth -> Clothes

这个缝纫机可以接受一匹布，产生一件衣服 sewMachine "a piece of cloth"

解析

回到最初的右折叠表示左折叠问题

1
2
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

再看一下foldr的签名

1
2
Prelude> :type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

foldr第一个参数是函数，其返回值类型为b，和foldr第二个参数，也就是foldr的初始值类型一样，也是b

在foldr step id xs z这里，第二个参数，也就是初始值，是id

1
2
Prelude> :type id
id :: a -> a

我们看到id是一个函数，接受一个类型为a的参数，返回的类型同样也是a（实际上id是identity的缩写，本身的意思，id作用是返回参数本身）

既然初始值类型是函数，那foldr的第一个参数，返回的也是一个函数

我们看到step的定义，它可以接受三个参数，但是在foldr的应用过程中，只会应用两个（列表的从右往左下一个值和初始值或者上一次函数的计算结果），结合函数的部分应用和柯里化，我们知道step函数在应用两个参数后，返回的是另一个函数，这个函数接受一个参数（step函数参数的第三个）

也就是foldr的第一个参数，类型为(a -> b -> b)，在实际执行过程中，a类型是列表内容的类型，第二个参数b类型，第一次是初始值，也就是id，实际类型是一个函数，同时，结果仍然是b，是一个函数，作为下一次计算(a -> b -> b)的第二参数

由于foldr的最终返回结果是一个函数，所以可以应用一个参数，这个参数在foldr step id xs z这里，也就是z，或者说可以把foldr step id xs z看作是(foldr step id xs) z，foldr全部折叠完，其最后结果是一个函数，然后用z作为函数的参数对这个最终函数进行调用

展开

参数个数的问题弄清楚后，我们可以把表达式进行展开，将实际参数带入到表达式的变量中

假设我们现在使用myFoldl对一个列表求和，列表是[1,2]，求和的初始值是0

按照左折叠的规则，我们预期执行顺序应该是((0 + 1) + 2)，从初始值和列表第一个元素开始相加，其和与列表的第二个元素继续相加，如此从左到右一次计算整个列表，并返回最终结果

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
myFoldl f z xs = foldr step id xs z
    where step x g a = g (f a x)

-- 我们的调用为
myFoldl (+) 0 [1,2]
-- 参数带入变量
-- f == (+)
-- z == 0
-- xs == [1,2]

-- 也就是
foldr step id [1,2] 0

==> foldr (\x g a -> g (f a x)) id [1,2] 0
-- 参数再带入到变量，列表从右向左
-- x == 2
-- g == id
-- f == (+)

==> foldr (\x g a -> g (f a x)) (\a -> id ((+) a 2)) [1] 0
-- x == 1
-- g == (\a = id ((+) a 2))
-- f == (+)

==> foldr (\x g a -> g (f a x)) (\a -> (\a -> id ((+) a 2)) ((+) a 1)) [] 0

==>     (\a -> (\a -> id ((+) a 2)) ((+) a 1)) 0
--               ↑                  |........|
--               ↑                      ↓
--               a == ((+) a 1)   <----/

==>     (\a -> (id ((+) ((+) a 1) 2))) 0
--              ↑
--              id返回参数本身

==>     (\a -> ((+) ((+) a 1) 2)) 0
--        ↑
--        a == 0

==>     ((+) ((+) 0 1) 2)
-- 改成中缀

==>     ((+) 0 1) + 2
==>     (0 + 1) + 2

经过上述将实际参数带入到变量，推导后，myFoldl的行为确实与预期一样，我们就这样通过foldr表示了foldl