Prolog中如何排序[peter-3,mark-2,sam-1]类列表？插入排序返回false排查

我来帮你排查这个插入排序的问题！你的代码里有两个明显的错误导致它返回false，没法正常完成排序：

错误分析 #

• 第一个insert子句的条件写错了：你写的N1>N1是个永远不成立的条件（一个数不可能大于它自己），这会导致所有需要往后插入的情况都匹配失败，应该改成N1 > N2——这样才是比较当前元素的数字N1和列表头部元素的数字N2，判断是否需要继续往后找插入位置。
• 第一个insert子句的结果列表结构错误：你返回的是[Y|NT]，但原列表的元素都是原子-数字的结构（比如peter-3），这里只保留了Y（比如peter），丢掉了-3的部分，应该改成[Y-N2|NT]，保持元素的完整结构。

修复后的完整代码 #

insert_sort(List,Sorted):-
    i_sort(List,[],Sorted).

i_sort([],Acc,Acc).

i_sort([H-N1|T],Acc,Sorted):-
    insert(H-N1,Acc,NAcc),
    i_sort(T,NAcc,Sorted).

% 修复后的第一个insert子句：修正条件和结果结构
insert(X-N1,[Y-N2|T],[Y-N2|NT]):-
    N1 > N2,
    insert(X-N1,T,NT).

insert(X-N1,[Y-N2|T],[X-N1,Y-N2|T]):-
    N1 =< N2.

insert(X-N1,[],[X-N1]).

测试验证 #

现在运行你的目标排序需求，就能得到正确结果了：

?- insert_sort([peter-3, mark-2, sam-1], Sorted).
Sorted = [sam-1, mark-2, peter-3].

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