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

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

sort([A,B,C],[3,2,1])

It succeeds.

:roll_eyes: I guess the second argument of sort/2 should not be called Sorted but MaybeSorted.

It is not even undetermined whether the argument is sorted (because possibly not all elements are ground and Prolog has a dearth of truth values to communicate such subtleties). It just isn’t sorted.

Solution: Call sort/2 again at once!

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

Saved!

sort/2 has mode (+,-). This means the semantics of this is defined to be equal to this:

sort([A,B,C], Tmp), Tmp = [3,2,1])

Tmp is indeed sorted. We just finished a discussion on standard order of terms wrt. variables and unification :slight_smile:

Edit note that for (-)-moded arguments the docs always state the semantics iff such an argument is unbound. Thus, sort/2 would be marked as det if determinism would have been documented, while sort([x], []) fails.

Some people claim one should annotate both the moded (+,-) and (+,+), where the latter would be semidet and (yek) also should not claim the second argument is sorted. I think that is mostly confusing as it is generally hard to describe all corner cases as we see here. If we define the behavior of output (-) arguments simply as the same as using a new variable and unification everything is unambiguously defined. As a consequence we must consider non-steadfast code as a bug. Note that steadfastness only applies to output (-) arguments. Input (+) arguments must be fully instantiated according to the type and not satisfying this requirement simply leads to undefined behavior (wrong result, error, failure, non-termination, all except for making the Prolog system crash completely).

1 Like

Tmp is indeed sorted.

Operationally. But objectively it is not. In fact, after a passage through sort/2, there should be (transitive) constraints between A,B,C so that any future instantiations cannot violate the implied promise of having a successful sort/2 on the proof tree. Same as for dif/2.

The problem of having sort([A,B,C],[3,1,2]) succeed inhibits any logical interpretation of sort/2 :scream: “Can [A,B,C] be sorted to [3,1,2]?” Prolog be like: “sure”.

Is it ISO? Has it been defined operationally?