Prolog: Trouble sorting a list

Question

I have a list like this that I am trying to sort:

[(tim,3),(tom,4),(jane,2),(mary,3)]

I want to rearrange it so it orders in descending numbers:

[(tom,4),(mary,3),(tim,3),(jane,2)]

I have a predicate that extract a list for a given number:

extractor([],[],[],_).
extractor([(Name, Number)|List], [(Name, Number)|NewList], Extracted, Number):-
   extractor(List, NewList, Extracted, Number),
   !.
extractor([A|List], NewList,[A|Extracted], Number):-
   extractor(List, NewList, Extracted, Number).

So given a number it should give me a list of the elements with those numbers and have an extracted list without those elements.

Then I put that through the sort. Where I have a highest number, and it should loop through from 0 to that number, extracting any elements for that number. Until I have the sorted list.

numberSort([], _, 0).
numberSort(Unsorted, Sorted, HighestNumber):-
   extractor(Unsorted, Sorted, ExtractedList, Counter),
   numberSort(ExtractedList, Sorted, Counter),
   HighestNumber is 1 + Counter.
numberSort(Unsorted, Sorted, HighestNumber):-
   numberSort(Unsorted, Sorted, Counter),
   HighestNumber is 1 + Counter.

However, when I try this it just goes through an infinite loop. Can someone help me out and show me where I am going wrong? Thanks,

Answer 1

First of all, before looking at your code in detail, lets make clear what the relation should describe. You have pairs of the form (Name, Number) — as an aside, usually Prolog code prefers to write Name-Number instead. And you want a relation between two list of pairs, the second being a permutation with pairs descending by number.

What about negative numbers? It seems you are not considering such a case. At least, 0 occurs in your program which suggests that you intended it to be the highest number, should list be [].

Why does your program loop? You might want to go through a debugger to see what "happens" step-by-step. Well, why not? Try it out! You will see that you see a lot of unrelated stuff happening. More effectively is to use a failure-slice like so:

numberSort([], _, 0) :- false.
numberSort(Unsorted, Sorted, HighestNumber) :- false,
   extractor(Unsorted, Sorted, ExtractedList, Counter),
   numberSort(ExtractedList, Sorted, Counter),
   HighestNumber is 1 + Counter.
numberSort(Unsorted, Sorted, HighestNumber) :-
   numberSort(Unsorted, Sorted, Counter), false,
   HighestNumber is 1 + Counter.

?- numberSort( [(tim,3),(tom,4),(jane,2),(mary,3)], Sorted, H).

This fragment of your program still loops, and therefore also your original program loops. You do not need to see more than that! Worse: Your program loops for all queries! To fix this problem you have to fix at least something in the remaining visible part. That might look surprising to you after all you spent some time with extractor/4 but regardless of its definition, this loop occurs.

The other issue is with extractor/4:

| ?- extractor([(tim,3),(jane,4)], Xs, Ys, 3).
Xs = [(tim,3)],
Ys = [(jane,4)] ? ;
no
| ?- extractor([(tim,3),(jane,4)], [], Ys, 3).
Ys = [(tim,3),(jane,4)] ? ;
no

Isn't this odd? The first query succeeds (probably according to you expectations), the second should thus fail, but it succeeds. The culprit being the cut which you placed at the end of the rule. We say, the predicate is not steadfast. I'd suggest to write this predicate in a manner that you do not need any cut at all.

Answer 2

Here is how you can debug your code

?- leash(-all),trace,numberSort([(tim,3),(tom,4),(jane,2),(mary,3)],L,N).
   Call: (7) numberSort([ (tim, 3), (tom, 4), (jane, 2), (mary, 3)], _G7370, _G7371)
   ...
   Exit: (8) extractor([ (tim, 3), (tom, 4), (jane, 2), (mary, 3)], [ (tim, 3), (mary, 3)], [ (tom, 4), (jane, 2)], 3)
   Call: (8) numberSort([ (tom, 4), (jane, 2)], [ (tim, 3), (mary, 3)], 3)
    ...
   Call: (11) extractor([], [ (tim, 3), (mary, 3)], _G7590, _G7602)
   Fail: (11) extractor([], [ (tim, 3), (mary, 3)], _G7590, _G7602)
   ...

the call (8) seems to have its arguments too much instantiated, consequently extractor fails. It's not easy to correct the code, because I don't understand completely the logic.

I think there should be some append around, or you should use difference lists.

OTOH, a much easier way it's to use the library. There is a builtin predsort that allows to specify a predicate for comparison:

?- predsort(\X^Y^Z^(Y=(A,B),Z=(C,D), (B < D -> X = > ; X = <)), [(tim,3),(tom,4),(jane,2),(mary,3)], L).
L = [ (tom, 4), (tim, 3), (mary, 3), (jane, 2)].

This 'query' uses library(lambda) to build the required predicate of arity 3.

Answer 3

CapelliC has a very useful answer, and I think there was something wrong with the way I was instantiating. There was something wrong in the numberSort predicate. It should be like this:

numberSort([], [], 0).
numberSort(Unsorted, Sorted, HighestNumber):-
     Counter is HighestNumber - 1,
     extractor(Unsorted, SemiSorted, ExtractedList, Counter),
     numberSort(ExtractedList, Sorting, Counter),
     append(SemiSorted, Sorting, Sorted), !.
numberSort(Unsorted, Sorted, HighestNumber):-
     Counter is HighestNumber - 1,         
     numberSort(Unsorted, Sorted, Counter).

That should work. If anyone notices any problems it in, let me know.