What is a "Proper" List?

Several of the predicate descriptions below indicate that a particular predicate only works when a particular argument "is a proper list". A proper list is either the atom [] or else it is of the form [_|L] where L is a proper list. X is a partial list if and only if var(X) or X is [_|L] where L is a partial list. A term is a list if it is either a proper list or a partial list; that is, [_|foo] is not normally considered to be a list because its tail is neither a variable nor [].

Note that the predicate is_list(X) defined in library(lists) really tests whether X is a proper list. The name is retained for compatibility with earlier releases of the library. Similarly, is_set(X) and is_ordset(X) test whether X is a proper list that possesses the additional properties defining sets and ordered sets.

The point of the definition of a proper list is that a recursive procedure working its way down a proper list can be certain of terminating. Let us take the case of last/2 as an example. last(X, L) ought to be true when append(_, [X], L) is true. The obvious way of doing this is

     last(Last, [Last]).
     last(Last, [_|Tail]) :-
             last(Last, Tail).
     

If called with the second argument a proper list, this definition can be sure of terminating (though it will leave an extra choice point behind). However, if you call

     | ?- last(X, L), length(L, 0).
     

where L is a variable, it will backtrack forever, trying ever longer lists. Therefore, users should be sure that only proper lists are used in those argument positions that require them.