What does sort/2 do?

Can some explain what does the predicate sort with an example ? I can’t understand what is in the website
sort/2

It sorts a list. For instance:

?- sort([2,1,3],L).
L = [1, 2, 3].

With many of the Prolog predicates what you think they do is probably what they do, the same with sort/2. However with many Prolog predicates they work not only like you would expect a method to work where you give it the method name, functor, and the arguments and it returns a result, but in both directions in that you can give it what you would consider the result and it gives you one or more arguments that will work to satisfy the result. It can get even more confusing with Prolog predicates as part of the result and part of the arguments can also contain variables.

Having noted all of that and looking like my goal it so make your understanding of Prolog predicates worse and have you flee in horror we will start from the something that is typically understood and progressively add to your knowledge until hopefully everything I noted in the first paragraph makes sense.


Working as a method to sort.

?- sort([3,1,2],Sorted).
Sorted = [1, 2, 3].

Some corner cases:

?- sort([],Sorted).
Sorted = [].

?- sort([3,2,1],Sorted).
Sorted = [1, 2, 3].

Working in reverse where the result is given and the arguments are generated.

?- sort([A,B,C],[1,2,3]).
A = 1,
B = 2,
C = 3.

Another example, but this is not a bug because of the way sort/2 is defined in the ISO standard.

?- sort([A,B,C],[3,2,1]).
A = 3,
B = 2,
C = 1.

Using variables with the result Unsorted and the arguments Sorted.

?- sort([A,B,3],[1,2,C]).
A = 1,
B = 2,
C = 3.

I wouldn’t do this on purpose. You might be surprised what comes out of it.

(Using only two elements for brevity)

?- var(A), var(B), sort([A,B], [1,2]).
A = 1,
B = 2.

?- var(B), var(A), sort([A,B], [1,2]).
B = 1,
A = 2.

Another problem:

?- sort([A,B], Sorted), A = 2, B = 1.
A = 2,
B = 1,
Sorted = [2, 1].

I take it that you expect sort/2 to be nondeterministic when working in that mode. If so, that is what I expected but notice in the example that the result was deterministic, which was not what I expected.

No, I didn’t expect that.

1 Like

OK, now that I read your original comment more carefully, this is the exact spot.

The result is not given and the argument are not generated. The elements in the list in the first argument are sorted by the standard order of terms; the result is unified with the second argument.

So what I showed in my previous examples demonstrate two probably unintuitive behaviors.

In the first example, I am “mentioning” B before A, thus moving B infront of A in the standard order of terms. The list is then “sorted” to [B, A], and then [B, A] is unified with [1, 2], so B = 1, A = 2.

In the second example, the list is sorted, so Sorted = [A, B]; after that, A = 2, B = 1 gives you a “sorted” list that is not actually sorted (it was sorted before the variables were further instantiated).

I hope this makes sense. I had completely forgotten it, but apparently I have struggled with those things myself, back in 2013 (look at the comments below the docs for sort/2).

A predicate sort/2 is defined in the ISO core standard. It is not intended
to work bidirectionally. This is also seen in the mode declaration:

sort(+List, -Sorted)
https://www.swi-prolog.org/pldoc/man?predicate=sort/2

The list is input (+) and the sorted list is output (-). Even variables in
the list do not make it bidrectional.

Because according to ISO core standard variables are sorted
according to some numbering of variables. The same variable

?- sort([A,B,C], L), sort([C,B,A], R).
L = R, R = [A, B, C].
?- compare(X, A, B), compare(Y, B, A).
X =  (<),
Y =  (>).

numbering that is also used in compare/3. In as far the predicates
sort/2, compare/3 belong to the same group of predicates as the predicates

(==)/2, (@<)/2, var/1, etc… namely that treat terms syntactically.

1 Like

sort/2 also removes duplicates (predicates such as setof/3 depend on this). If you don’t want duplicate removal, use msort/2 or keysort/2 (there are also a few other sorting predicates, such as predsort/3 and sort/4).

?- sort([1,2,2,3], X).
X = [1, 2, 3].

?- msort([1,2,2,3], X).
X = [1, 2, 2, 3].

?- keysort([3-z,2-y,1-b,1-a], X).
X = [1-b, 1-a, 2-y, 3-z].
1 Like

(wondering why this not a link. There is https://www.swi-prolog.org/pldoc/doc_for?object=sort/4)

Not standard and copied from ECLiPSe. It can replace sort/2, msort/2 and keysort/2 and a lot more (e.g, sorting dicts on a key). It is these days my favorite sorting tool for most jobs unless especially the standard sort/2 or keysort/2 do the job already precisely as I want it done.

edit Now it does link sort/4. Magic going on?

My best guess is that because the search to find the predicate indicators is using regular expressions it is slow. Also there are two different component themes searching for patterns using regular expressions. So the entire post is scanned twice.

What I would like to do, but it is way down on my to do list is to

  1. Hook in some DCG parsing into the editor which should be faster and smarter than regular expressions.
  2. Make the changes permanent in the field entry in the database for the post. Right now the posts table has two columns related to the post, raw and cooked.
1 Like

Yes…for annoying reasons, the function runs asynchronously and isn’t persisted, so it can take varying amounts of time for the links to show up. Annoying, but I’m not sure how best to address this with a purely client-side plugin.

Have you asked for help and the Discourse forum? I do know that using the tag customer with a user name does seem to get better and faster help. Not that most people aren’t getting good and fast help but it seems some of the more senior staff tend to help me out when I having a brain fart.

1 Like

can you explain this …

Since you sort before you unify the variables with values, it’s sorted the list of variables, which puts them in standard order (which for variables, means sorted by address), after which you unify those variables with a value, but this happens after they’re sorted.

You could use when/2 or freeze/2 to make it “wait” until it’s safe to sort:

?- use_module(library(when)).
true.
?- when(ground([A,B]),
        sort([A, B], Sorted)),
   A = 2, B = 1.
A = 2,
B = 1,
Sorted = [1, 2].
1 Like

ok. thanks.

I find this implementation choice rather odd … since once the variables are bound, then the sort can be incorrect.

I would expect default behavior to be as if a when clause was added – or if the variables aren’t bound to perhaps even raise an exception

My understanding is that the ISO standard specifies the behaviour for sort/2 (and, AFAIK, when/2 isn’t in the standard, so couldn’t be part of it), so we’re somewhat stuck with it.

I can also see it somewhat justifiable that it doesn’t error on variables, since presumably you could want to sort things that might be permissible to have variables/not be fully instantiated, but it definitely is not obvious; one of the predicates that one has to be careful about how instantiated the arguments are when calling.

11 posts were split to a new topic: A pure sort/2