What is a List?

Examples of Lists

          []    empty list:
                no elements
         [X]    list with one element:
                the variable X.
     [1,2,3]    list with three elements:
                the numbers 1,2,3.
[do,[re,mi]]    list with two elements
                the symbol do and 
                the list [re,me]

Components of Lists

A list is either empty, or it is composite, having a head and a tail.


The head of a non-empty list is its first element, eg


The tail of a non-empty list is what remains after removing its head, eg

Accessing Components of Lists

The Bar Notation

To access the components of lists, we employ a special notation which makes the head and the tail explicit.
standard notation    head   tail   bar notation

[a]                  a      []     [a | []]

[a,b]                a      [b]    [a | [b]]

[[a,b],c]           [a,b]   [c]    [[a,b] | [c]]

The term [X | Y] (with X and Y variable) thus denotes a list with head X and tail Y. By unifying such a term against a list, the variables become bound, thus picking out head and tail. In the last case, we attempt to unify a composite list with an empty list. The result is failure.
term          term               unification results

[X | Y]       [a,b,c]            X=a        Y=[b,c]

[X | Y]       [a]                X=a        Y=[]

[X | Y]       [do,[re,me]]       X=do       Y=[[re,me]]

[X | Y]       [[do,re],me]       X=[do,re]  Y=[me]

[[do,X] | Y]  [[do,re],me]       X=re       Y=[me]

[X | Y]       []                     failure

Invoking Unification Explicitly with "="

In Prolog the results of unification can verified by explicit invocation of a goal involving the operator "=".
?- X = a.
?- [X | Y] = [a,b,c].
Normally, unification is invoked automatically whenevar the database is searched for clauses matching a given subgoal. The resulting variable bindings are then available to be used in subsequent subgoals.
Mike Rosner (
Last modified: Wed Apr 9 12:50:54 MET DST