# Lists

## What is a List?

• A list is a data structure for representing sequences of elements.
• A list is a sequence of zero or more terms.
• A list is itself a term.

### 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
• head of [1,2,3] is 1
• head of [[1,2],3] is [1,2]

### Tail

The tail of a non-empty list is what remains after removing its head, eg
• tail of [1,2,3] is [2,3]
• tail of [[1,2],3] is [3]
• tail of [3] is []

## 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=a
?- [X | Y] = [a,b,c].
X=a
Y=[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 (mros@cs.um.edu.mt)