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.

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

Prolog Sorting a List of Structure, arithmetic error

list

prolog

clpfd