列表简介

在接下来的课程中，我们将学习列表类型（list datatype），这是 Haskell 以及函数式编程中的核心数据类型。由于列表本身是递归定义的，因此它非常适合使用递归作为主要问题解决手段的语言。

列表类型

列表是一种线性数据结构，用于存储元素的集合。每个元素指向下一个元素，最后一个元素则指向一个特殊的 nil 值（即空列表）。下图展示了一个包含三个数字 1, 2, 3 的列表。

与元组类似，我们可以用任何 Haskell 数据类型来构造列表。列表类型的表示方式是使用方括号。整数列表的类型为 [Int]，双精度浮点数列表的类型为 [Double]，依此类推。要创建列表字面量，只需将值用方括号括起来。以下是一些列表的例子：

1ints :: [Int]
2ints = [1, 2, 3]
3
4empty :: [Int]
5empty = []
6
7functions :: [Int -> Int]
8functions = [(+1), (*2)]
9
10nested :: [[String]]
11nested = [["hi"], ["how", "are", "you"], ["i'm", "fine"]]

如示例所示，我们可以用任意类型构造列表，包括函数类型和列表类型本身（从而生成嵌套列表）。Haskell 中一个列表的所有元素必须具有相同类型，不能存在混合了整数和浮点数的列表。

Haskell 中的列表，像大多数类型一样，是不可变的，即无法直接修改列表中的值，除非创建一个新的列表。但 Haskell 让我们能够轻松地从已有列表构建新列表。

构造列表

我们可以使用两个 数据构造器 [] 和 : 逐个构建列表。

• [] 表示空列表。它可以代表任意类型的空列表（例如 [Int] 或 [Double]）。
• 如果 x 是类型 a 的元素，xs 是类型为 [a] 的列表，那么 l = x : xs 也是一个类型为 [a] 的列表。l 的第一个元素是 x，称为 l 的头（head）。剩下的部分是 xs，称为 l 的尾（tail）。

例如，我们可以将列表 [1, 2, 3] 写成 1 : (2 : (3 : []))

• [] 是空列表
• 3 : [] 是以 3 为头、空尾的列表，即单元素列表 [3]
• 2 : (3 : []) 是以 2 为头、3 : [] 为尾的列表，即包含两个元素的列表 [2, 3]
• 1 : (2 : (3 : [])) 是以 1 为头、2 : (3 : []) 为尾的列表，即包含三个元素的列表 [1, 2, 3]

: 操作符是右结合的，因此我们也可以写成 1 : 2 : 3 : []，这与上面的可视化完全一致。实际上，简写形式 [1, 2, 3] 只是语法糖，内部会被转换为 1 : 2 : 3 : []。所有 Haskell 列表都是由空列表 [] 和操作符 : 构建而成，后者通常被称为 cons 操作符。

对列表进行模式匹配

为了编写操作列表的函数，我们将再次使用模式匹配。列表有两种模式：

• 空模式 []。它仅匹配空列表。
• cons 模式 pattern_1 : pattern_2，其中 pattern_1 和 pattern_2 本身也是模式。它仅匹配非空列表，其中 pattern_1 匹配头，pattern_2 匹配尾。

这些模式在语法上与数据构造器非常相似。特别是 cons 模式可以看作是列表的“数据解构器”，因为它能将非空列表拆分为头和尾两部分。

最常用的 cons 模式是为 pattern_1 和 pattern_2 使用变量。按照惯例，头的变量通常命名为 x，尾的变量命名为 xs（读作“x 的复数”）。这样就形成了模式 x : xs，它匹配所有非空列表。此时 x 会绑定到列表的头，xs 会绑定到其尾部（尾部可能为空）。

让我们通过实现一个 containsMatchingInt 函数来说明这些模式的用法。该函数接收一个谓词函数 test :: Int -> Bool 和一个整数列表 xs。如果列表中存在某个元素满足谓词 test，则 containsMatchingInt test xs 返回 True，否则返回 False。

1containsMatchingInt :: (Int -> Bool) -> [Int] -> Bool

我们将 containsMatchingInt 实现为对列表参数的递归函数。基础情况是列表为空，这意味着它不可能包含我们寻找的值。

1containsMatchingInt _ [] = False

递归情况是列表非空。此时我们可以使用带保护条件的等式来检查头是否满足谓词 test，如果满足，则返回 True。否则，我们需要递归地检查列表的尾部。

1containsMatchingInt test (x:xs) | test x == True = True
2                                | otherwise      = containsMatchingInt test xs

语法上，我们必须在左侧的 cons 模式周围加上括号。以下是 containsMatchingInt 的完整定义：

1containsMatchingInt :: (Int -> Bool) -> [Int] -> Bool
2containsMatchingInt _ [] = False
3containsMatchingInt test (x:xs) | test x == True = True
4                                | otherwise      = containsMatchingInt test xs
5
6main = do 
7  print (containsMatchingInt (>5) [2, -3, 7])
8  print (containsMatchingInt (\x -> x `mod` 3 == 0) [-2, 4, 8])

练习：列表模式

编写一个函数 intLength :: [Int] -> Int。它应返回给定整数列表的长度。请使用模式匹配实现 intLength 为递归函数。

1intLength :: [Int] -> Int
2-- 请修改下面的代码！
3intLength xs = -1