Erlang/OTP 完全指南 / 07 - 列表深入
第 07 章：列表深入 — Cons、列表操作与尾递归优化
列表是 Erlang 中最常用的数据结构。本章深入理解 cons 操作符、列表操作函数以及关键的尾递归优化。
7.1 Cons 操作符
7.1.1 列表的本质
Erlang 的列表是单向链表，由 cons 单元构成：
[1, 2, 3] = [1 | [2 | [3 | []]]]
┌───┐ ┌───┐ ┌───┐
│ 1 │──→│ 2 │──→│ 3 │──→ []
└───┘ └───┘ └───┘
7.1.2 Cons 操作符 |
%% 构造列表
[1 | [2, 3]]. %% [1, 2, 3]
[1 | []]. %% [1]
[a | [b, c, d]]. %% [a, b, c, d]
%% 多层 cons
[1 | [2 | [3 | []]]]. %% [1, 2, 3]
%% 非正规列表（Improper List）
%% 最后一个元素不是 []
[1 | 2]. %% [1 | 2]（不是 [1, 2]！）
[1, 2 | 3]. %% [1, 2 | 3]
7.1.3 正规列表 vs 非正规列表
| 类型 | 结构 | 示例 | is_list/1 |
|---|---|---|---|
| 正规列表 | 以 [] 结尾 | [1, 2, 3] | true |
| 非正规列表 | 以非 [] 值结尾 | [1 | 2] | true |
| 空列表 | [] | [] | true |
%% 判断是否是正规列表
is_proper_list([]) -> true;
is_proper_list([_ | T]) -> is_proper_list(T);
is_proper_list(_) -> false.
is_proper_list([1, 2, 3]). %% true
is_proper_list([1 | 2]). %% false
7.1.4 模式匹配中的 Cons
%% 提取头部和尾部
[H | T] = [1, 2, 3, 4]. %% H = 1, T = [2, 3, 4]
%% 提取多个元素
[A, B | Rest] = [1, 2, 3, 4]. %% A=1, B=2, Rest=[3,4]
%% 匹配特定前缀
[1, 2 | Rest] = [1, 2, 3, 4]. %% Rest = [3, 4]
[1, 2 | Rest] = [1, 3, 4]. %% 错误！不匹配
%% 匹配空列表
[] = []. %% ok
%% 匹配单元素列表
[X] = [42]. %% X = 42
7.2 列表操作函数
7.2.1 构造与合并
%% cons：在头部添加
[0 | [1, 2, 3]]. %% [0, 1, 2, 3]
%% ++：列表拼接
[1, 2] ++ [3, 4]. %% [1, 2, 3, 4]
%% ⚠️ 注意：++ 时间复杂度 O(左侧列表长度)
%% 追加单个元素（使用 ++ 或在尾部构造）
List = [1, 2, 3],
List ++ [4]. %% [1, 2, 3, 4]
%% 更高效的方式：先反转再 cons
lists:reverse([4 | lists:reverse([1, 2, 3])]).
7.2.2 常用列表函数
| 函数 | 作用 | 复杂度 | 示例 |
|---|---|---|---|
length(L) | 列表长度 | O(n) | length([1,2,3]) → 3 |
hd(L) | 头部 | O(1) | hd([1,2,3]) → 1 |
tl(L) | 尾部 | O(1) | tl([1,2,3]) → [2,3] |
lists:last(L) | 最后一个元素 | O(n) | lists:last([1,2,3]) → 3 |
lists:nth(N, L) | 第 N 个元素 | O(n) | lists:nth(2, [a,b,c]) → b |
lists:reverse(L) | 反转 | O(n) | lists:reverse([1,2,3]) → [3,2,1] |
lists:sort(L) | 排序 | O(n log n) | lists:sort([3,1,2]) → [1,2,3] |
lists:flatten(L) | 展平嵌套列表 | O(n) | lists:flatten([[1,2],[3]]) → [1,2,3] |
lists:member(X, L) | 是否包含 | O(n) | lists:member(2, [1,2,3]) → true |
lists:keyfind(K, N, T) | 按元组第 N 个元素查找 | O(n) | 见下文 |
lists:usort(L) | 去重排序 | O(n log n) | lists:usort([1,2,1,3,2]) → [1,2,3] |
lists:umerge(L1, L2) | 有序合并去重 | O(n) | 见下文 |
lists:zip(L1, L2) | 拉链合并 | O(n) | lists:zip([1,2],[a,b]) → [{1,a},{2,b}] |
lists:unzip(L) | 拉链拆分 | O(n) | lists:unzip([{1,a},{2,b}]) → {[1,2],[a,b]} |
lists:sublist(L, N) | 取前 N 个 | O(n) | lists:sublist([1,2,3,4], 2) → [1,2] |
lists:nthtail(N, L) | 第 N 个之后 | O(n) | lists:nthtail(2, [1,2,3,4]) → [3,4] |
lists:duplicate(N, X) | 重复 N 次 | O(n) | lists:duplicate(3, a) → [a,a,a] |
lists:seq(A, B) | 生成序列 | O(n) | lists:seq(1,5) → [1,2,3,4,5] |
7.2.3 关键元组列表操作
%% 元组列表 [{Key, Value}] 常用于模拟简单 Map
Proplist = [{name, "Alice"}, {age, 25}, {city, "Beijing"}].
%% 查找
lists:keyfind(name, 1, Proplist). %% {name, "Alice"}
lists:keyfind(height, 1, Proplist). %% false
%% 替换
lists:keyreplace(age, 1, Proplist, {age, 26}).
%% [{name,"Alice"},{age,26},{city,"Beijing"}]
%% 删除
lists:keydelete(age, 1, Proplist).
%% [{name,"Alice"},{city,"Beijing"}]
%% 排序
lists:keysort(2, Proplist).
%% 按第二个元素排序
%% ⚠️ 推荐：对于有 key-value 需求，优先使用 Map
7.3 递归与尾递归
7.3.1 递归基础
%% 经典递归：计算列表长度
%% 非尾递归版本
length([]) -> 0;
length([_ | T]) -> 1 + length(T).
%% 执行过程：
%% length([1,2,3])
%% = 1 + length([2,3])
%% = 1 + (1 + length([3]))
%% = 1 + (1 + (1 + length([])))
%% = 1 + (1 + (1 + 0))
%% = 1 + (1 + 1)
%% = 1 + 2
%% = 3
%%
%% 问题：需要保存大量中间状态（栈帧），长列表可能栈溢出
7.3.2 尾递归优化
%% 尾递归版本（使用累加器）
%% Erlang 的编译器可以将尾递归优化为循环（无栈溢出风险）
length_tail(L) ->
length_tail(L, 0).
length_tail([], Acc) -> Acc;
length_tail([_ | T], Acc) ->
length_tail(T, Acc + 1). %% 最后一个调用（尾位置）
%% 执行过程：
%% length_tail([1,2,3], 0)
%% length_tail([2,3], 1)
%% length_tail([3], 2)
%% length_tail([], 3)
%% = 3
%%
%% 不需要保存中间状态，常数内存！
7.3.3 尾递归的关键条件
一个函数是尾递归的，当且仅当递归调用是函数的最后一个操作：
%% ✅ 尾递归：递归调用在尾位置
sum([], Acc) -> Acc;
sum([H | T], Acc) -> sum(T, H + Acc).
%% ❌ 非尾递归：递归调用后还有 +1 操作
len([]) -> 0;
len([_ | T]) -> 1 + len(T).
%% 等价于：Tmp = len(T), 1 + Tmp
%% ❌ 非尾递归：递归调用后还有 cons 操作
reverse([]) -> [];
reverse([H | T]) -> reverse(T) ++ [H].
%% 等价于：Tmp = reverse(T), Tmp ++ [H]
%% ✅ 尾递归版本的 reverse
reverse(L) -> reverse(L, []).
reverse([], Acc) -> Acc;
reverse([H | T], Acc) -> reverse(T, [H | Acc]).
7.3.4 常见尾递归模式
%% 模式一：累加器
sum(L) -> sum(L, 0).
sum([], Acc) -> Acc;
sum([H | T], Acc) -> sum(T, Acc + H).
%% 模式二：构建列表（注意顺序：结果会反转）
filter(Pred, L) -> filter(Pred, L, []).
filter(_Pred, [], Acc) -> lists:reverse(Acc); %% 反转回来
filter(Pred, [H | T], Acc) ->
case Pred(H) of
true -> filter(Pred, T, [H | Acc]);
false -> filter(Pred, T, Acc)
end.
%% 模式三：多累加器
min_max([]) -> {error, empty};
min_max([H | T]) -> min_max(T, H, H).
min_max([], Min, Max) -> {Min, Max};
min_max([H | T], Min, Max) ->
min_max(T, min(H, Min), max(H, Max)).
%% 模式四：带停止条件的递归
find(_Pred, []) -> not_found;
find(Pred, [H | T]) ->
case Pred(H) of
true -> {found, H};
false -> find(Pred, T)
end.
7.3.5 尾递归 vs 非尾递归性能对比
%% 性能测试
bench() ->
List = lists:seq(1, 1000000),
{T1, _} = timer:tc(fun() -> length(List) end),
{T2, _} = timer:tc(fun() -> length_tail(List) end),
io:format("非尾递归: ~p μs~n", [T1]),
io:format("尾递归: ~p μs~n", [T2]).
%% 结果（大致）：
%% 非尾递归: 15000 μs（还可能栈溢出）
%% 尾递归: 5000 μs（常数内存）
⚠️ 注意：在现代 BEAM 中，编译器可能自动优化某些非尾递归模式，但不要依赖于此。
7.4 常用列表算法
7.4.1 快速排序
%% 经典快速排序（简洁但非尾递归）
quicksort([]) -> [];
quicksort([Pivot | Rest]) ->
quicksort([X || X <- Rest, X < Pivot]) ++
[Pivot] ++
quicksort([X || X <- Rest, X >= Pivot]).
%% 更高效的就地排序使用 lists:sort/1
%% lists:sort 使用 merge sort，时间复杂度 O(n log n)
7.4.2 合并有序列表
%% 合并两个有序列表
merge([], L) -> L;
merge(L, []) -> L;
merge([H1 | T1], [H2 | T2]) when H1 =< H2 ->
[H1 | merge(T1, [H2 | T2])];
merge([H1 | T1], [H2 | T2]) ->
[H2 | merge([H1 | T1], T2)].
%% 或使用 lists:merge/2
lists:merge([1, 3, 5], [2, 4, 6]). %% [1,2,3,4,5,6]
7.4.3 分组与频率统计
%% 频率统计
frequency(List) ->
frequency(List, #{}).
frequency([], Acc) -> Acc;
frequency([H | T], Acc) ->
Count = maps:get(H, Acc, 0),
frequency(T, Acc#{H => Count + 1}).
frequency([a, b, a, c, b, a]).
%% #{a => 3, b => 2, c => 1}
%% 分组
group_by(Fun, List) ->
group_by(Fun, List, #{}).
group_by(_Fun, [], Acc) -> Acc;
group_by(Fun, [H | T], Acc) ->
Key = Fun(H),
Group = maps:get(Key, Acc, []),
group_by(Fun, T, Acc#{Key => [H | Group]}).
group_by(fun(X) -> X rem 2 end, [1,2,3,4,5,6]).
%% #{0 => [6,4,2], 1 => [5,3,1]}
7.4.4 列表去重
%% 使用 Map 去重（保持顺序）
unique(L) ->
unique(L, #{}, []).
unique([], _Seen, Acc) ->
lists:reverse(Acc);
unique([H | T], Seen, Acc) ->
case maps:is_key(H, Seen) of
true -> unique(T, Seen, Acc);
false -> unique(T, Seen#{H => true}, [H | Acc])
end.
unique([1, 2, 3, 1, 2, 4, 3, 5]).
%% [1, 2, 3, 4, 5]
%% 或使用 lists:usort/1（排序去重，不保持顺序）
lists:usort([1, 2, 3, 1, 2, 4, 3, 5]).
%% [1, 2, 3, 4, 5]
7.5 IO List — 高效字符串构建
7.5.1 IO List 原理
%% 传统字符串拼接：每次 ++ 都复制整个列表
%% "Hello" ++ " " ++ "World" 需要多次复制
%% IO List：嵌套的二进制/整数/IO list，最后一次性输出
IOList = ["Hello", " ", "World"].
io:format("~s~n", [IOList]). %% Hello World
%% IO List 可以任意嵌套
Nested = [["He", "llo"], " ", [["Wo", "rld"]]].
io:format("~s~n", [Nested]). %% Hello World
%% 检查大小
iolist_size(IOList). %% 11
7.5.2 IO List vs 字符串拼接
%% 方式一：字符串拼接（O(n²)）
build_message_bad(Name) ->
"Hello, " ++ Name ++ "! Welcome to Erlang.".
%% 方式二：IO List（O(n)）
build_message_good(Name) ->
["Hello, ", Name, "! Welcome to Erlang."].
%% IO List 在输出时一次性处理，无需中间字符串
io:format("~s~n", [build_message_good("Alice")]).
7.5.3 实用场景
%% 构建 HTML
html_list(Items) ->
["<ul>\n",
[[" <li>", Item, "</li>\n"] || Item <- Items],
"</ul>"].
html_list(["Apple", "Banana", "Cherry"]).
%% "<ul>\n <li>Apple</li>\n <li>Banana</li>\n <li>Cherry</li>\n</ul>"
%% 构建 JSON
json_object(Pairs) ->
["{",
lists:join(", ", [[json_escape(K), ":", json_value(V)] || {K, V} <- Pairs]),
"}"].
7.6 实战：词频统计
%% word_count.erl
-module(word_count).
-export([count/1, top_n/2]).
-spec count(string()) -> #{string() => integer()}.
count(Text) ->
Words = string:lexemes(string:lowercase(Text), " ,.!?;:\n\t"),
frequency(Words, #{}).
-spec top_n(#{string() => integer()}, integer()) -> [{string(), integer()}].
top_n(FreqMap, N) ->
Sorted = lists:sort(fun({_, A}, {_, B}) -> A >= B end,
maps:to_list(FreqMap)),
lists:sublist(Sorted, N).
%% 内部
frequency([], Acc) -> Acc;
frequency([W | Rest], Acc) ->
Count = maps:get(W, Acc, 0),
frequency(Rest, Acc#{W => Count + 1}).
1> word_count:count("the cat sat on the mat the cat").
#{"cat" => 2, "mat" => 1, "on" => 1, "sat" => 1, "the" => 3}
2> word_count:top_n(ans, 3).
[{"the",3},{"cat",2},{"mat",1}]
7.7 注意事项
⚠️ 性能陷阱
| 操作 | 复杂度 | 说明 |
|---|---|---|
[H|T] | O(1) | cons 操作 |
++ | O(n) | 左侧列表越长越慢 |
length(L) | O(n) | 需要遍历整个列表 |
lists:reverse(L) | O(n) | 但它是尾递归的 |
lists:nth(N, L) | O(N) | 需要遍历 N 个元素 |
lists:member(X, L) | O(n) | 线性搜索 |
💡 最佳实践
- 始终使用尾递归处理长列表
- 使用累加器模式构建新列表
- 用 IO list 代替字符串拼接
- 频繁按 key 查找时，使用 Map 代替元组列表
- 避免在列表末尾追加元素（
++ [X]），使用[X | Acc]然后反转 lists:reverse/1是 O(n) 且高效，善用它
7.8 扩展阅读
上一章：06 - 函数进阶 下一章：08 - 元组与 Map