序言中的选择排序

Question

我是 Prolog 的新手，我正在尝试对选择进行排序。这是我拥有的：

ssort([],[]).
ssort([M|S],L):-min(M,L),remove(M,L,N),ssort(S,N).

min(M,[M]).
min(M,[H,T]):-min(N,T),min2(M,H,N).

min2(A,A,B):-less(A,B).
min2(B,A,B):-not(less(A,B)).

less(A,B):-(A<B).

append([],B,B).
append([H|A],B,[H|AB]):-append(A,B,AB).

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

但是当我尝试这个时：

ssort(S,[5,3,1]),write(S).

我得到 false，无论我尝试什么。你能告诉我如何真正对列表进行排序并得到写在 S 中的结果吗？

Answer 1

正如@Boris 指出的那样，主要错误在 min/2 谓词中，因为它需要第三个参数才能 return 该参数中的最小元素。通过一些小的更改，代码如下所示：

ssort([],[]).
ssort([M1|S],[H|T]):-min(H,T,M1),remove(M1,[H|T],N),ssort(S,N).

min(M,[],M).
min(M,[H|T],M1):-min2(M,H,N),min(N,T,M1).

min2(A,B,A):-less(A,B).
min2(A,B,B):-not(less(A,B)).

less(A,B):-(A<B).

append([],B,B).
append([H|A],B,[H|AB]):-append(A,B,AB).

remove(X,L,N):-append(A,[X|B],L),append(A,B,N).

示例：

?- ssort(S,[5,3,1]).
S = [1, 3, 5] ;
false.

?- ssort(S,[5,3,1,7]).
S = [1, 3, 5, 7] ;
false.

编辑：

正如@Will Ness 正确指出的那样，唯一的错误是 min(M,[H,T]) 中的逗号，因此更改为 min(M,[H|T]) 它工作正常！！！我认为 min/2 谓词效果不佳，所以我在上面的答案中对其进行了更改，但最终没有必要这样做。

Answer 2

这里是您至少可以定位程序中的错误的一般方法。如果查询失败，只需从程序中删除目标即可。如果剩余片段仍然失败，则该片段中一定有错误。

:- op(950,fy,*).
*_.

ssort(_/*[]*/,[]).
ssort(_/*[M|S]*/,L):-
   min(_/*M*/,L),
   * remove(M,L,N),
   * ssort(S,N).

min(M,[M]).
min(M,[H,T]):-
   * min(N,T),
   * min2(M,H,N).

?- ssort(S,[5,3,1]).

因为这个片段失败了，你原来的程序也会失败。你需要在剩下的部分概括一些东西。

序言中的选择排序

Selection sort in prolog

prolog

program-slicing