Classify, compare and sort terms

Classifying terms

Frequently it is necessary to identify the type of a particular term. The following are the data classification predicates provided by Arity/Prolog32.

integer(+X)

Succeeds when X is an integer.

float(+X)

Succeeds when X is a floating-point number but not an integer.

number(+X)

Succeeds when X is either an integer or a floating-point number.

atom(+X)

string(+X)

Succeeds when X is an atom (which is also in Arity/Prolog32 a string).

ref(+X)

Succeeds when X is a database reference.

atomic(+X)

Succeeds when X is an atomic data type.

var(+X)

Succeeds when X is an uninstantiated variable.

nonvar(+X)

Succeeds when X is instantiated.

The predicate nonvar/1 is defined as follows:

nonvar(X) :- var(X), !, fail.
nonvar(_).

ground(+X)

Succeeds when X is a ground term. A ground term is any Prolog term that does not contain any variables.

The standard order for term comparison

Often program decisions can must be made by comparing data using criteria such as "greater than" or "less than." When comparing objects you must assume that certain objects are lower and others higher in a predefined order. There is a standard ordering of terms used by Arity/Prolog32 which defines this order.

Standard order, from lowest to highest:

  • Variables, in an arbitrary order.
  • Integers and floating-point numbers from minus infinity to plus infinity.
  • Atoms (strings) in dictionary order, using ASCII character codes.
  • Database references, in a consistent order.
  • Complex terms are ordered first by increasing arity, next by the name of the principal functor, and last recursively by their arguments, left to right.

The comparison predicates

The comparison predicates are as follows; T1 and T2 represent the terms that are the arguments to the predicates. Do not confuse the ‘=’/2 unification predicate with the ‘==’/2 comparison predicate. The unification predicate unifies the terms involved if they can be unified. The comparison predicate simply evaluates whether the terms involved are equivalent and does not affect the terms in any way.

T1 == T2

Succeeds if the terms T1 and T2 are equivalent.

T1 \== T2

Succeeds if the terms T1 and T2 are not equivalent.

T1 @< T2

Succeeds if the term T1 is before (less than) term T2 in the standard order.

T1 @> T2

Succeeds if the term T1 is after (greater than) term T2 in the standard order.

T1 @=< T2

Succeeds if term T1 is less than or equal to term T2 in the standard order.

T1 @>= T2

Succeeds if term T1 is greater than or equal to term T2 in the standard order.

eq(?X, ?Y)

Succeeds if X and Y are the same term, occupying the same storage location.

For example, where the '=='/2 predicate determines that the following are equal, eq/2 does not:

?- article(a) == article(a).
yes

?- eq(article(a), article(a)).
no

?- X = article(a), eq(X,X).
yes

Uninstantiated variables will succeed with eq/2 if they are the same variable. Such strong equality checking is useful when you need to find the boundaries of "infinite" data structures.

compare(-Comp, +T1, +T2)

compare(-Comp, +T1, +T2, +Case)

Compares terms T1 and T2 and either tests or returns a comparison value.

Compare unifies its first argument with the appropriate atom (=, <, or >) to describe the relationship between the terms T1 and T2. Textual comparisons performed by compare/3 are case sensitive using the ASCII character set. For compare/4, if Case is 0 then the comparison is case sensitive, otherwise if Case is 1 then the case of the characters in atoms will be ignored.

The comparison predicates do not evaluate expressions, perform unification, or in any other way change the value of their arguments. They perform a literal comparison of terms. For example, the == predicate would not find the following terms to be equivalent:

?- 2 + 1 == 1 + 2.
no

Common programming errors in Prolog is to use the unification predicate '='/2 in place of the comparison predicate '=='/2, or vice versa. In addition, '='/2 is sometimes confused with the arithmetic evaluation predicate is/2.

Sorting terms

The built-in predicates for sorting use the standard order of terms to sort lists of objects in ascending order using the comparison predicate, '@=<'/2.

The following is a Prolog implementation of quick sort (similar to but not the same as the built-in sort/2 predicate):

quick_sort(List, Sorted) :-
    q_sort_(List, [], Sorted).

quick_sort_([], Acc, Acc) :- !.
quick_sort_([H|T], Acc, Sorted) :-
    pivot_(H, T, L1, L2),
    quick_sort_(L1, Acc, Sorted1),
    quick_sort_(L2, [H|Sorted1], Sorted).

pivot_(H, [], [], []) :- !.
pivot_(H, [X|T], [X|L], G) :-
    X @=< H,
    !,
    pivot_(H, T, L, G).
pivot_(H, [X|T], L, [X|G]) :-
    pivot_(H, T, L, G).

For example, you could sort the following list of objects:

?- quick_sort (['dog', any(0,2), X, 7, X=Y, -9], L).
X = _14
Y = _28
L = [ _14, -9, 7, dog, _14 = _28, any(0,2) ]
yes

Arity/Prolog32 provides two predicates for sorting terms, sort/2 and keysort/2.

sort(+List1, -List2)

Sorts the list List1 according to the standard order, removes duplicates, and unifies the sorted list with List2. For example:

?- sort([p, c, f, c, p, f], L).
L = [c, f, p]
yes

keysort(+List1, -List2)

Sorts a list of terms of the form Key-Value, ordering by the Key terms only, does not merge duplicates, and unifies the list to List2.

For example:

?- keysort([a-3, b-2, a-1, c-dog], L).
L = [a - 3, a - 1, b - 2, c - dog]
yes

List Length

length(+List, -N)

This predicate determines the length of a list. The List argument must be instantiated to a list of determinate length.

The following is an implementation of the length/2 predicate:

length(List, Len) :-
    length_(List, 0, Len).

length_([], Len, Len) :- !.
length_([_|T], N, Len) :-
    inc(N, N1),
    length_(T, N1, Len).

The length/2 predicate does the following:

?- length("morning" ,N).
N = 7
yes

?- length([a,b,c,d],X).
X = 4
yes

?- length([a|T], X).
no