Prolog中实现flip谓词判断两列表互为逆序的高效方案

你目前「反转第一个列表后与第二个列表比对」的思路是完全正确的，已经达到了这个问题的最坏时间复杂度下界——任何判断两个列表是否互为逆序的实现，都至少需要遍历两个列表的全部元素一次，无法低于O(n)的时间开销。
最简洁的基础实现可以直接复用Prolog内置的reverse/2谓词：

flip(Lst1, Lst2) :-
    reverse(Lst1, Lst2).

这个实现可以完全覆盖你的示例场景：

• 匹配成功：flip([a,b,c,d], [d,c,b,a])、flip([a], [a])
• 匹配失败：flip([a,b], [b,c])

直接调用内置reverse的写法虽然简洁，但在两个列表都完全已知、且长度差异较大的场景下，存在无意义的计算开销：内置reverse会完整遍历第一个列表生成全量反转结果后，才会开始和第二个列表做比对，如果两个列表长度差异很大，会浪费大量时间遍历长列表构造完全不需要的反转内容。
针对这类场景，最高性价比的优化是增加双向同步的长度前置校验，避免单独遍历单个列表拿长度的冗余操作：

• 不要用length(L1, Len1), length(L2, Len2)这种方式校验长度：这种实现会把两个列表从头到尾遍历一遍拿到长度，即使两个列表长度差很大，也要走完全程，和直接调用reverse的开销几乎没有区别。
• 改用逐位同步遍历两个列表的头来做长度校验：只要任意一个列表先遍历到空，就可以立刻判断两个列表长度是否相等，不需要遍历完长列表的剩余部分。比如一个长度10000的列表和一个长度2的列表做校验，只需要3次递归就可以发现长度不等，比逐列表遍历拿长度的方式快几个数量级。

下面的实现兼顾了双向求值能力（既可以从已知Lst1生成匹配的Lst2，也可以从已知Lst2反推Lst1），同时在长度差异较大的场景下可以快速失败：

% 同步长度校验：两个列表逐位取头，同时遍历到空才说明长度相等
same_length([], []).
same_length([_|T1], [_|T2]) :-
    same_length(T1, T2).

% flip谓词主逻辑
flip([], []).
flip(L1, L2) :-
    same_length(L1, L2), % 先快速校验长度，不等直接失败
    reverse(L1, L2).

• 长度不等的场景：校验过程仅需遍历min(len(L1), len(L2)) +1次递归操作，相比直接调用reverse的len(L1) + len(L2)次操作，当两个列表长度差异较大时可以获得数量级的性能提升
• 长度相等的场景：校验过程会完整遍历两个列表一次，相比直接调用reverse的实现仅多一次O(n)的遍历开销，但因为遍历是逐位拿头操作，没有额外的列表构造开销，实际开销极低
• 完全兼容双向求值：当任意一个列表存在自由变量时，same_length会正常绑定对应长度的自由变量，不会引入不必要的约束，和内置reverse的行为完全一致

内容的提问来源于stack exchange，提问作者Vortca 2