lambda与折叠

lambda与折叠

一个已经一个半月没有更过的系列。。。。折叠比较难以理解，需要多花时间来学习一下，这篇博客的篇幅应该也会比较长。

参考书籍: Learn you a Haskell

lambda

lambda在Haskell中就是指一次性的佚名函数。当我们想使用一个函数但是不想再去定义它时可以使用lambda。在Haskell中，如果襄阳声明一个lambda，就写一个\。之所以用这个符号，是因为它长得比较像\(\lambda\)（然而我觉得并不像。。。）。具体用例如下：

1
2

biggerThanFive :: Int
biggerThanFive xs = length (filter (\x -> even x) xs) 

上面的式子计算出了1到100中偶数的个数。lambda表达式看上去十分好用，以至于经常被滥用，很多情况下的lambda表达式都是没有必要的，比如下面两个式子便是等价的:

1
2
3
4
5

addThree :: [Int] -> [Int]
addThree xs = map (+3) xs

addThree :: [Int] -> [Int]
ad Three xs = map (\x -> x + 3) xs

和普通函数一样,lambda也可以取多个参数：

1
2

ghci> zipWith (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]
[3,8,9,8,7]

此外，还有一个同时运用了lambda和柯里化的较为有趣的例子：

1
2
3
4
5

sumThree :: Int -> Int -> Int -> Int
sumThree x y z = x + y + z

sumThree :: Int -> Int -> Int -> Int 
sumThree = \x -> \y -> \z -> x + y + z

上面的两个函数的作用时相同的。只不过第二个并不易理解。

折叠

折叠应该算是到现在为止比较难的部分了(起码我是这么认为的)，其实主要是学会区分和使用左折叠和右折叠。折叠会取一个二元函数，一个初始值和一个列表。它会依次将二元函数从左到右或从右到左应用到列表上，并且上一个的返回值为下一次二元运算的一个参数。

foldl-左折叠

左折叠，显而易见，就是从列表的左端开始执行"折叠"操作。闲话不多说，我们先来举一个最简单的例子-求和：

1
2

sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs

在进行左折叠时，譬如计算sum' [3,5,2,6]，即foldl (\acc x -> acc + x) 0 [3,5,2,6],其步骤大概为先计算0+3，得出3，再计算3+5，得出8，然后计算8+2，得出10，最后计算10+6，算出16，得到最终答案。

当然，上面的函数如果我们使用函数柯里化的方式而非lambda函数的话，写法会更加简单:

1
2

sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0

foldr-右折叠

右折叠，顾名思义，从右边开始折叠。需要注意的是，右折叠的二元函数内的参数位置和左折叠是相反的。折叠的初始值可以为任何类型，比如，我们可以自己实现map函数，初始值为map所要操作的列表，写法如下：

1
2

map' :: (a -> b) -> [a] -> [b]
map' f xs = foldr (\x acc -> f x : acc) [] xs

如果我们运行map' (+3) [1,2,3],即foldr (\x acc -> f x : acc) [] xs时，程序会首先将执行f 3 : [],得到[6],然后执行f 2 : [6],得到[5,6]，最后是f 1 :[5,6]，得到[4,5,6]。当然，我们也可以使用左折叠来实现map'函数：

1
2

map' :: (a -> b) -> [a] -> [b];
map' f xs = foldl (\acc x -> acc ++ [f x]) [] xs

但是，使用左折叠时用到的++操作远比:要慢，所以需要生成列表时，我们一般会使用右折叠。此外，两个折叠有一个非常重要的区别：左折叠无法处理无限列表，而右折叠可以。这个我们在之后会深入讨论。

foldl1与foldr1

当我们想要使用折叠而又没有初始值时该怎么办呢？这时候就要拿出我们的foldl1和foldr1函数了。这两个函数与常规的折叠函数的唯一区别是没有初始值，而是取列表最左(右)边的元素作为初始值。在很多时候这会非常有用，比如我们要实现一个maximum'函数：

1
2

maximum' :: (Ord a) => [a] -> a
maximum = foldl1 max

此时的maximum'函数会取列表最左边的元素作为初始值，然后一次向右进行折叠操作，以此比较出最大值。

foldl1和foldr1需要注意的是传入的列表不能够为空列表，应该至少包含一个元素，否则会发生运行时错误。

一些折叠的例子

为了继续熟悉折叠的用法，我们来用折叠实现几个标准库函数：

1
2

reverse' :: [a] -> a
reverse' = foldl (\acc x -> x : acc) []

这里我们使用左折叠，从左边开始取数，然后从左边放入答案的列表中，实现反转功能。而若是我们使用filp，可以将上面的函数简化成这样：

1

reverse'= fold (flip (:)) []

我们可以实现product'函数：

1
2

product' :: (Num a) => [a] -> a
product' = foldl (*) 1

1

product' = foldl1 (*)

还有较为复杂的filter'函数：

1
2

filter' :: (a -> Bool) -> [a] -> [b]
filter' p = foldr (\x acc -> if p x then x : acc else acc) []

此外，我们还可以用折叠来实现last'函数，这是比较巧妙地用法：

1
2

last' :: [a] -> a
last' = foldl1 (\_ x -> x)

关于折叠的运行步骤

我们很容易理解，左折叠和右折叠分别为从左侧和右侧开始。但是若是将这过程直接拆分为一个表达式会是什么样子呢？还是以sum'函数为例，假如进行sum' [3,5,6,8]操作，那么，左折叠和右折叠的运行步骤应该为什么样子呢？

• 左折叠：

1

(((0 + 3) + 5) + 6) + 8

• 右折叠:

1

3 + (5 + (6 + (8 + 0)))

无限列表的折叠

之前我们也已经讲过了，只有右折叠能够实现无限列表的操作。这看上去有悖于直觉。因为我们可能会认为左折叠是从左面开始的，所以能过先计算左边的元素，然后因为Haskell的惰性，满足条件时直接退出。

但是，我们可以来看一下之前提到的折叠的运行步骤。当我们将左折叠和右折叠分别拆分时，发现两种折叠都为括号内的项数为无限多。而左折叠的括号在左侧，右折叠在右侧。也就是说，右折叠拆分后，无限多的项被放到了右边，因此我们可以从左边开始依次进行处理，然后根据情况依赖于Haskell的惰性，退出这个无限长的式子。

比如，我们运行下面的式子:

1
2

ghci> foldr && True (repeat False)
False

这个式子拆分完后是:

1

True && (False && (False && (False && ...)))

也就是说，我们完全可以从左到右依次运行，算出结果为False。