# Lists

## Contents

## 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**.
### Head

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)
Last modified: Wed Apr 9 12:50:54 MET DST