Chapter 3

List Processing in Prolog

Prof. N. G. J. Dias
Senior Professor
Department of Computer Systems Engineering,
Faculty of Computing and Technology,
University of Kelaniya,
Kelaniya
Learning outcomes
At the end of this chapter, students should be able to
• Understand different representations of a list.
• Implement some operations associated with lists.

3 May 2025 NGJD@FCT-UoK 2

3.1 Representation of lists
3.1.1 Introduction to lists
• The list is a simple data structure widely used in non-numeric programming.
• A collection of items in a specific order (sequence) is termed a list.
• In many programming languages members of the list must all have the same
specified type.
However, in Prolog there is no restriction at all on the type of objects which can be
included in a list.
• In the simplest form a list is expressed by placing the items, separated by commas,
inside square brackets ([ ]).
This is called the square bracket notation of a list.

3 May 2025 NGJD@FCT-UoK 3

Examples:
1. [jan, feb, mar, apr, may]
2. [04, ‘May’, 1993]
3. [parent(pam, X), * , [ ], [3,8,4]]
• A list is either empty or non empty.
• In the first case, the list is simply written as a Prolog atom ‘[]’.
• In the second case, a list can be regarded as being made up of two things;
(1) the first item, called the head of the list (denoted by H);
(2) the remaining part of the list, called the tail (denoted by T).
Example: Consider the list of vowels [a, e, i, o, u].
Then ‘a’ is the head of the list and tail is the list [e,i,o,u].

3 May 2025 NGJD@FCT-UoK 4

• In general, the head can be anything (any Prolog object, for example, a constant, a
variable or another list); the tail has to be a list.
• Prolog provides another notational extension, the list constructor, which separates
the head and the tail:
Any non empty list L can be represented in the form, L=[H|T], where the vertical
bar (‘|’) separating the head and the tail of the list called the list constructor.
• Note that,
(1) H is not a sub-list of [H|T]. However it may or may not be a list.
(2) T is a sub-list of [H|T]. Either empty or it has own head and tail.
(3) Since H can be an object of any type it could be another list, but it would still
not be a sub-list of [H|T].

3 May 2025 NGJD@FCT-UoK 5

 • The list constructor notation is in fact more general: we can list any number of
elements followed by ‘|’ and the list of remaining items.
Thus, for example, the alternative ways of writing the list [a, e, i, o, u] are:
[a, e, i, o, u] = [ a | [e, i, o, u] ]
= [ a, e | [i, o, u] ]
= [ a, e, i | [o, u] ]
= [ a, e, i, o | [u] ]
= [ a, e, i, o, u | [] ] .
• In summary, to improve the readability Prolog provides a special simple
notation for lists, thus accepting any list written as:
[ ltem1, Item2, ... ] or [ Head | Tail ] or [ Item1, Item2, ... | Others ].

3 May 2025 NGJD@FCT-UoK 6

3.1.2 Tree structure of a list
• A list is a structured object in Prolog.
• The head and the tail of a non-empty list are then combined into a structure by a
special functor ‘.’:
.( Head, Tail)
This is called the standard notation of a list.
• As we have already seen in chapter 2, all structured objects in Prolog can be
pictured as trees.
Thus a list in the form .( Head, Tail) can be represented as follows:

Head Tail

3 May 2025 NGJD@FCT-UoK 7

• Since Tail is in turn a list, it is either empty or it has its own head and tail.
Therefore, to represent lists of any length no additional principle for structuring
objects is needed.
Examples
1. The list [ann] represents the Prolog term: .( ann, [ ] ).
The corresponding tree structure is given below:
ann []
2. The list [a,e|T] represents the Prolog term: [ a, e | T] = .( a, [ e | T]) = .( a, .( e, T) ).
The corresponding tree structure is given below:

e T
3 May 2025 NGJD@FCT-UoK 8
3. The list [ ann, tennis, tom, skiing ] represents the Prolog term:
[ ann, tennis, tom, skiing ] = .( ann, [ tennis, tom, skiing ] )
= .( ann, .( tennis, [ tom, skiing ] ) )
= .( ann, .( tennis, .( tom, [ skiing ] ) ) )
= .( ann, .( tennis, .( tom, .( skiing, [ ] ) ) ) )
Following figure shows the corresponding tree structure:

ann
tennis
tom
skiing []

3 May 2025 NGJD@FCT-UoK 9

• The third example shows how the general principle for structuring data objects in
Prolog also applies to lists of any length.
• Our example, also shows the straight forward standard notation with dots and
possibly deep nesting of sub terms in the tail can produce rather confusing
expressions.
This is the reason why Prolog provides the neater and friendlier notation for lists,
so they can be written as sequences of items enclosed in square brackets.
• A programmer can use both notations, but the square bracket notation, of course,
normally preferred.
We will be aware, however that this is only a cosmetic improvement and that our
list will be internally represented as binary trees.
When such terms are output they will be automatically converted into there neater
form.
Thus the following conversions with Prolog are possible.
3 May 2025 NGJD@FCT-UoK 10
Example
|?-[a,b,c] = .(a, .(b, .(c, []))).
yes
|?-List1=[a, b, c], List2=.(a, .(b, .(c, []))).
List1=[a, b, c]
List2=[a, b, c]
|?-Hobbies1=.(cricket, .(music, [])),
Hobbies2=[Skiing, food],
L=[ann,Hobbies1, tom, Hobbies2].
Hobbies1=[cricket, music]
Hobbies2=[skiing, food]
L=[ann, [cricket, music], tom, [skiing, food]]
|?-
3 May 2025 NGJD@FCT-UoK 11
3.1.3 Comparison of Lists
• During the execution of a Prolog program a variable could be given a value, a
process known as instantiation.
• This is achieved by the build-in process of unification, which tries to match two
Prolog terms by suitable substitutions for the variable involved.
• For example, if we want to access the 4th element of a list of four or more
elements, either of the conditions
[X1, X2, X3, X4|T] = L or [_, _, _, X4|_] = L
will initiate X4 to the 4th element of L.
Example:
Let L=[a, e, i, o, u]. Then
(i) [a, e|T] matches with T = [i,o,u].
(ii) [2|H] fails to match L as 2 is not identical to a.
(iii) [a|[e|T]] matches L with T=[ i,o,u] as [e|T] has to match [e,i,o,u].
3 May 2025 NGJD@FCT-UoK 12
3.2 Some Operations with Lists
3.2.1 Introduction
• List can be used to represents sets although there is a difference: The order of
elements in a set does not matter while the order of items in a list does; also, the
same object can occur repeatedly in a list.
• Still, the most common operations on List are similar to those on sets.
• Common operations include:
(i) Checking whether some object is an element of a list, which corresponds to
the checking for the set membership;
(ii) Concatenation of two lists, obtaining a third list, which corresponds to the
union of sets.
(iii) Adding a new object to a list, or deleting some object from it.

3 May 2025 NGJD@FCT-UoK 13

3.2.2 Membership of a List
• Let X be an object and L be a list, then we can define the membership relation
member(X,L) as follows:
member(X,L) is true if X is a member of the list L.
• The program for the membership relation can be based on the following
observation:
X is a member of L if either (1) X is the head of List L or
(2) X is a member of the tail of list L.
This can be written in two clauses, the first is a simple fact and the second is a rule:
member(X, [X | Tail]). % Clause1
member(X, [Head | Tail]) :- member(X, Tail). % Clause2
• Note that the above set of clauses can be written using anonymous variables as,
member(X,[X|_]).
member(X,[_|T]):-member(X,T).
3 May 2025 NGJD@FCT-UoK 14
Examples
1. |?_member(b,[a,b,c]).
yes.
2. |?_member(b,[a,[b,c]]).
no.
3. |?_member([b,c],[a,[b,c]]).
yes.
4. We can generate through backtracking all the members of a given list:
|?_member(X, [a,b,c]).
X = a;
X = b;
X = c;
no
3 May 2025 NGJD@FCT-UoK 15
 5. |?_member(volvo,[toyota,nissan,volvo,vw]).
yes.
The way Prolog evaluates the query, which is regarded as a goal to be satisfied,
can be illustrated as follows :
Attempting to match goal with clause1 Fail.
Attempting to match goal with head of clause2 Succeeds with unification,
member(volvo,[toyota|[nissan,volvo,vw]]) :-
member(volvo,[nissan,volvo,vw]).
giving new goal
member(volvo,[nissan,volvo,vw]).

3 May 2025 NGJD@FCT-UoK 16

 Attempting to match new goal with clause1 Fail.
Attempting to match new goal with head of clause2 Succeeds with unification,
member(volvo,[nissan|[volvo,vw]]) :- member(volvo,[volvo,vw]).
giving new goal
member(volvo,[volvo,vw]).
Attempting to match new goal with clause1 Succeeds with unification,
member(volvo,[volvo|[vw]]).
Thus the original goal succeeds and Prolog will respond by displaying ‘yes’.

3 May 2025 NGJD@FCT-UoK 17

3.2.3 Concatenation of two Lists
• Let L1 and L2 be two lists and L3 be there concatenation.
Then we can define the relation, conc(L1,L2,L3) by
conc(L1,L2,L3) is true if L3 is the concatenation of L1 and L2.
• In the definition of conc we will have again two cases depending on the first
argument L1:
(i) If the first argument is the empty list, then the second and third arguments
must be the same (call it L); this is expressed by the following Prolog fact:
conc([ ],L,L).
(ii) If the first argument of conc is a non-empty list then it has a head and a tail and
must look like this L1=[X|T]

3 May 2025 NGJD@FCT-UoK 18

 Now consider the following figure:
[X|T]

X T L2

X N

[X|N]

The above figure illustrates the concatenation of [X|T] and some List L2.
The result of the concatenation is the list [X|N], where N is the concatenation of T
and L2.
In Prolog this is written as
conc([X|T], L2, [X|N]):-conc(T, L2, N).

3 May 2025 NGJD@FCT-UoK 19

 Hence the complete program for concatenation of list as follows:
conc([ ], L, L).
conc([X|T], L, [X|N]) :- conc(T, L, N).

Examples:
1. |?_conc([a,b], [c,d],[a,b,c,d]).
yes
2. |?_conc ([a,b], [c,d],[a,b,a,c,d]).
no
3. |?_conc([a,b,c], [1,2,3], L).
L=[a,b,c,1,2,3]
4. |?_conc([a,[b,c],d],[a,[ ],b],L).
L=[a,[b,c],d,a,[ ],b]
3.2025
3 May NGJD@FCT-UoK 20
 5. |?_conc([a,b],[c,d],L).
L=[a,b,c,d]
• Although the conc program looks rather simple it can be used flexibly in many
other ways.

3 May 2025 NGJD@FCT-UoK 21

 (1) We can use conc in the inverse direction for decomposing a given list into two
lists.
|?_conc(L1,L2,[a,b,c]).
L1=[]
L2=[a,b,c];
L1=[a]
L2=[b,c];
L1=[a,b]
L2=[c];
L1=[a,b,c]
L2=[ ];
no
|?_
It is possible to decompose the list [a,b,c] in four ways all of which were found
by our program through backtracking.

3 May 2025 NGJD@FCT-UoK 22

 (2) We can also use our program to look for a certain pattern in a list.
Examples
(i). Find the months that follows a given month, say May.
|?_conc(Before,[may|After],
[jan,feb,mar,apr,may,jun,jul,aug,sep,oct,nov,dec]).
Before = [jan,feb,mar,apr]
After = [jun,jul,aug,sep,oct,nov,dec]
(ii). Find the immediate predecessor and immediate successor of May.
|?_conc(_,[Month1,may,Month2| _],
[jan,feb,mar,apr,may,jun,jul,aug,sep,oct.nov,dec]).
Month1 = apr
Month2 = jun

3 May 2025 NGJD@FCT-UoK 23

 (3) Further still, we can, for example, delete from some list L1 everything that
follows three successive occurrences of z in L1 together with the three z’s.

|?_L1=[a,b,z,z,c,z,z,z,d,e], conc(L2,[z,z,z | _],L1).

L1=[a,b,z,z,c,z,z,z,d,e]
L2=[a,b,z,z,c]

3 May 2025 NGJD@FCT-UoK 24

• We have already programmed the membership relation using recursion, however,
the membership relation could be elegantly programmed using conc as follows:
member1(X,L) :- conc(L1,[X|L2],L).
L

L1 X L2

[X|L2]

This clause says:

X is a member of list L, if L can be decomposed into two lists, so that second
one has X as its head.
Of course, member1 defines the same relation as member.
Note that above clause can be written using anonymous variable as,
member1(X,L) :- conc(_,[X|_],L).

3 May 2025 NGJD@FCT-UoK 25

Exercises
1. (a) Write a goal, using conc, to delete the last three elements from a list L
producing another list L1. Hint: L is the concatenation of L1 and a three-
element list.
(b) Write a sequence of goals to delete the first three elements and the last three
elements from a list L producing list L2.
2. Define the relation
Iast( Item, List)
so that ltem is the last element of a list List. write two versions:
(a) using the conc relation,
(b) without conc.

3 May 2025 NGJD@FCT-UoK 26

3.2.4 Adding an Item
• To add an item to a list it is easiest to put the new item in front of the list so that it
becomes the new head.
• If X is the new item and the list to which X is added is L, then the resulting list is
simply [X|L].
This can be expressed as the following Prolog fact:
add(X,L,[X|L]).

3 May 2025 NGJD@FCT-UoK 27

3.2.5 Deleting an Item
• To delete one occurrence of an element X from a list L to give the new list L1, we
define a relation, delete(X,L,L1) by,
delete(X,L,L1) is true if L1 is the result of deleting one occurrence of X from
the list L.
• The delete relation can be defined similarly to the membership relation.
• Two cases have to be considered,
(1) If X is the head of L, then the result after the deletion is the tail.
(2) If X is in the tail then it is deleted from the tail.
These cases are define in following program,
delete(X, [X|T], T).
delete(X, [Y|T], [Y|T1]) :- delete(X, T, T1).

3 May 2025 NGJD@FCT-UoK 28

• Like member, delete is also non-deterministic in nature.
If there are several occurrences of X in the list then delete will be able to delete
any one of them by backtracking.
Of course, each alternative execution will only delete one occurrence of X, leaving
the other untouched.
Examples
1. |?_delete(a,[a,b,a,a],L).
L=[b,a,a];
L=[a,b,a];
L=[a,b,a];
no.

3 May 2025 NGJD@FCT-UoK 29

 2. |?_delete(4,[6,4,7,4,5],N).
N=[6,7,4,5];
N=[6,4,7,5];
no
• ‘delete’ will fail if the list does not contain the item to be deleted or empty list.
• ‘delete’ can also be use in the inverse direction, to add an item to a list by inserting
the new item any where in the list.
For example, if we want to insert ‘a’ at any place in the list L = [1,2,3], then we can
do this by asking the question :
What is L such that after deleting ‘a’ from L to obtain [1,2,3]?

3 May 2025 NGJD@FCT-UoK 30

 |?_delete(a,L,[1,2,3]).
L=[a,1,2,3];
L=[1,a,2,3];
L=[1,2,a,3];
L=[1,2,3,a];
no
• In general the operation of inserting X at any place in some list, ‘List’ giving
‘BiggerList’ can be defined by the clause,
insert(X, List, BiggerList) :- delete(X, BiggerList, List).
• In member1 we elegantly implement the membership relation by using conc.
We can also used ‘delete’ for test for membership.
The idea is simple: Some X is a member of ‘List’ if X can be deleted from ‘List’:
member2(X, List) :- delete(X, List, _).
3 May 2025 NGJD@FCT-UoK 31
3.2.6 Sublist
• Let us now consider the relation, sublist(S,L), where S and L are lists, then
sublist(S,L) is true if S occurs within as a sublist of L.
So sublist([c,d,e],[a,b,c,d,e,f]) is true, but sublist([c,e],[a,b,c,d,e,f]) is false.
• The idea is based on the following figure,
L

L1 S L3

L2
Accordingly, the relation can be formulated as:
S is a sub list of L if,
(i) L can be decomposed into two lists L1 and L2 and,
(ii) L2 can be decomposed into two lists S and some list L3.
3 May 2025 NGJD@FCT-UoK 32
• As we have seen before, the conc relation can be used for decomposing lists.
So the above formulation can be expressed in Prolog as

sublist(S, L) :- conc(L1, L2, L),conc(S, L3, L2).

• Although sub lists is designed to check if some list occurs as a sublist within
another list, it can also be used to find all sub lists of a given list.

3 May 2025 NGJD@FCT-UoK 33

Example
|?_sublist(S,[a,b,c]).
S=[ ];
S=[a];
S=[b];
S=[c];
S=[a,b,c];
S=[a,b];
S=[b,c];
no

3 May 2025 NGJD@FCT-UoK 34

3.4.7 Permutations
• Sometimes it is useful to generate permutations of a given list, to this end, we will
define the relation
permutation(L1,L2), where the two arguments L1 and L2 are lists and one is a
permutation of the other.
• The program for permutation can be, again, based on the consideration of two
cases, depending on the first list:
(i) If the first list is empty then the second list must also be empty.
(ii) If the first list is non empty then it has the form, [X|L], and a permutation of
such a list can be constructed as shown in the following figure: First permute L
obtaining P and then insert X at any position into P.

3 May 2025 NGJD@FCT-UoK 35

 X L

Permute L

P P is a permutation of L

Insert X obtaining a permutation of [X|L]

Two Prolog clauses that corresponds to the two cases are

permutation([ ],[ ]).
permutation([X|L], L2) :- permutation(L, P),insert(X, P, L2).

3 May 2025 NGJD@FCT-UoK 36

• One alternate to this program would be to delete an element X from the first list,
permute the rest of it obtaining the list L and then add X in front of P.
The corresponding program is,
permutation2([ ], [ ]).
permutation2(L, [X|P]) :- delete(X, L, L1),permutation2(L1, P).

3 May 2025 NGJD@FCT-UoK 37

• It is instructive to do some experiments with our permutation programs.
1. Its normal use would be something like this:
|?_permutation([red,blue,green],P).
This would result in all six permutations, as intended:
P=[red,blue,green];
P=[red,green,blue];
P=[green,red,blue];
P=[green,blue,red];
P=[blue,red,green];
P=[blue,green,red];
no

3 May 2025 NGJD@FCT-UoK 38

 2. Another attempt to use permutation is
|?_permutation(L,[red,blue,green]).
- Our 1st version, permutation (using insert), will now instantiate L
successfully to all 6 permutations.
If the user then requests more solutions, the program would never answer
“no” because it would get into an infinite loop trying to find another
permutation when there is none.
- Our 2nd version, permutation2 (using delete), will in this case find only the
first identical permutation and then immediately get into an infinite loop.
Thus some care is necessary when using these permutation programs.

3 May 2025 NGJD@FCT-UoK 39

Exercises
1. Define two predicates
evenlength(List) and oddlength(List)
so that they are true if their argument is a list of even or odd length respectively.
For example, the list [a,b,c,d] is 'evenlength‘ and [a,b,c] is 'oddlength'.
2. Define the relation
reverse( List, Reversedlist)
that reverses lists.
For example, reverse([a ,b,c,d],[ d,c,b,a]).
3. Define the predicate palindrome( List). A list is a palindrome if it reads the same in
the forward and in the backward direction. For example, [m,a,d,a,m].

3 May 2025 NGJD@FCT-UoK 40

4. Define the relation
shift( List1, List2)
so that List2 is List1 ‘shifted rotationally’ by one element to the left. For example,
?- shift([1,2,3,4,5], L1), shift(Ll, L2).
produces:
L1 = [2,3,4,5,1]
L2 = [3,4,5,1,2]
5. Define the relation
translate(List1, List2)
to translate a list of numbers between 0 and 9 to a list of the corresponding words.
For example:
translate([3,5 ,1 ,3], [three,five,one,three)
3 May 2025 NGJD@FCT-UoK 41
 Use the following as an auxiliary relation:
means(0, zero), means(1, one), means( 2, two), ...
6. Define the relation
dividelist( List, Listl, List2)
so that the elements of List are partitioned between List1 and List2, and List1 and
List2 are of approximately the same length.
For example, dividelist( [a,b,c,d,e], [a,c,e], [b,d] ).
7. Define the predicate
equal_length(L1, L2)
which is true if lists L1 and L2 have equal number of elements.

3 May 2025 NGJD@FCT-UoK 42

Summary
• The list is a frequently used structure. It is either empty or consists of a head and a
tail which is a list as well.
• Prolog provides special notations for lists: square bracket notation and standard
dotted notation.
• Common operations on lists, programmed in this chapter, are: list membership,
concatenation, adding an item, deleting an item, sublists and permutaions.

3 May 2025 NGJD@FCT-UoK 43