列表（List）与常用操作¶

语法糖与构造方式¶

方括号字面量只是连续 Cons 的语法糖：

-- 语法糖写法：
[1, 2, 3]

-- 底层展开：
1 : (2 : (3 : []))

时间复杂度¶

由单向链表的结构可以得出：

• 头部插入（Cons）：: 的时间复杂度为 O(1)。

• 列表拼接：++ 的时间复杂度为 O(n)，其中 n 是左侧列表的长度，需要复制左侧链表的所有节点。

• 尾部追加：形如 xs ++ [x] 的写法每次都要复制整个列表。如果在递归中反复这样做，整体复杂度会变成 O(n²)。

• 惯用做法：在头部用 (:) 插入，最后需要时调用一次 reverse（O(n)）。

无限列表¶

由于惰性求值，可以直接定义无限长的列表，只有被消费的部分才会真正生成：

-- 从 1 开始的无限自然数流：
ghci> take 5 [1..]
[1,2,3,4,5]

-- repeat：无限重复单个元素
ghci> take 4 (repeat "hello")
["hello","hello","hello","hello"]

-- replicate：生成指定长度的重复元素列表
ghci> replicate 5 'A'
"AAAAA"

-- cycle：把一个有限列表首尾相接无限循环
ghci> take 7 (cycle [1, 2, 3])
[1,2,3,1,2,3,1]

偏函数¶

标准库提供了提取端点元素的函数：

• head :: [a] -> a：获取首元素

• tail :: [a] -> [a]：获取除去首元素后的剩余列表

• last :: [a] -> a：获取最后一个元素

• init :: [a] -> [a]：获取除去最后一个元素后的前缀列表

用 Data.List.NonEmpty 在类型上保证非空¶

如果想从类型层面排除空列表，可以使用标准库自带的 Data.List.NonEmpty：

import Data.List.NonEmpty (NonEmpty(..))
import qualified Data.List.NonEmpty as NE

-- 定义为一个头部元素加一个可能为空的尾部列表：
-- data NonEmpty a = a :| [a]

safeHeadTotal :: NonEmpty a -> a
safeHeadTotal (x :| _) = x

NonEmpty a 的首元素在类型上保证存在，所以 safeHeadTotal 是全函数，不可能因为空列表而崩溃。

按数量切片¶

• take n xs：提取前 n 个元素（不足 n 个则返回全部，不会报错）。

• drop n xs：丢弃前 n 个元素，返回剩余部分。

• splitAt n xs：在索引 n 处拆分，等价于 (take n xs, drop n xs)。

ghci> take 3 [1..10]
[1,2,3]
ghci> drop 7 [1..10]
[8,9,10]
ghci> splitAt 4 "Haskell"
("Hask","ell")

按谓词切片¶

• takeWhile p xs：从左向右提取，遇到第一个不满足谓词的元素就停止。

• dropWhile p xs：从左向右跳过满足谓词的元素，返回从第一个不满足处开始的剩余部分。

• span p xs：等价于 (takeWhile p xs, dropWhile p xs)。

• break p xs：在第一个满足谓词处切开，等价于 span (not . p) xs。

ghci> takeWhile (< 5) [1, 2, 3, 4, 10, 2, 1]
[1,2,3,4]
ghci> dropWhile (< 5) [1, 2, 3, 4, 10, 2, 1]
[10,2,1]
ghci> span even [2, 4, 6, 7, 8, 10]
([2,4,6],[7,8,10])

map 与 filter¶

map :: (a -> b) -> [a] -> [b] 对每个元素应用函数，filter :: (a -> Bool) -> [a] -> [a] 只保留满足条件的元素。要一份名单，要一份及格名单：

ghci> map fst scores
["Alice","Bob","Carol","Dave"]
ghci> filter ((>= 60) . snd) scores
[("Alice",92),("Carol",75)]

(>= 60) . snd 是运算符截断与函数组合的搭配：先取二元组的第二项，再和 60 比较。这种“组合出一个谓词”的写法在列表处理里随处可见。

排序与分组¶

sort :: Ord a => [a] -> [a] 直接按元素排序。更常用的是 sortOn，按一个键函数排序；降序用 Data.Ord 的 Down 包一层把比较方向翻转。需要完全自定义比较逻辑时才用 sortBy。partition 一次遍历把列表拆成满足条件与不满足条件的两部分：

ghci> sortOn snd scores
[("Bob",58),("Dave",58),("Carol",75),("Alice",92)]
ghci> sortOn (Down . snd) scores
[("Alice",92),("Carol",75),("Bob",58),("Dave",58)]
ghci> partition ((>= 60) . snd) scores
([("Alice",92),("Carol",75)],[("Bob",58),("Dave",58)])

排序是稳定的，分数相同的 Bob 和 Dave 保持原有顺序。这几个函数都是“列表进、列表出”，所以可以用 . 串成管道。按分数从高到低列出及格者的名字：

passedNames :: [(String, Int)] -> [String]
passedNames = map fst . filter ((>= 60) . snd) . sortOn (Down . snd)

ghci> passedNames scores
["Alice","Carol"]

读的时候从右往左：先排序，再筛选，最后取名字。这是 Haskell 处理数据最常见的形状，对应其他语言里 stream().filter().map() 这类链式调用。

去重与查找¶

• nub :: Eq a => [a] -> [a]：去重，保留首次出现的顺序。它只要求 Eq，所以是 O(n²)，数据量大时应改用 Data.Set。

• find :: (a -> Bool) -> [a] -> Maybe a：找第一个满足条件的元素。

• lookup :: Eq a => a -> [(a, b)] -> Maybe b：在关联列表中按键查找。

ghci> nub (map snd scores)
[92,58,75]
ghci> find ((> 90) . snd) scores
Just ("Alice",92)
ghci> lookup "Carol" scores
Just 75

find 和 lookup 找不到时返回 Nothing 而不是抛异常，是全函数。lookup 每次都要线性扫描，键一多就该换成下一章的 Map。

展平与拼接¶

• concat :: [[a]] -> [a]：把嵌套列表压平为单层。

• concatMap :: (a -> [b]) -> [a] -> [b]：每个元素映射成一个列表，再压平。

• intercalate :: [a] -> [[a]] -> [a]：在子列表之间插入分隔列表再拼接，即其他语言的 join。

ghci> intercalate ", " (map fst scores)
"Alice, Bob, Carol, Dave"

脊柱是什么¶

有了节点的图景，就可以把列表拆成两部分来看：

1. 脊柱（Spine）：所有 (:) 节点沿 next 指针（Lisp 的 cdr）连成的骨架。它决定了列表有多长，以及在哪里结束。

2. 元素（Values）：每个节点的 value 字段（Lisp 的 car）指向的数据。

下图是 [1, 2, 3] 在内存中的结构。横向的一排是脊柱，元素挂在每个节点下方：

        graph LR
  subgraph spine["脊柱（Spine）"]
    direction LR
    C1["(:)"] --> C2["(:)"] --> C3["(:)"] --> Nil["[]"]
  end
  subgraph values["元素（Values）"]
    direction LR
    V1["1"]
    V2["2"]
    V3["3"]
  end
  C1 --> V1
  C2 --> V2
  C3 --> V3

  classDef spineNode fill:#dbe9ff,stroke:#3b6fb6;
  classDef valNode fill:#fff3d6,stroke:#c48a1a;
  class C1,C2,C3,Nil spineNode;
  class V1,V2,V3 valNode;
    

到这里为止，Haskell 列表和 C 链表、Lisp 列表没有本质区别。区别在下面。

与 C 链表的不同：两个字段都可以是未求值的¶

在 C 里，一个 Node 被 malloc 出来时，value 和 next 都已经填好了确定的地址，整条链表是现成的。

在 Haskell 里，(:) 的两个字段指向的都是堆上的对象，而这个对象可以是一个尚未计算的表达式，称为 Thunk。程序真正需要它的值时才会计算，算完后用结果替换掉原来的 Thunk（第 21 章会详细讨论这套机制）。这带来两个后果。

第一，沿脊柱走不会碰元素。求值 length 只需要顺着 next 指针数节点个数，每个节点的 value 字段指向什么，它根本不看：

ghci> length [undefined, undefined, undefined]
3

undefined 一旦被求值就会抛出异常。这里三个 undefined 都还是 Thunk，从头到尾没有人去碰它们，所以程序正常返回。换成 C 的说法，length 只读了每个节点的 next，从没解引用过 value。

第二，脊柱本身也可以只造一部分。next 字段同样可以是一个 Thunk，代表”剩下的列表还没生成”。前面见过的 [1..] 就是这样：它在堆上不是一条无限长的链，而是一个节点加上一个指向”1 之后的部分”的 Thunk。消费者每向后走一步，就多生成一个节点。

ghci> take 3 [1..]
[1,2,3]

-- length 需要走完整条脊柱，而这条脊柱永远走不完：
ghci> length [1..]
（不会返回）

在 C 里想做到同样的事，需要手写一个带状态的迭代器，或者把链表换成回调。Haskell 列表天然就是这种”按需生成”的结构，生产者与消费者用普通的 (:) 和模式匹配就能对接。

这两条性质合起来，就是 Haskell 能用列表做流式处理的原因。像 take 10 (filter even [1..]) 这样的表达式，filter 不会先把整个输入过一遍，而是在 take 每次索要下一个节点时才向 [1..] 多要一个数。内存中同时存在的只有正在处理的那几个节点，处理过的部分可以立刻被回收。