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) []
折叠需要一些时间才能习惯，但它是函数式编程中的一个基本模式，最终会变得非常自然。任何时候你想要遍历一个列表并从它的成员中构建一个结果，你可能想要一个折叠。
| 练习 |
|---|
|
“扫描”就像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的对应函数，它们从右侧累积总数。
| 练习 |
|---|
|
对列表执行的常见操作是过滤——生成一个新列表，该列表仅包含满足特定条件的第一个列表中的元素。一个简单的例子：从整数列表中生成仅包含偶数的列表。
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一样，它们接受另一个函数作为参数；使用它们无点强调了这种“函数的函数”的方面。
列表推导是某些常见列表操作（例如过滤）的语法糖。例如，我们可以这样编写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作为生成新列表时要附加的元素。相反，我们可以在竖线之前放置任何表达式（当然，它必须与列表的类型兼容）。例如，如果我们想要从每个偶数中减去一，只需要
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，它们以这种方式运行。