4.1.3.1 Lists

Lists form an important class of data structures in Prolog. They are essentially the same as the lists of Lisp: a list is either the atom [], representing the empty list, or else a compound term with functor . and two arguments, which are the head and tail of the list respectively, where the tail of a list is another list. Thus a list of the first three natural numbers is the structure

                  .
                 / \
                1    .
                    / \
                   2    .
                       / \
                      3   []

which could be written using the standard syntax, as (A) but which is normally written in a special list notation, as (B). Two examples of this list notation, as used when the tail of a list is a variable, are (C), which represent the structure in (D).

     .(1,.(2,.(3,[]))) (A)

     [1,2,3] (B)

     [X|L]     [a,b|L] (C)

                  .               .
                 / \             / \
               X     L         a     .
                                    / \
                                  b     L (D)

Note that the notation [X|L] does not add any new power to the language; it simply improves readability. These examples could be written equally well as (E).

      .(X,L) .(a,.(b,L)) (E)