Haskell/列表 III
像map一样，折叠是一个高阶函数，它接收一个函数和一个列表。但是，它不是逐个元素应用函数，而是使用它将列表元素组合成一个结果值。
让我们来看几个具体的例子。sum可以实现为
示例： sum
sum :: [Integer] -> Integer
sum [] = 0
sum (x:xs) = x + sum xs
而product可以实现为
示例： product
product :: [Integer] -> Integer
product [] = 1
product (x:xs) = x * product xs
concat，它接收一个列表的列表，并将它们连接（合并）成一个
示例： concat
concat :: [[a]] -> [a]
concat [] = []
concat (x:xs) = x ++ concat xs
所有这些例子都展示了递归模式，被称为折叠。想想这个名称指的是列表被“折叠起来”成一个单一的值，或者指的是一个函数被“折叠在”列表的元素之间。
Prelude 定义了四个fold函数：foldr、foldl、foldr1 和 foldl1。
右结合foldr从右到左折叠一个列表。在进行过程中，foldr 使用给定的函数将每个元素与称为累加器的运行值结合起来。调用 foldr 时，累加器的初始值作为参数设置。
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acc [] = acc
foldr f acc (x:xs) = f x (foldr f acc xs)
foldr 的第一个参数是一个具有两个参数的函数。第二个参数是累加器的值（通常从一个中性的“零”值开始）。第三个参数是要折叠的列表。
在sum中，f是(+)，acc是0。在concat中，f是(++)，acc是[]。在许多情况下（像我们迄今为止的所有示例一样），传递给折叠的函数将是一个接收两个相同类型参数的函数，但这并不总是如此（正如我们可以从类型签名的(a -> b -> b)部分看到 - 如果类型必须相同，类型签名中的前两个字母应该匹配）。
记住，在 Haskell 中写成[a, b, c]的列表是a : b : c : []的另一种（语法糖）风格。
现在，foldr f acc xs 在foldr定义中只是用函数f替换xs列表中的每个 cons（:），同时用acc替换最后的空列表
foldr f acc (a:b:c:[]) = f a (f b (f c acc))
注意括号是如何嵌套在列表的右端。
一个优雅的可视化方法是将列表数据结构想象成一棵树
: f
/ \ / \
a : foldr f acc a f
/ \ -------------> / \
b : b f
/ \ / \
c [] c acc
我们可以在这里看到，foldr (:) []将返回完全未改变的列表。这种没有影响的函数称为恒等函数。你应该养成习惯，在不同的情况下寻找恒等函数，我们将在学习幺半群时更多地讨论它们。
左结合foldl从左侧开始处理列表。
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f acc [] = acc
foldl f acc (x:xs) = foldl f (f acc x) xs
因此，结果表达式中的括号累积在列表的左侧
foldl f acc (a:b:c:[]) = f (f (f acc a) b) c
相应的树看起来像
: f
/ \ / \
a : foldl f acc f c
/ \ -------------> / \
b : f b
/ \ / \
c [] acc a
由于所有折叠都包含左元素和右元素，初学者可能会被名称搞糊涂。你可以将 foldr 视为 fold-right-to-left 的简写，将 foldl 视为 fold-left-to-right 的简写。这些名称指的是折叠从哪里开始。
注意
技术说明：foldl 是尾递归的，也就是说，它立即递归，调用自身。因此，编译器会将其优化为一个简单的循环以提高效率。但是，Haskell 是一种惰性语言，因此对f的调用默认情况下不会被求值，从而在内存中构建一个未求值的表达式，其中包含列表的整个长度。为了避免内存不足，我们有一个名为foldl'的 foldl 版本，它是严格的 - 它会在每一步立即强制求值f。
函数名末尾的撇号发音为“tick”，如“fold-L-tick”或“prime”，如“fold-L-prime”。撇号是 Haskell 标识符中的有效字符。foldl'可以在Data.List库模块中找到（通过在源文件开头添加import Data.List导入）。作为经验法则，你应该对可能无限的列表或折叠正在构建数据结构的列表使用foldr，而对已知为有限且最终归结为单个值的列表使用foldl'。几乎没有使用foldl（不带撇号）的好理由，尽管如果馈送给它的列表不太长，它可能只是有效。
你可能会注意到，在某些情况下，foldl和foldr似乎不是相反的。让我们检查一下这种情况下的一种情况，涉及减法作为组合运算。下面的每个等式将得到True还是False？
foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
将foldr视为从右到左进行，可能会让我们认为第二个等式将为真，因为最右边的元素在最左边的元素之前出现。然而，事实并非如此
GHCi> foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
True
GHCi> foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
False
这是因为foldr和foldl之间的区别在于结果表达式是如何关联的，而不是列表元素的从左到右顺序。以下是上面表达式的展开，带有显式括号
foldl (-) 6 [3, 2, 1] == ((6 - 3) - 2) - 1 -- True
foldr (-) 6 [1, 2, 3] == 1 - (2 - (3 - 6)) -- True
还要注意，初始累加器（在本例中为6）始终位于最里面的括号中。
为了对比，以下是一种模拟的命令式风格，它确实改变了列表中元素的顺序：[1]
GHCi> import Data.List -- So that we can give foldl' a try
GHCi> reduce f acc list = foldl' f acc list -- This is the same as plain old foldl'
GHCi> reduceRight f acc list = foldl' f acc (reverse list) -- keep foldl', but reverse list
现在我们从初始示例中获得了两个True，因为它们都是从左侧折叠
GHCi> reduce (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
True
GHCi> reduceRight (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
True
如前所述，foldr 的类型声明使得列表元素和结果可以具有不同的类型。例如，“read”是一个函数，它接收一个字符串并将其转换为某种类型（类型系统足够智能，可以弄清楚是哪一种）。在这种情况下，我们将它转换为浮点数。
示例： 列表元素和结果可以具有不同的类型
addStr :: String -> Float -> Float
addStr str x = read str + x
sumStr :: [String] -> Float
sumStr = foldr addStr 0.0
还有一个名为foldr1（“fold - R - one”）的变体，它通过采用列表的最后一个元素来代替显式的“零”作为累加器
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
foldr1 _ [] = error "Prelude.foldr1: empty list"
以及foldl1
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f [x] = x
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error "Prelude.foldl1: empty list"
注意：与 foldl 一样，Data.List 库包含 foldl1' 作为 foldl1 的严格版本。
使用 foldl1 和 foldr1，所有类型都必须相同，空列表是一个错误。当没有明显的初始累加器值候选者并且我们确定列表不会为空时，这些变体很有用。如有疑问，请坚持使用 foldr 或 foldl'。
右结合折叠在 Haskell 中比左结合折叠更自然的原因之一是，右折叠可以操作无限列表。返回无限列表的折叠在不需要访问整个无限结果的更大上下文中是完全可用的。在这种情况下，foldr 可以尽可能地移动，编译器会知道何时停止。但是，左折叠必须递归调用自身，直到它到达输入列表的末尾（因为递归调用不是在 f 的参数中进行的）。不用说，如果输入列表对 foldl 是无限的，那么就永远不会到达末尾。
作为一个玩具示例，考虑一个名为 echoes 的函数，它接受一个整数列表，并生成一个新的列表，使得输入列表中出现数字 n 的地方，在输出列表中重复 n 次。为了创建 echoes 函数，我们将使用 prelude 函数 replicate，其中 replicate n x 是一个长度为 n 的列表，每个元素的值都为 x。
我们可以很方便地将 echoes 写成一个 foldr
echoes :: [Int] -> [Int]
echoes = foldr (\ x xs -> (replicate x x) ++ xs) []
GHCi> take 10 (echoes [1..])
[1,2,2,3,3,3,4,4,4,4]
(注意： 由于使用了 \ x xs -> 语法，这个定义非常简洁。\，看起来像一个 lambda (λ)，作为 匿名 函数，适用于我们不再需要在其他地方使用该函数的情况。因此，我们将一次性函数的定义 就地 提供。在本例中，x 和 xs 是参数，定义的右侧是 -> 后面的内容。）
我们也可以使用 foldl
echoes :: [Int] -> [Int]
echoes = foldl (\ xs x -> xs ++ (replicate x x)) []
GHCi> take 10 (echoes [1..]) -- not terminating
但只有 foldr 版本可以处理无限列表。如果你直接计算 echoes [1..] 会发生什么？试试看！ (如果你在 GHCi 或终端中尝试，请记住你可以用 Ctrl-c 停止计算，但要快，并注意系统监视器，否则你的内存很快就会被耗尽，系统就会挂起。)
作为最后一个例子，map 本身可以用 fold 实现
map :: (a -> b) -> [a] -> [b]
map f = foldr (\ x xs -> f x : xs) []
折叠需要一段时间才能习惯，但它是函数式编程中的一个基本模式，最终会变得非常自然。任何时候你想要遍历一个列表并从它的成员中累积一个结果，你可能都需要一个 fold。
| 练习 |
|---|
|
扫描
[edit | edit source]“扫描”就像 map 和 fold 的交叉。折叠一个列表会累积一个单一的返回值，而映射会将每个项目通过一个函数，为每个项目返回一个单独的结果。扫描会同时做两件事：它像 fold 一样累积一个值，但它并不只返回最终值，而是返回所有中间值的列表。
Prelude 包含四个扫描函数
scanl :: (a -> b -> a) -> a -> [b] -> [a]
scanl 从左侧累积列表，第二个参数成为结果列表中的第一个项目。因此，scanl (+) 0 [1,2,3] = [0,1,3,6].
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanl1 使用列表的第一个项目作为零参数。如果你想让输入和输出项目类型相同，通常使用这个函数。注意 scanl 和 scanl1 类型签名之间的差异。 scanl1 (+) [1,2,3] = [1,3,6].
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr (+) 0 [1,2,3] = [6,5,3,0]
scanr1 :: (a -> a -> a) -> [a] -> [a]
scanr1 (+) [1,2,3] = [6,5,3]
这两个函数分别是 scanl 和 scanl1 的对应函数，它们从右侧累积总计。
| 练习 |
|---|
|
过滤
[edit | edit source]对列表执行的常见操作是 过滤 - 生成一个新列表，其中只包含满足特定条件的第一个列表中的元素。一个简单的例子：从整数列表中生成一个仅包含偶数的列表。
retainEven :: [Int] -> [Int]
retainEven [] = []
retainEven (n:ns) =
-- mod n 2 computes the remainder for the integer division of n by 2.
if (mod n 2) == 0
then n : (retainEven ns)
else retainEven ns
这个定义有点冗长和具体。Prelude 提供了一个简洁通用的 filter 函数，其类型签名为
filter :: (a -> Bool) -> [a] -> [a]
因此，(a -> Bool) 函数会测试一个元素是否满足某个条件，然后我们提供一个要过滤的列表，最后得到过滤后的列表。
要使用 filter 写 retainEven，我们需要将条件声明为一个辅助的 (a -> Bool) 函数，例如
isEven :: Int -> Bool
isEven n = (mod n 2) == 0
然后 retainEven 就简单地变成了
retainEven ns = filter isEven ns
我们使用 ns 而不是 xs 来表示我们知道这些是数字，而不仅仅是任何东西，但我们可以忽略它，使用更简洁的无点定义
retainEven = filter isEven
这类似于我们之前对 map 和 fold 的演示。与 filter 一样，它们接受另一个函数作为参数；使用它们进行无点操作突出了这种 “函数的函数” 方面。
列表推导
[edit | edit source]列表推导是某些常见列表操作的语法糖，例如过滤。例如，我们可以像这样写 retainEven，而不是使用 Prelude filter
retainEven es = [n | n <- es, isEven n]
这种简洁的语法可能看起来很吓人，但它很容易分解。一种解释是
- (从中间开始) 接受列表 es 并将它的每个元素绘制 (使用 “<-”) 为一个值 n。
- (在逗号之后) 对每个绘制的 n，测试布尔条件
isEven n。 - (在竖线之前) 如果 (且仅当) 布尔条件满足，则将 n 附加到正在创建的新列表中 (注意整个表达式周围的方括号)。
因此，如果 es 为 [1,2,3,4]，那么我们将得到列表 [2,4]。1 和 3 没有被绘制，因为 (isEven n) == False 。
列表推导的强大之处在于它易于扩展。首先，我们可以使用任意多的测试 (甚至为零！)。多个条件以逗号分隔的表达式列表的形式写入 (当然，这些表达式应该计算为布尔值)。举一个简单的例子，假设我们想要修改 retainEven，使其只保留大于 100 的数字
retainLargeEvens :: [Int] -> [Int]
retainLargeEvens es = [n | n <- es, isEven n, n > 100]
此外，我们不仅限于使用 n 作为生成新列表时要附加的元素。相反，我们可以在竖线之前放置任何表达式 (当然，如果它与列表的类型兼容)。例如，如果我们想要从每个偶数中减去 1，只需要
evensMinusOne es = [n - 1 | n <- es, isEven n]
实际上，这意味着列表推导语法包含了 map 和 filter 的功能。
为了进一步简化操作，列表推导中的左箭头符号可以与模式匹配结合使用。例如，假设我们有一个 (Int, Int) 元组列表，并且我们想要构造一个包含每个元组的第一个元素的列表，这些元组的第二个元素是偶数。使用列表推导，我们可以这样写
firstForEvenSeconds :: [(Int, Int)] -> [Int]
firstForEvenSeconds ps = [fst p | p <- ps, isEven (snd p)] -- here, p is for pairs.
模式可以使代码更易读
firstForEvenSeconds ps = [x | (x, y) <- ps, isEven y]
与其他情况一样，可以在 | 之前使用任意表达式。如果我们想要一个包含这些第一个元素的双倍值的列表
doubleOfFirstForEvenSeconds :: [(Int, Int)] -> [Int]
doubleOfFirstForEvenSeconds ps = [2 * x | (x, y) <- ps, isEven y]
不计算空格，该函数代码比它的描述性名称更短！
还有更多可能的技巧
allPairs :: [(Int, Int)]
allPairs = [(x, y) | x <- [1..4], y <- [5..8]]
这个推导从 两个 列表中提取，并生成所有可能的 (x, y) 对，其中第一个元素从 [1..4] 中提取，第二个元素从 [5..8] 中提取。在最终的成对列表中，第一个元素将是使用第一个列表的第一个元素 (这里是 1) 生成的元素，然后是使用第一个列表的第二个元素生成的元素，等等。在本例中，完整的列表是 (为了清晰起见，添加了换行符)
Prelude> [(x, y) | x <- [1..4], y <- [5..8]] [(1,5),(1,6),(1,7),(1,8), (2,5),(2,6),(2,7),(2,8), (3,5),(3,6),(3,7),(3,8), (4,5),(4,6),(4,7),(4,8)]
我们可以很容易地添加一个条件来限制进入最终列表的组合
somePairs = [(x, y) | x <- [1..4], y <- [5..8], x + y > 8]
这个列表只包含元素之和大于 8 的对；从 (1,8) 开始，然后是 (2,7)，依此类推。
| 练习 |
|---|
|
备注
- ↑
reduce和reduceRight函数取自 JavaScript，它们以这种方式工作。