Haskell/列表 II
之前我们了解到 Haskell 使用 cons 操作符 (:) 和空列表 [] 来构建列表。我们看到了如何使用递归和模式匹配来逐个处理列表。在本章和下一章中，我们将深入探讨列表处理的更深入技术，并发现一些新的符号。我们将初次接触 Haskell 的一些特性，如无限列表、列表推导式和高阶函数。
注意
在本章中，您将阅读和编写函数，这些函数会对列表中的元素进行求和、减法和乘法运算。为简单起见，我们将假设列表元素的类型为 Integer。但是，正如您从关于 类型基础 II 的讨论中所记得的那样，Num 类型类中存在许多不同的类型。作为一种练习，您可以计算出如果我们使这些函数多态，允许列表元素具有 Num 类中的任何类型，那么这些函数的类型签名将是什么。要检查您的签名，只需暂时省略它们，将函数加载到 GHCi 中，使用 :t 并让类型推断来指导您。
这是一个将整数列表中每个元素加倍的函数
doubleList :: [Integer] -> [Integer]
doubleList [] = []
doubleList (n:ns) = (2 * n) : doubleList ns
在这里，基本情况为空列表，它计算为空列表。在递归情况下，doubleList 构建一个新的列表，使用 (:)。这个新列表的第一个元素是参数头部元素的两倍，我们通过递归调用 doubleList 对参数尾部进行操作来获得其余结果。当尾部变为空列表时，将调用基本情况，递归将停止。[1]
让我们研究一个示例表达式的求值过程
doubleList [1,2,3,4]
我们可以通过将参数代入函数定义来手动进行计算，就像教科书中的代数一样
doubleList 1:[2,3,4] = (1*2) : doubleList (2 : [3,4])
= (1*2) : (2*2) : doubleList (3 : [4])
= (1*2) : (2*2) : (3*2) : doubleList (4 : [])
= (1*2) : (2*2) : (3*2) : (4*2) : doubleList []
= (1*2) : (2*2) : (3*2) : (4*2) : []
= 2 : 4 : 6 : 8 : []
= [2, 4, 6, 8]
因此，我们重建了原始列表，将每个元素替换为其两倍。
在这个手动求值练习中，我们选择何时计算乘法的 时机 不会影响结果。我们也可以在每次递归调用 doubleList 之后立即计算倍数。[2]
Haskell 在一些重要方面利用了这种对求值顺序的灵活性。作为一种 纯 函数式编程语言，编译器会做出大部分关于何时实际计算内容的决定。作为一种 惰性 语言，Haskell 通常会延迟求值，直到需要最终值（有时可能永远不会出现）。[3] 从程序员的角度来看，求值顺序很少重要。[4]
要将列表中每个元素乘以 3，我们可以使用与 doubleList 相同的策略
tripleList :: [Integer] -> [Integer]
tripleList [] = []
tripleList (n:ns) = (3 * n) : tripleList ns
但我们不想为每个不同的乘数编写一个新的列表乘法函数（例如，将列表中的元素乘以 4、8、17 等）。因此，让我们创建一个通用函数，允许使用 任何 数字进行乘法。我们的新函数将接受两个参数：被乘数以及要乘以的 Integer 列表
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList _ [] = []
multiplyList m (n:ns) = (m * n) : multiplyList m ns
此示例使用 _ 作为“无关紧要”的模式。被乘数在基本情况下未使用，因此我们忽略该参数，而不是给它一个名称（如 m、n 或 ns）。
我们可以测试 multiplyList，以确保它按预期工作
Prelude> multiplyList 17 [1,2,3,4] [17,34,51,68]
| 练习 |
|---|
|
编写以下函数并测试它们。不要忘记类型签名。
take、drop 和 sum。 |
在本章中，我们从一个受限于将元素乘以 2 的函数开始。然后，我们认识到，我们可以通过创建 multiplyList 来避免为每个乘数硬编码一个新函数，这样就可以轻松地使用任何 Integer。现在，如果我们想要使用其他运算符（如加法）或计算每个元素的平方，该怎么办？
我们可以使用 Haskell 的关键功能进一步泛化。但是，由于解决方案可能令人意外，我们将以一种迂回的方式来解决这个问题。考虑 multiplyList 的类型签名
multiplyList :: Integer -> [Integer] -> [Integer]
首先要了解的是，类型签名中的 -> 箭头是 右结合 的。这意味着我们可以将此签名理解为
multiplyList :: Integer -> ([Integer] -> [Integer])
我们应该如何理解它？它告诉我们 multiplyList 是一个函数，它接受一个 Integer 参数并计算出另一个函数。因此，返回的函数接受一个 Integer 列表并返回另一个 Integer 列表。
考虑我们以前使用 multiplyList 重新定义的 doubleList 函数
doubleList :: [Integer] -> [Integer]
doubleList xs = multiplyList 2 xs
以这种方式编写，我们可以清楚地消去 `xs`
doubleList = multiplyList 2
这种定义风格（没有参数变量）被称为 无点 风格。我们的定义现在表明，对 multiplyList 应用一个参数不会导致求值失败，而是会得到一个更具体的函数，其类型为 [Integer] -> [Integer]，而不是以最终的 [Integer] 值结束。
我们现在看到，Haskell 中的函数的行为与任何其他值非常相似。函数可以返回其他函数，函数可以作为对象独立存在，而无需提及它们的论据。函数似乎几乎与普通常量一样。我们甚至可以将函数本身用作 参数 吗？可以，这就是泛化 multiplyList 的下一步的关键。我们需要一个函数，它接受任何其他合适的函数并将给定的函数应用于列表中的元素
applyToIntegers :: (Integer -> Integer) -> [Integer] -> [Integer]
applyToIntegers _ [] = []
applyToIntegers f (n:ns) = (f n) : applyToIntegers f ns
使用 applyToIntegers，我们可以接受 任何 Integer -> Integer 函数并将其应用于 Integer 列表中的元素。因此，我们可以使用此通用函数重新定义 multiplyList
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList m = applyToIntegers ((*) m)
这将使用 (*) 函数，并使用单个初始参数创建一个新的函数，该函数准备接受另一个参数（在本用例中，将来自给定列表中的数字）。
如果所有这些抽象概念让您感到困惑，请考虑一个具体的例子：当我们在 Haskell 中进行 5 * 7 的乘法时，(*) 函数不会同时接受两个参数，而实际上它会首先接受 5 并返回一个新的 5* 函数；然后，该函数 再 接受第二个参数，并将其乘以 5。因此，在我们的示例中，我们将 7 作为 5* 函数的参数，然后 该函数 返回最终的计算结果（35）。
因此，Haskell 中的所有函数实际上只接受一个参数。但是，当我们知道为了得到最终结果将生成多少个中间函数时，我们可以将函数 视为 接受多个参数。我们通常所说的函数接受的参数个数实际上是在第一个参数和最终的非函数结果值之间生成的单参数函数的个数。
在将参数输入复杂函数时创建中间函数的过程称为 柯里化（以 Haskell Curry 的名字命名，也是 Haskell 编程语言的同名人物）。
虽然 applyToIntegers 的类型为 (Integer -> Integer) -> [Integer] -> [Integer]，但定义本身不包含任何特定于整数的内容。要使用相同逻辑处理其他类型的列表，我们可以定义诸如 applyToChars、applyToStrings 等版本。它们将具有相同的定义，但类型签名不同。我们可以使用泛化的最后一步来避免所有这些冗余：创建一个完全多态的版本，其签名为 (a -> b) -> [a] -> [b]。Prelude 已经有了这个函数，它被称为 map
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs
使用 map，我们可以轻松地实现各种不同的函数，例如...
multiplyList :: Integer -> [Integer] -> [Integer]
multiplyList m = map ((*) m)
...以及...
heads :: [[a]] -> [a]
heads = map head
Prelude> heads [[1,2,3,4],[4,3,2,1],[5,10,15]] [1,4,5]
map 是将函数应用于列表中每个元素的通用解决方案。我们最初的 doubleList 问题只是 map 的一个特例。像 map 这样的接受其他函数作为参数的函数称为 *高阶函数*。在下一章中，我们将学习更多关于列表处理的高阶函数。
| 练习 |
|---|
|
提示和技巧
[edit | edit source]关于 Haskell 中列表的一些杂项说明
点点表示法
[edit | edit source]Haskell 有一种方便的简写方式来编写等间距整数的有序列表。以下是一些示例来说明它
Code Result
---- ------
[1..10] [1,2,3,4,5,6,7,8,9,10]
[2,4..10] [2,4,6,8,10]
[5,4..1] [5,4,3,2,1]
[1,3..10] [1,3,5,7,9]
相同的表示法适用于字符，甚至适用于浮点数。不幸的是，由于舍入误差，浮点数存在问题。试试这个
[0,0.1 .. 1]
无限列表
[edit | edit source]由于惰性求值，Haskell 列表可以是 *无限* 的。例如，以下代码生成从 1 开始的无限整数列表
[1..]
(如果你在 GHCi 中尝试这个，请记住你可以在 Ctrl-c 中停止求值)。
相同的效果可以通过递归函数来实现
intsFrom n = n : intsFrom (n + 1) -- note there is no base case!
positiveInts = intsFrom 1
无限列表在实践中很有用，因为 Haskell 的惰性求值在任何给定时刻实际上只求值它需要的部分。在大多数情况下，我们可以将无限列表视为普通的列表。程序只有在求值需要列表中的所有值时才会进入无限循环。因此，我们无法对无限列表进行排序或打印，但是
evens = doubleList [1..]
将定义 "evens" 为无限列表 [2,4,6,8..]，然后我们可以将 "evens" 传递给其他函数，这些函数只需要求值列表的一部分即可获得其 *最终* 结果。Haskell 会知道只使用最终需要的无限列表的部分。
与硬编码一个长的有限列表相比，定义一个无限列表，然后取前几个项目通常更方便。无限列表也可以成为交互式程序顶层传统无限循环的便捷替代方案。
关于 head 和 tail 的说明
[edit | edit source]在使用 ( : ) 模式或 head/tail 来拆分列表时，模式匹配几乎总是更可取的。使用 head 和 tail 可能很诱人，因为它们简单且简洁，但很容易忘记它们在空列表上会失败（运行时崩溃永远不好）。我们确实有一个 Prelude 函数，null :: [a] -> Bool，它对空列表返回 True，对其他列表返回 False，因此这提供了一种安全的方式来检查空列表，而无需模式匹配；但匹配空列表往往比使用 null 的对应 if-then-else 表达式更干净、更清晰。
| 练习 |
|---|
|