Prolog Sorting a List of Structure, arithmetic error

1
votes

I've been trying to sort a list of structure.

The structure is like this

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

And the list would be like this

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

I want to sort the list from greatest weight to least. Like this:

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

So far I have this:

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).

I've tried with a list of two persons and it works:

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

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

But when I try with a list of 3 or more person appears an error:

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

no
?-

Can anybody help?

2
listprologclpfd
You don't actually have person(Name, Weight). written as a fact, do you? - lurker
I don't see >=/2 being used anywhere in the code you show, but the error is clearly regarding this operator. Perhaps there's an issue in your insertInPlace/3 predicate, which isn't shown. - lurker
@Danick: Is there a reason why you have edited out the clpfd tag? It seems relevant for your question; stackoverflow.com/tags/clpfd/info. - Matt
@Danick: The tag is not meant to indicate what you are allowed to use; it is meant to help later readers who are looking for this topic find pertaining questions! Please restore the clpfd tag for this question, since CLP(FD) constraints are the solution for such problems. This is also clearly reflected in both answers. - mat
@Matt: So why this now? - false

2 Answers

5
votes

The way I see it your insertion-sort is okay, except for the second clause of 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).

Sample query:

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

The error comes from the fact that the built-in arithmetic operators like < and =< only work on instantiated terms (i.e. 1 < 2 is true but 1 < X throws the exception you mentioned). If you use constraints, the code becomes something like:

:- 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).

I assume your insertInPlace predicate is similar to smallest_in_rest_vars, only without the explicit list of variables Vs which is useful for labeling (which we don't need in this case). If I would not use constraints, I'd get the following error when I query with your list:

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) ?

The reason is that the clause which is marked in the example, we don't know anything about the new person N1 yet, which leads to a comparison 80 < A1. I found using clpfd much easier to think about, but when you give us your insertInPlace, we might find a non-clp solution too.