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