如何用Prolog实现Gnome sort？新手编写的排序代码运行失败该如何解决

你写的代码存在3个核心错误：

• 语法错误：Prolog不支持把谓词last_element/2直接作为参数写在子句头里，谓词调用必须放在规则的body部分，你写的insert(X, last_element(P,[Y|T]),[Y|NT])完全不符合语法，运行会直接报错。
• 逻辑不匹配：你现在的外层递归结构是典型的插入排序逻辑（遍历原列表逐个插入到有序累加器），完全没有实现侏儒排序核心的「当前元素小于前一个时交换、回退一步比较」的逻辑。
• 变量未绑定：错误书写的insert分支里的P、NT等变量没有绑定来源，运行时会因为变量未实例化报错。

我们按照侏儒排序的原生逻辑实现如下：

% 对外暴露的排序接口
gnome_sort(List, Sorted) :-
    gnome_sort(List, 0, Sorted).

% 索引走到列表末尾时，当前列表就是排序结果
gnome_sort(List, Index, List) :-
    length(List, Len),
    Index >= Len,
    !.

% 索引为0时直接往前走一步
gnome_sort(List, 0, Sorted) :-
    NextIndex is 1,
    gnome_sort(List, NextIndex, Sorted),
    !.

% 当前元素 >= 前一个元素，往前走一步
gnome_sort(List, Index, Sorted) :-
    nth0(Index, List, Current),
    PrevIndex is Index - 1,
    nth0(PrevIndex, List, Prev),
    Current >= Prev,
    NextIndex is Index + 1,
    gnome_sort(List, NextIndex, Sorted),
    !.

% 当前元素 < 前一个元素，交换两个元素，回退一步
gnome_sort(List, Index, Sorted) :-
    nth0(Index, List, Current),
    PrevIndex is Index - 1,
    nth0(PrevIndex, List, Prev),
    Current < Prev,
    swap(List, PrevIndex, Index, SwappedList),
    NextIndex is Index - 1,
    gnome_sort(SwappedList, NextIndex, Sorted).

% 辅助交换列表中两个位置的元素
swap(List, I, J, Result) :-
    nth0(I, List, ElemI),
    nth0(J, List, ElemJ),
    replace_nth(List, I, ElemJ, Tmp),
    replace_nth(Tmp, J, ElemI, Result).

% 辅助替换列表指定位置元素
replace_nth([_|T], 0, NewVal, [NewVal|T]).
replace_nth([H|T], N, NewVal, [H|ResT]) :-
    N > 0,
    NextN is N - 1,
    replace_nth(T, NextN, NewVal, ResT).

运行gnome_sort([3,1,4,1,5,9,2,6], Sorted).会得到结果Sorted = [1, 1, 2, 3, 4, 5, 6, 9]。

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