Prolog中如何使用difference-list实现列表旋转（前两元素移至末尾）

要实现将列表前两个元素移动到末尾的旋转（比如[a,b,c,d]转为[c,d,a,b]），用差列表可以做到常数时间复杂度，不需要遍历整个列表。

核心谓词实现 #

差列表的结构为实际列表段-开放尾部变量，可以直接通过模式匹配拆分前两个元素，再利用差列表开放尾部的特性直接把前两个元素拼到剩余段的末尾，不需要调用append遍历：

% 核心规则：匹配长度≥2的列表，将前两位A、B移到段尾
rotate_two_dl([A,B|Rest]-InputTail, Rest-[A,B|OutputTail]) :-
    InputTail = OutputTail.

% 可选边界规则：列表长度不足2时直接返回原列表，避免匹配失败
rotate_two_dl(List-Tail, List-Tail) :-
    List \= [_,_|_].

调用方式 #

处理普通封闭列表（也就是平时常用的常规Prolog列表）时，只需要把输入列表转为尾为[]的差列表传入，输出时取差列表的前半段（尾同样绑定为[]）即可：

% 常规示例
?- rotate_two_dl([a,b,c,d]-[], Result-[]).
Result = [c,d,a,b].

% 长度恰好为2的列表示例
?- rotate_two_dl([x,y]-[], Result-[]).
Result = [x,y].

% 长度不足2的列表示例（需要开启上面的边界规则）
?- rotate_two_dl([z]-[], Result-[]).
Result = [z].

?- rotate_two_dl([]-[], Result-[]).
Result = [].

效率说明 #

普通列表实现相同逻辑通常需要遍历列表完成拼接：

% 普通列表版本，时间复杂度O(n)
rotate_two_plain([A,B|Rest], Result) :-
    append(Rest, [A,B], Result).

这个版本需要遍历完整个剩余列表才能把前两个元素拼到末尾，而差列表版本仅靠模式匹配和变量绑定就完成操作，无论列表多长时间复杂度都是O(1)，这也是差列表在处理大列表拼接、语法解析等场景时的核心优势。

内容的提问来源于stack exchange，提问作者Nuwanthi Karunarathne