Skip to content
Tutorials Center
My learning

Topics

Lesson 22 of 40 ยท Arithmetic and Control

Comparing and Ordering Terms

Understand the difference between =, ==, =:= and \=, learn the standard order of terms, and sort data with compare/3, sort/2, msort/2, sort/4, predsort/3 and keysort/2.

Prolog has several kinds of "equal", and picking the wrong one is the source of many subtle bugs. = unifies, == asks whether two terms are already identical, =:= compares numeric values, and @< and friends compare terms by a fixed standard order. This lesson sorts them out and then uses the standard order to sort lists.

Unify, identical, and numerically equal

Goal True when Binds variables?
A = B the terms can be made equal by binding variables yes
A \= B they can not be unified no
A == B they are already identical, same variables included no
A \== B they are not identical no
A =:= B both evaluate to the same number no
A =\= B both evaluate to different numbers no
PROLOG
?- a = a.            % true
?- X = Y.            % true, X and Y become the same variable
?- X == Y.           % false, two different variables
?- f(X) = f(a).      % true, X = a
?- f(X) == f(a).     % false, X is not a
?- 1 =:= 1.0.        % true, same number
?- 1 == 1.0.         % false, an integer and a float are different terms
?- 2 + 3 =:= 5.     % true
?- 2 + 3 == 5.      % false

A useful mental model: == never changes anything, it only looks. = may change things. \= is "unification would fail", and is best used when its arguments are already bound; with unbound variables it nearly always fails, because a variable can unify with anything.

The next demo models the difference in Python. Prolog is not available on this site, so the code is a stand-in with variables as objects.

Python Identical or unifiable? (Python model)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

(Python treats 1 and 1.0 as equal, so the last row differs from Prolog, where 1 = 1.0 fails. That is exactly the kind of detail to remember: Prolog distinguishes integers from floats when comparing terms.)

The standard order of terms

Any two terms can be compared, even a number with a compound. The standard order is:

flowchart LR
  V["Variables"] --> N["Numbers"] --> A["Atoms"] --> S["Strings"] --> C["Compound terms"]

Variables come first, then numbers, atoms, strings and compound terms.

Within each class:

  • Numbers compare by value. If an integer and a float have the same value, the float comes first.
  • Atoms compare alphabetically (by character code).
  • Compound terms compare by arity (number of arguments), then by functor name, then by arguments from left to right.
  • Variables compare by age, which is not something you should depend on.

The comparison operators are @<, @>, @=<, @>=, plus compare/3, which gives <, = or >:

PROLOG
?- a @< b.
true.

?- g @< f(a).            % any atom comes before any compound
true.

?- compare(Order, 3, a).
Order = (<).

?- compare(Order, 1, 1.0).
Order = (>).

Sorting with the standard order

SWI-Prolog's sorting predicates all use the standard order:

PROLOG
?- sort([c, a, b, a], L).        % removes duplicates
L = [a, b, c].

?- msort([c, a, b, a], L).       % keeps duplicates
L = [a, a, b, c].

?- msort([b, 3, f(a), 2.0, 2, a], L).
L = [2.0, 2, 3, a, b, f(a)].

?- sort(0, @>=, [1, 3, 2, 3], L).   % descending, keep duplicates
L = [3, 3, 2, 1].

sort/4 is the powerful one. sort(Key, Order, List, Sorted) sorts on the Key-th argument of each element (0 means the whole term). Order is @< (ascending, drop duplicates), @=< (ascending, keep), @> or @>= (descending).

PROLOG
?- sort(2, @>=, [p(a, 3), p(b, 9), p(c, 5)], L).
L = [p(b, 9), p(c, 5), p(a, 3)].

keysort/2 sorts Key-Value pairs by key only, and it is stable: pairs with equal keys keep their original order. That makes it the classic tool for grouping:

PROLOG
?- keysort([b-1, a-2, b-0, a-1], L).
L = [a-2, a-1, b-1, b-0].

When you need a custom order, predsort(Pred, List, Sorted) calls your predicate with three arguments, Pred(Order, A, B), and expects <, > or =. It removes elements for which = is returned, so make your comparison break ties:

PROLOG
by_length(Order, A, B) :-
    length(A, LA), length(B, LB),
    compare(Order0, LA, LB),
    (   Order0 == (=) -> compare(Order, A, B)
    ;   Order = Order0
    ).
PROLOG
?- predsort(by_length, [[a,b], [c], [d,e,f], [a]], L).
L = [[a], [c], [a, b], [d, e, f]].

The helper first compares lengths and falls back to the standard order for ties, so no list is dropped by accident. Notice the use of ->; it is explained in Negation and If-Then-Else.

The stand-in below implements the standard order in Python so you can see why mixed lists sort the way they do.

Python Standard order of terms (Python model)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Practical advice

  • Use == and \== to test a term without binding it, for example when checking that a variable is still unbound: var(X) is clearer for that.
  • Compare numbers with =:= and <, not with ==, unless you want integer and float to differ.
  • Use msort/2 when duplicates matter (counting), sort/2 when you want a set-like result.
  • Remember sort/2 sorts by the standard order of whole terms, so [10, 9] sorts as numbers, but ['10', '9'] as atoms comes out as ['10', '9'] (character by character).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is the result of ?- f(X) == f(a).?

    == tests identity without binding. X is a different term from a, so the answer is false. f(X) = f(a) would succeed and bind X.
  2. 2. Which one removes duplicates while sorting?

    sort/2 drops duplicates; msort/2 keeps them; keysort/2 sorts pairs by key and is stable.
  3. 3. In the standard order, which comes first?

    Order is variables, numbers, atoms, strings, compound terms. So 99 comes before zebra, which comes before f(a).
  4. 4. What does compare(O, 2, 2.0) return?

    When an integer and a float have the same value, the float comes first in the standard order, so 2 is greater than 2.0.

Summary

  • = unifies, == tests identity, =:= compares numeric values; \= and \== are their negations.
  • The standard order is variables, numbers, atoms, strings, compound terms; compounds compare by arity, name, then arguments.
  • compare/3, @< and friends use that order; sort/2, msort/2, sort/4, keysort/2 and predsort/3 sort with it.
  • keysort/2 is stable; predsort/3 drops elements where your predicate returns =.

Next: The Cut