1©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Lists
• A list is a finite sequence of elements
• Examples of lists in Prolog:
[mia, vincent, jules, yolanda]
[mia, robber(honeybunny), X, 2, mia]
[ ]
[mia, [vincent, jules], [butch, friend(butch)]]
[[ ], dead(z), [2, [b,c]], [ ], Z, [2, [b,c]]]
2©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Important things about lists
• List elements are enclosed in square
brackets
• The length of a list is the number of
elements it has
• All sorts of Prolog terms can be
elements of a list
• There is a special list:
the empty list [ ]
3©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail
• A non-empty list can be thought of as
consisting of two parts
– The head
– The tail
• The head is the first item in the list
• The tail is everything else
– The tail is the list that remains when we
take the first element away
– The tail of a list is always a list
4©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 1
• [mia, vincent, jules, yolanda]
Head:
Tail:
5©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 1
• [mia, vincent, jules, yolanda]
Head: mia
Tail:
6©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 1
• [mia, vincent, jules, yolanda]
Head: mia
Tail: [vincent, jules, yolanda]
7©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 2
• [[ ], dead(z), [2, [b,c]], [ ], Z, [2, [b,c]]]
Head:
Tail:
8©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 2
• [[ ], dead(z), [2, [b,c]], [ ], Z, [2, [b,c]]]
Head: [ ]
Tail:
9©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 2
• [[ ], dead(z), [2, [b,c]], [ ], Z, [2, [b,c]]]
Head: [ ]
Tail: [dead(z), [2, [b,c]], [ ], Z, [2, [b,c]]]
10©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 3
• [dead(z)]
Head:
Tail:
11©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 3
• [dead(z)]
Head: dead(z)
Tail:
12©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and Tail example 3
• [dead(z)]
Head: dead(z)
Tail: [ ]
13©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Head and tail of empty list
• The empty list has neither a head
nor a tail
• For Prolog, [ ] is a special simple list
without any internal structure
• The empty list plays an important role in
recursive predicates for list processing
in Prolog
14©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
The built-in operator |
• Prolog has a special built-in operator |
which can be used to decompose a list
into its head and tail
• The | operator is a key tool for writing
Prolog list manipulation predicates
15©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
The built-in operator |
?- [Head|Tail] = [mia, vincent, jules, yolanda].
Head = mia
Tail = [vincent,jules,yolanda]
yes
?-
16©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
The built-in operator |
?- [X|Y] = [mia, vincent, jules, yolanda].
X = mia
Y = [vincent,jules,yolanda]
yes
?-
17©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
The built-in operator |
?- [X|Y] = [ ].
no
?-
18©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
The built-in operator |
?- [X,Y|Tail] = [[ ], dead(z), [2, [b,c]], [], Z, [2, [b,c]]] .
X = [ ]
Y = dead(z)
Tail = [[2, [b,c]], [ ], Z, [2, [b,c]]]
yes
?-
19©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Anonymous variable
• Suppose we are interested in the
second and fourth element of a list
?- [X1,X2,X3,X4|Tail] = [mia, vincent, marsellus, jody, yolanda].
X1 = mia
X2 = vincent
X3 = marsellus
X4 = jody
Tail = [yolanda]
yes
?-
20©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Anonymous variables
• There is a simpler way of obtaining only
the information we want:
?- [ _,X2, _,X4|_ ] = [mia, vincent, marsellus, jody, yolanda].
X2 = vincent
X4 = jody
yes
?-
• The underscore is an anonymous
variable
21©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
The anonymous variable
• Is used when you need to use a
variable, but you are not interested in
what Prolog instantiates it to
• Each occurrence of the anonymous
variable is independent, i.e. can be
bound to something different
22©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Member
• One of the most basic things we would
like to know is whether something is an
element of a list or not
• So let’s write a predicate that when
given a term X and a list L, tells us
whether or not X belongs to L
• This predicate is usually called
member/2
23©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?-
24©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(yolanda,[yolanda,trudy,vincent,jules]).
25©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(yolanda,[yolanda,trudy,vincent,jules]).
yes
?-
26©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(vincent,[yolanda,trudy,vincent,jules]).
27©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(vincent,[yolanda,trudy,vincent,jules]).
yes
?-
28©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(zed,[yolanda,trudy,vincent,jules]).
29©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(zed,[yolanda,trudy,vincent,jules]).
no
?-
30©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(X,[yolanda,trudy,vincent,jules]).
31©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
member/2
member(X,[X|T]).
member(X,[H|T]):- member(X,T).
?- member(X,[yolanda,trudy,vincent,jules]).
X = yolanda;
X = trudy;
X = vincent;
X = jules;
no
32©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Rewriting member/2
member(X,[X|_]).
member(X,[_|T]):- member(X,T).
33©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Recursing down lists
• The member/2 predicate works by
recursively working its way down a list
– doing something to the head, and then
– recursively doing the same thing to the tail
• This technique is very common in
Prolog and therefore very important that
you master it
• So let`s look at another example!
34©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Example: a2b/2
• The predicate a2b/2 takes two lists as
arguments and succeeds
– if the first argument is a list of as, and
– the second argument is a list of bs of
exactly the same length
?- a2b([a,a,a,a],[b,b,b,b]).
yes
?- a2b([a,a,a,a],[b,b,b]).
no
?- a2b([a,c,a,a],[b,b,b,t]).
no
35©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Defining a2b/2: step 1
• Often the best away to solve such
problems is to think about the simplest
possible case
• Here it means: the empty list
a2b([],[]).
36©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Defining a2b/2: step 2
• Now think recursively!
• When should a2b/2 decide that two
non-empty lists are a list of as and a list
of bs of exactly the same length?
a2b([],[]).
a2b([a|L1],[b|L2]):- a2b(L1,L2).
37©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Testing a2b/2
a2b([],[]).
a2b([a|L1],[b|L2]):- a2b(L1,L2).
?- a2b([a,a,a],[b,b,b]).
yes
?-
38©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Testing a2b/2
a2b([],[]).
a2b([a|L1],[b|L2]):- a2b(L1,L2).
?- a2b([a,a,a,a],[b,b,b]).
no
?-
39©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Testing a2b/2
a2b([],[]).
a2b([a|L1],[b|L2]):- a2b(L1,L2).
?- a2b([a,t,a,a],[b,b,b,c]).
no
?-
40©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Further investigating a2b/2
a2b([],[]).
a2b([a|L1],[b|L2]):- a2b(L1,L2).
?- a2b([a,a,a,a,a], X).
X = [b,b,b,b,b]
yes
?-
41©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Further investigating a2b/2
a2b([],[]).
a2b([a|L1],[b|L2]):- a2b(L1,L2).
?- a2b(X,[b,b,b,b,b,b,b]).
X = [a,a,a,a,a,a,a]
yes
?-
42©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Append
• We will define an important predicate
append/3 whose arguments are all lists
• Declaratively, append(L1,L2,L3) is true
if list L3 is the result of concatenating
the lists L1 and L2 together
?- append([a,b,c,d],[3,4,5],[a,b,c,d,3,4,5]).
yes
?- append([a,b,c],[3,4,5],[a,b,c,d,3,4,5]).
no
43©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Append viewed procedurally
• From a procedural perspective, the
most obvious use of append/3 is to
concatenate two lists together
• We can do this simply by using a
variable as third argument
?- append([a,b,c,d],[1,2,3,4,5], X).
X=[a,b,c,d,1,2,3,4,5]
yes
?-
44©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Definition of append/3
• Recursive definition
– Base clause: appending the empty list to any list
produces that same list
– The recursive step says that when concatenating
a non-empty list [H|T] with a list L, the result is a
list with head H and the result of concatenating
T and L
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
45©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
How append/3 works
• Two ways to find out:
– Use trace/0 on some examples
– Draw a search tree!
Let us consider a simple example
?- append([a,b,c],[1,2,3], R).
46©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R). append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
47©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
48©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
49©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
/ \
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
50©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
/ \
† L0=[b|L1]
?- append([c],[1,2,3],L1)
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
51©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
/ \
† L0=[b|L1]
?- append([c],[1,2,3],L1)
/ \
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
52©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
/ \
† L0=[b|L1]
?- append([c],[1,2,3],L1)
/ \
† L1=[c|L2]
?- append([],[1,2,3],L2)
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
53©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
/ \
† L0=[b|L1]
?- append([c],[1,2,3],L1)
/ \
† L1=[c|L2]
?- append([],[1,2,3],L2)
/ \
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
54©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
/ \
† L0=[b|L1]
?- append([c],[1,2,3],L1)
/ \
† L1=[c|L2]
?- append([],[1,2,3],L2)
/ \
L2=[1,2,3] †
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
55©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Search tree example
?- append([a,b,c],[1,2,3], R).
/ \
† R = [a|L0]
?- append([b,c],[1,2,3],L0)
/ \
† L0=[b|L1]
?- append([c],[1,2,3],L1)
/ \
† L1=[c|L2]
?- append([],[1,2,3],L2)
/ \
L2=[1,2,3] †
L2=[1,2,3]
L1=[c|L2]=[c,1,2,3]
L0=[b|L1]=[b,c,1,2,3]
R=[a|L0]=[a,b,c,1,2,3]
append([], L, L).
append([H|L1], L2, [H|L3]):-
append(L1, L2, L3).
56©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Using append/3
• Now that we understand how append/3
works, let`s look at some applications
• Splitting up a list:
?- append(X,Y, [a,b,c,d]).
X=[ ] Y=[a,b,c,d];
X=[a] Y=[b,c,d];
X=[a,b] Y=[c,d];
X=[a,b,c] Y=[d];
X=[a,b,c,d] Y=[ ];
no
57©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Prefix and suffix
• We can also use append/3 to define
other useful predicates
• A nice example is finding prefixes and
suffixes of a list
58©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Definition of prefix/2
• A list P is a prefix of some list L when
there is some list such that L is the
result of concatenating P with that list.
• We use the anonymous variable
because we don`t care what that list is.
prefix(P,L):-
append(P,_,L).
59©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Use of prefix/2
prefix(P,L):-
append(P,_,L).
?- prefix(X, [a,b,c,d]).
X=[ ];
X=[a];
X=[a,b];
X=[a,b,c];
X=[a,b,c,d];
no
60©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Definition of suffix/2
• A list S is a suffix of some list L when
there is some list such that L is the
result of concatenating that list with S.
• Once again, we use the anonymous
variable because we don`t care what
that list is.
suffix(S,L):-
append(_,S,L).
61©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Use of suffix/2
suffix(S,L):-
append(_,S,L).
?- suffix(X, [a,b,c,d]).
X=[a,b,c,d];
X=[b,c,d];
X=[c,d];
X=[d];
X=[];
no
62©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Definition of sublist/2
• Now it is very easy to write a predicate
that finds sub-lists of lists
• The sub-lists of a list L are simply the
prefixes of suffixes of L
sublist(Sub,List):-
suffix(Suffix,List),
prefix(Sub,Suffix).
63©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Reversing a List
• We will define a predicate
that changes a list [a,b,c,d,e] into
a list [e,d,c,b,a]
• This would be a useful tool to have, as
Prolog only allows easy access to the
front of the list
64©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Reverse
• Recursive definition
1. If we reverse the empty list, we obtain the empty
list
2. If we reverse the list [H|T], we end up with the
list obtained by reversing T and concatenating it
with [H]
• To see that this definition is correct,
consider the list [a,b,c,d].
– If we reverse the tail of this list we get [d,c,b].
– Concatenating this with [a] yields [d,c,b,a]
65©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Reverse
• This definition is correct, but it does
an awful lot of work
• It spends a lot of time carrying out
appends
• But there is a better way…
reverse([],[]).
reverse([H|T],R):-
reverse(T,RT),
append(RT,[H],R).
66©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Reverse using an accumulator
• A better way is using an accumulator
• The accumulator will be a list, and
when we start reversing it will be empty
• We simply take the head of the list that
we want to reverse and add it to the the
head of the accumulator list
• We continue this until we hit the
empty list
• At this point the accumulator will
contain the reversed list!
67©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Reverse using an accumulator
accReverse([ ],L,L).
accReverse([H|T],Acc,Rev):-
accReverse(T,[H|Acc],Rev).
68©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Adding a wrapper predicate
accReverse([ ],L,L).
accReverse([H|T],Acc,Rev):-
accReverse(T,[H|Acc],Rev).
reverse(L1,L2):-
accReverse(L1,[ ],L2).
69©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Illustration of the accumulator
• List: [a,b,c,d] Accumulator: []
70©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Illustration of the accumulator
• List: [a,b,c,d]
• List: [b,c,d]
Accumulator: []
Accumulator: [a]
71©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Illustration of the accumulator
• List: [a,b,c,d]
• List: [b,c,d]
• List: [c,d]
Accumulator: []
Accumulator: [a]
Accumulator: [b,a]
72©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Illustration of the accumulator
• List: [a,b,c,d]
• List: [b,c,d]
• List: [c,d]
• List: [d]
Accumulator: []
Accumulator: [a]
Accumulator: [b,a]
Accumulator: [c,b,a]
73©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Illustration of the accumulator
• List: [a,b,c,d]
• List: [b,c,d]
• List: [c,d]
• List: [d]
• List: []
Accumulator: []
Accumulator: [a]
Accumulator: [b,a]
Accumulator: [c,b,a]
Accumulator: [d,c,b,a]
74
A few other things …
75©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Comparing Integers
x < y x £ y x = y x ¹ y x ≥³ y x > y
X < Y
X =< Y
X =:= Y
X =\= Y
X >= Y
X > Y
Arithmetic Prolog
76©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Comparison Operators
• Have the obvious meaning
• Force both left and right hand argument
to be evaluated
?- 2 < 4+1.
yes
?- 4+3 > 5+5.
no
77©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Comparison Operators
• The unification operator does not force
evaluation but the numeric equality
comparison operator dose.
?- 4 = 4.
yes
?- 2+2 = 4.
no
?- 2+2 =:= 4.
yes
78
Similar looking symbols
= The unification predicate. Succeeds if it can unify its arguments, fails
otherwise.
\= The negation of the unification predicate. Succeeds if = fails, and vice-versa.
== The identity predicate. Succeeds if its arguments are identical, fails
otherwise.
\== The negation of the identity predicate. Succeeds if == fails, and vice-versa.
=:= The arithmetic equality predicate. Succeeds if its arguments evaluate to the
same integer.
=\= The arithmetic inequality predicate. Succeeds if its arguments evaluate to
different integers.
79©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Negation as Failure
• The cut operator (!) suppresses
backtracking.
• The fail predicate always fails.
• They can be combined to get negation
as failure as follows:
neg(Goal):- Goal, !, fail.
neg(Goal).
80©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Vincent and burgers
enjoys(vincent,X):- burger(X),
neg(bigKahunaBurger(X)).
burger(X):- bigMac(X).
burger(X):- bigKahunaBurger(X).
burger(X):- whopper(X).
bigMac(a).
bigKahunaBurger(b).
bigMac(c).
whopper(d).
81©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Vincent and burgers
enjoys(vincent,X):- burger(X),
neg(bigKahunaBurger(X)).
burger(X):- bigMac(X).
burger(X):- bigKahunaBurger(X).
burger(X):- whopper(X).
bigMac(a).
bigKahunaBurger(b).
bigMac(c).
whopper(d).
?- enjoys(vincent,X).
X=a
X=c
X=d
82©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Another built-in predicate: \+
• Because negation as failure is so often
used, there is no need to define it.
• In standard Prolog the prefix operator \+
means negation as failure
• We can define Vincent`s preferences as
follows:
enjoys(vincent,X):- burger(X),
\+ bigKahunaBurger(X).
?- enjoys(vincent,X).
X=a
X=c
X=d
83©
P
a
tr
ic
k
B
la
ck
b
u
rn
,
Jo
h
a
n
B
o
s
&
K
ri
st
in
a
S
tr
ie
g
n
it
z
Negation as failure and logic
• Negation as failure is not logical
negation
• Changing the order of the goals in the
vincent and burgers program gives a
different behaviour:
enjoys(vincent,X):- \+ bigKahunaBurger(X),
burger(X).
?- enjoys(vincent,X).
no
84
Complete negation example
enjoys(vincent,X):- burger(X),
\+ bigKahunaBurger(X).
burger(X):- bigMac(X).
burger(X):- bigKahunaBurger(X).
burger(X):- whopper(X).
bigMac(a).
bigKahunaBurger(b).
bigMac(c).
whopper(d).
?- enjoys(vincent,X).
X=a;
X=c;
X=d;
no
85
Miscellaneous Examples and Applications
86
Quick sort in Prolog
partition([], Pivot, [], []).
partition([H|T], Pivot, [H|Left], Right) :- H =< Pivot,
partition(T, Pivot, Left, Right).
partition([H|T], Pivot, Left, [H|Right]) :- H > Pivot,
partition(T, Pivot, Left, Right).
quicksort([], []).
quicksort([P|T], Sorted) :- partition(T, P, Left, Right),
quicksort(Left, SortedLeft),
quicksort(Right, SortedRight),
append(SortedLeft, [P|SortedRight], Sorted).
87
person(ann).
person(bob).
personSkill(ann, software).
personSkill(bob, software).
personSkill(bob, floating).
job(lifeguard).
job(developer).
jobSkill(lifeguard, firstaid).
jobSkill(lifeguard, swimming).
hasSkills(P, Skills) :- person(P), findall(S, personSkill(P,S), Skills).
needsSkills(J, Skills) :- job(J), findall(S, jobSkill(J,S), Skills).
fit_for_job(P, J) :- hasSkills(P, SkillsHas),
needsSkills(J, SkillsNeeded),
forall(member(S, SkillsNeeded), member(S, SkillsHas)).
Complex queries and Expert systems
88
Natural language processing
– See:
– Parsing and difference lists
– Eliza chatbot
– IBM Watson:
– Unstructured Information Management
Architecture framework running on Hadoop
“We required a language in which we could conveniently express pattern
matching rules over the parse trees and other annotations (such as named
entity recognition results), and a technology that could execute these rules
very efficiently. We found that Prolog was the ideal choice for the language due
to its simplicity and expressiveness.” — Watson development team