Prolog对结构列表进行排序,算术错误

Question

我一直试图对结构列表进行排序.

结构是这样的

% person(Name, Weight).
person(tom, 65).
person(dan, 70).
person(mike, 80).

列表就是这样的

List = [person(tom, 65), person(dan, 70), person(mike, 80)].

我想从最大的权重到最小的排序.像这样:

SortList = [person(mike, 80), person(dan, 70), person(tom, 65)].

到目前为止我有这个:

sortListPerson([], []).
sortListPerson([person(NameP, WP)|Rest], Result):-
     sortListPerson(Rest, List),
     insertPerson(person(NameP, WP), List, Result).

insertPerson(person(NameP, WP), [], [person(NameP, WP)]).
insertPerson(person(NameP1, WP1), [person(NameP2, WP2)|Rest],   [person(NameP1, WP1)|List]):-
    integer(WP1),
    integer(WP2),
    WP1 @>= WP2,
    insertPerson(person(NameP2, WP2), Rest, List).
insertPerson(person(NameP1, WP1), [person(NameP2, WP2)|Rest], [person(NameP2, WP2)|List]):-
    integer(WP1),
    integer(WP2),
    WP1 @< WP2,
    insertInPlace(person(NameP1, WP1), Rest, List).

我尝试过两个人的名单并且它有效:

?- sortListPerson([person(a, 10), person(b, 30)], SortList).

SortList = [person(b,30),person(a,10)] ? ;

但是当我尝试使用3个或更多人的列表时出现错误:

?- sortListPerson([person(a, 10), person(b, 30), person(c, 40)], SortList).
{ERROR: arithmetic:>=/2 - expected an arithmetically evaluable expression, found person(a,10)}

no
?- 

有人可以帮忙吗？

Answer 1

这个错误来自这样一个事实:内置的算术运算符喜欢<并且=<只对实例化的术语起作用(即为1 < 2真,但1 < X抛出你提到的异常).如果使用约束,代码将变为:

:- use_module(library(clpfd)).

smallest_in_rest_vars(person(N,A), [person(N,A)], [], [A]).
smallest_in_rest_vars(person(N,A), [person(N1,A1) | Ps],    % <-- this one fails without clpfd
                      [person(N1,A1) | Rs], [A1|Vs] ) :-
    A #=< A1,
    smallest_in_rest_vars(person(N,A), Ps, Rs, Vs).
smallest_in_rest_vars(person(N1,A1), [person(N1,A1) | Ps],
                      [person(N,A) | Rs], [A1|Vs] ) :-
    A #> A1,
    smallest_in_rest_vars(person(N,A), Ps, Rs, Vs).

list_sorted([],[], []).
list_sorted(L, [Smallest|SortedRest], Vars) :-
    smallest_in_rest_vars(Smallest, L, Rest, Vars0),
    list_sorted(Rest, SortedRest, Vars1),
    append(Vars0, Vars1, Vars).

我假设您的insertInPlace谓词类似于smallest_in_rest_vars,只是没有明确的变量列表,Vs这对标记很有用(在这种情况下我们不需要).如果我不使用约束,当我查询你的列表时,我会收到以下错误:

ERROR: =</2: Arguments are not sufficiently instantiated
   Exception: (9) smallest_in_rest_vars(_G400, [person(tom, 65), person(dan, 70), person(mike, 80)], [person(_G406, _G407)], _G462) ? 

原因是在示例中标记的条款,我们对新人N1还没有任何了解,这导致了比较80 < A1.我发现使用clpfd更容易思考,但是当你给我们的时候insertInPlace,我们也可能找到一个非clp解决方案.

Answer 2

我看到你插入排序的方式是可以的,除了第二个条款insertPerson/3:

:- use_module(library(clpfd)).

insertPerson(person(N,W), [], [person(N,W)]).
insertPerson(person(N1,W1), [person(N2,W2)|Ps], [person(N1,W1),person(N2,W2)|Ps]) :-
   W1 #>= W2.                                   % If Ps is in order, we're done!
insertPerson(person(N1,W1), [person(N2,W2)|Ps], [person(N2,W2)|Qs]) :-
   W1 #< W2,
   insertPerson(person(N1,W1), Ps, Qs).

示例查询:

?- sortListPerson([person(tom,65),person(dan,70),person(mike,80)], Xs).
Xs = [person(mike,80),person(dan,70),person(tom,65)] ;
false.