Prolog 列表操作：[H|T] 模式

Prolog 处理列表的核心机制是模式匹配，其中最关键的工具就是 [H|T] 模式。这种模式将列表拆分为“头部（Head）”和“尾部（Tail）”，是实现递归遍历、搜索和构建列表的基础。头部是列表的第一个元素，尾部则是除去头部后剩余的列表（注意：尾部始终是一个列表）。

在数学上，一个非空列表 $L$ 可以表示为：

$$ L = [H] \cup T $$

其中 $H$ 是一个元素，$T$ 是一个列表。理解这一结构是编写 Prolog 列表处理程序的第一步。

1. 理解 [H|T] 的基本匹配

通过交互式查询，可以直观地看到 [H|T] 如何拆分列表。

打开 SWI-Prolog 终端。

输入 以下查询并观察结果：

?- [H|T] = [apple, banana, cherry].

系统会自动匹配变量：

• H 绑定为 apple。
• T 绑定为 [banana, cherry]。

输入 另一个查询测试单元素列表：

?- [X|Y] = [orange].

系统输出：

• X = orange。
• Y = []。
• 这里 Y 是空列表，这是递归终止的关键条件。

输入 尝试对空列表进行模式匹配：

?- [A|B] = [].

系统输出 false.。因为空列表没有头部，无法与 [H|T] 模式匹配。这一特性决定了递归的基准情况。

2. 编写递归遍历规则

大多数列表操作（如计算长度、查找元素、求和）都遵循“头部处理 + 尾部递归”的结构。以编写一个计算列表长度的谓词 list_length/2 为例。

定义 计算长度的两个规则：

1. 基准情况：空列表的长度为 0。
2. 递归步骤：列表 [H|T] 的长度是 1 加上尾部 T 的长度。

编写 代码如下：

% 规则 1：空列表长度为 0
list_length([], 0).

% 规则 2：非空列表长度为 尾部长度 + 1
list_length([_H|T], Length) :-
    list_length(T, TailLength),
    Length is TailLength + 1.

编译 上述代码。

测试 谓词：

?- list_length([a, b, c, d], L).

系统输出 L = 4。

为了更清晰地展示递归执行流程，下图描述了 list_length([a, b], L) 的推导过程。

3. 实现列表成员检查

检查元素是否在列表中（通常称为 member/2）是另一个经典场景。逻辑是：如果元素是头部，则成功；否则检查元素是否在尾部。

定义 成员检查规则：

1. 命中头部：如果 X 是列表 [H|T] 的头部 H，则匹配成功。
2. 搜索尾部：如果 X 不是头部，则检查 X 是否在尾部 T 中。

编写 代码如下：

% 规则 1：X 是列表的头部
member(X, [X|_]).

% 规则 2：X 在列表的尾部中
member(X, [_|T]) :-
    member(X, T).

注意 代码中使用了匿名变量 _。在规则 1 中，我们不关心尾部是什么；在规则 2 中，我们不关心头部是什么。

测试 该谓词：

?- member(b, [a, b, c]).

系统输出 true.。

测试 不存在的元素：

?- member(d, [a, b, c]).

系统输出 false.。

4. 构造新列表

除了读取数据，[H|T] 还常用于构造列表。假设我们要编写一个规则，将输入列表中的每个元素复制一份（例如 [a, b] 变成 [a, a, b, b]）。

定义 复制规则 duplicate/2：

1. 基准情况：空列表映射为空列表。
2. 递归步骤：处理头部 H，将其构造为 [H, H]，然后递归处理尾部。

编写 代码如下：

% 规则 1：空列表进，空列表出
duplicate([], []).

% 规则 2：将 H 变为 [H, H]，并追加处理后的 T
duplicate([H|T], [H, H|Rest]) :-
    duplicate(T, Rest).

观察 [H, H|Rest] 的用法。这里不仅利用 [H|T] 解构了输入列表，还利用 | 符号构造了输出列表。Rest 变量最终绑定为对尾部进行 duplicate 处理后的结果。

测试 该谓词：

?- duplicate([1, 2], Result).

系统输出 Result = [1, 1, 2, 2]。

5. 调试常见错误

在使用 [H|T] 模式时，新手常犯两类错误。

错误 1：混淆元素与列表

编写 如下错误代码：

wrong_example([H|T], [H|T]).

查询：

?- wrong_example([a], [a]).

结果为 false。
原因：[a] 匹配为 H=a, T=[]。右边 [H|T] 变为 [a|[]] 即 [a]。这看起来是对的，但在处理多元素或复杂结构时，这种直接“复制”往往导致逻辑意图不明。更常见错误是：

编写：

bad_sum([H|T], Sum) :-
    Sum is H + T. % 错误：H是数字，T是列表，不能直接相加

修正：必须递归地将 T 转化为数字。

错误 2：忘记基准情况

编写 缺少空列表处理的代码：

bad_process([H|T]) :-
    write(H),
    bad_process(T).

查询：

?- bad_process([1, 2]).

输出 12 后程序崩溃或报错，因为最后会调用 bad_process([])，而该调用无法匹配任何规则。

修正：始终添加针对空列表的规则。

6. 进阶：累加器模式

对于长列表，普通递归可能导致栈溢出。使用累加器是更高效的方式。我们要用“尾递归”计算列表长度。

定义 list_length_acc/3：

• 参数 1：输入列表。
• 参数 2：当前累加长度（初始为 0）。
• 参数 3：最终结果。

编写 代码如下：

% 公共接口，隐藏累加器参数
list_length_fast(List, Length) :-
    list_length_acc(List, 0, Length).

% 规则 1：列表为空，将累加器的值赋给 Length
list_length_acc([], Acc, Acc).

% 规则 2：列表非空，Acc + 1，继续递归
list_length_acc([_H|T], Acc, Length) :-
    NewAcc is Acc + 1,
    list_length_acc(T, NewAcc, Length).

测试 性能（在大列表上差异明显）：

?- list_length_fast([a, b, c], L).

系统输出 L = 3。

下表总结了普通递归与累加器模式的区别：