Programming in Prolog – Lists
Programming in Prolog
Lists
Romain Barnoud
Thanks to:
Dr Fariba Sadri
Claudia Schulz
Introduction
Lists are useful to represent sequences or collections of things.
dept(eng, aero).
dept(eng, bio_eng).
dept(eng, computing).
dept(eng, eee).
dept(eng, mech_eng).
dept(nat_sci, chemistry).
dept(nat_sci, maths).
dept(nat_sci, physics).
dept(business, finance).
dept(business, management).
dept(eng,
[aero, bio_eng, computing,
eee, mech_eng]).
dept(nat_sci, [chemistry,
maths, physics]).
dept(business,
[finance, management]).
temp(171113, 0000, 16).
temp(171113, 0300, 14).
temp(171113, 0600, 10).
temp(171113, 0900, 11).
temp(171113, 1200, 16).
temp(171113, 1500, 17).
temp(171113, 1800, 14).
temp(171113, 2100, 12).
temp(171113, [16, 14, 10, 11,
16, 17, 14, 12]).
N.B.
The elements in a list can be any Prolog
term (including a list), e.g.
‘[a, 1, f(X,Y), [4,Z,6], 2.0]’.
De�nition
A list is a data structure that represent a sequence of any number of terms.
A Prolog list is one of the following:
‘[]’ called the empty list.
‘[H|T]’ where H is a term and T is a list (recursive de�nition).
H, the �rst item of the list, is called the head.
T, the remaining of the list, is called the tail.
Abbreviated notation:
[a|[b|[c|[d|[]]]]] ≡ [a,b,c,d]
≡ [a|[b,c,d]]
≡ [a,b|[c,d]]
≡ [a,b,c|[d]]
≡ [a,b,c,d|[]]
Head and Tail � Examples
List Head Tail
[]
undef. undef.
[1, 2, 3]
1 [2, 3]
[a]
a []
[[b]]
[b] []
[[]]
[] []
[[2.0, c], 42,
[], [X,y,f(Z)]]
[2.0, c] [42, [], [X,y,f(Z)]]
Head and Tail � Examples
List Head Tail
[] undef. undef.
[1, 2, 3] 1 [2, 3]
[a] a []
[[b]] [b] []
[[]] [] []
[[2.0, c], 42,
[], [X,y,f(Z)]]
[2.0, c] [42, [], [X,y,f(Z)]]
Lists and Uni�cation
List 1 List 2
Substitution
(if existing)
[] [X]
7
[Y] [A|B]
{A 7→ Y,B 7→ []}
[a,b,c] [Y1,Y2]
7
[a,b,c] [Y1|Y2]
{Y1 7→ a,Y2 7→ [b,c]}
[a,b,c] [Z1,Z2,Z3]
{Z1 7→ a,Z2 7→ b,Z3 7→ c}
[a,b,c] [Z1,Z2|Z3]
{Z1 7→ a,Z2 7→ b,Z3 7→ [c]}
[[1,2],[3,4]] [H|T]
{H 7→ [1,2],T 7→ [[3,4]]}
[[1,2],3] [[X|Y]|Z]
{X 7→ 1,Y 7→ [2],Z 7→ [3]}
Lists and Uni�cation
List 1 List 2
Substitution
(if existing)
[] [X] 7
[Y] [A|B] {A 7→ Y,B 7→ []}
[a,b,c] [Y1,Y2] 7
[a,b,c] [Y1|Y2] {Y1 7→ a,Y2 7→ [b,c]}
[a,b,c] [Z1,Z2,Z3] {Z1 7→ a,Z2 7→ b,Z3 7→ c}
[a,b,c] [Z1,Z2|Z3] {Z1 7→ a,Z2 7→ b,Z3 7→ [c]}
[[1,2],[3,4]] [H|T] {H 7→ [1,2],T 7→ [[3,4]]}
[[1,2],3] [[X|Y]|Z] {X 7→ 1,Y 7→ [2],Z 7→ [3]}
Membership
belongs_to(X,L): X belongs to the list L.
belongs_to/2 � Implementation
Base case: X is the �rst element of L
belongs_to(X, L) :-
L = [X|_].
belongs_to(X, [X|_]).
Recursive case: Search for X in the tail of L
belongs_to(X, L) :-
L = [H|T],
belongs_to(X, T).
belongs_to(X, [H|T]) :-
belongs_to(X,T).
Membership
belongs_to(X,L): X belongs to the list L.
belongs_to/2 � Examples of queries
?- belongs_to(3, [1,2,3,4]).
yes
?- belongs_to(2, [1,3,5]).
no
?- belongs_to(X, [2,4,6]).
X = 2 ;
X = 4 ;
X = 6 ;
no
?- belongs_to(1, L).
L = [1|_A] ;
L = [_A, 1|_B] ;
L = [_A, _B, 1|_C] ;
L = [_A, _B, _C, 1|_D] ;
yes
Concatenation
concat(L1, L2, L3): L3 is the list formed by all elements of L1,
followed by all elements of L2.
concat/3 � Implementation
Base case: the �rst list is empty
concat(L1, L2, L3) :-
L1 = [],
L3 = L2.
concat([], L2, L2).
Recursive case:
concat(L1, L2, L3) :-
L1 = [H1|T1],
concat(T1, L2, T3),
L3 = [H1|T3].
concat([H1|T1], L2, [H1|T3]) :-
concat(T1, L2, T3).
TR!
Concatenation
concat(L1, L2, L3): L3 is the list formed by all elements of L1,
followed by all elements of L2.
concat/3 � Examples of queries
?- concat([5,1,8], [4,2], [5,1,8,4,2]).
yes
?- concat([a,b], [d,e], [a,b,c,d,e]).
no
?- concat([0,2,4], [1,3,5], L).
L = [0,2,4,1,3,5] ;
no
?- concat(L1, [y,z], [y,z,x,y,z]).
L1 = [y,z,x] ;
no
Concatenation
concat(L1, L2, L3): L3 is the list formed by all elements of L1,
followed by all elements of L2.
concat/3 � Examples of queries (cont.)
?- concat([1,2,4], L2, [1,2,3,4,5]).
no
?- concat(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
?- concat(L1, [1|T2], [1,2,4,1,3,9,1,4,16]).
L1 = [], T2 = [2,4,1,3,9,1,4,16] ;
L1 = [1,2,4], T2 = [3,9,1,4,16] ;
L1 = [1,2,4,1,3,9], T2 = [4,16] ;
no
Partitioning
even_odd(All, Even, Odd): Even is the sequence of even elements
in All and Odd is the sequence of odd elements in All.
even_odd/3 � Examples of queries
?- even_odd([1,2,3,4,5,6], [2,4,6], [1,3,5]).
yes
?- even_odd([3,7,1,10,3,5,8], Even, Odd).
Even = [10,8], Odd = [3,7,1,3,5] ;
no
?- even_odd(_, [4,4], [5,3,2]).
no
Partitioning
even_odd(All, Even, Odd): Even is the sequence of even elements
in All and Odd is the sequence of odd elements in All.
even_odd/3 � Examples of queries (cont.)
?- even_odd(L, [8,2], [1,3,5]).
L = [8,2,1,3,5] ;
L = [8,1,2,3,5] ;
L = [8,1,3,2,5] ;
L = [8,1,3,5,2] ;
L = [1,8,2,3,5] ;
L = [1,8,3,2,5] ;
L = [1,8,3,5,2] ;
L = [1,3,8,2,5] ;
L = [1,3,8,5,2] ;
L = [1,3,5,8,2] ;
no
Partitioning
even_odd(All, Even, Odd): Even is the sequence of even elements
in All and Odd is the sequence of odd elements in All.
even_odd/3 � Proposed solution
even_odd([], [], []).
even_odd([N|TAll], [N|TEven], Odd) :-
N mod 2 =:= 0,
even_odd(TAll, TEven, Odd).
even_odd([N|TAll], Even, [N|TOdd]) :-
N mod 2 =:= 1,
even_odd(TAll, Even, TOdd).
Try it at home!
Can you implement the following procedures?
len(L,N): N is the number of elements in list L.
list_double(L1,L2): every element in L2 is the double of its
corresponding element in L1.
list_avg(L,A): A is the average of all elements in L.
access_element(N, L, X): X is the Nth element in L.
remove(X,L,Rest): Rest is the list L from which every element
equal to X has been removed.
a2b(L1,L2): every occurrence of a in L1 occurs as b in L2,
everything else is identical/uni�able.
permutation(L1, L2): L2 is a permutation of L1 (harder!).
Built-in predicates
Prolog has numerous built-in predicates to manipulate lists, some of them
available via the `lists’ library1
To load the library, either use the query
?- use_module(library(lists)).
or add the rule
:- use_module(library(lists)).
to your program.
1documentation available at
https://sicstus.sics.se/sicstus/docs/4.3.0/html/sicstus/lib_002dlists.html
https://sicstus.sics.se/sicstus/docs/4.3.0/html/sicstus/lib_002dlists.html
Built-in predicates
A few useful built-in predicates2
member(?Element, ?List):
true if Element occurs in List.
nonmember(?Element, ?List):
true if Element does not occurs in List.
append(?List1, ?List2, ?List3):
true if List3 is the list consisting of List1 followed by List2.
length(?List, ?Integer):
true if Integer is the length of List.
2 How to read the predicate signature:
+Term: Term is expected to not be a variable (but may contain variables).
-Var: Var is expected to be a variable.
?Arg: no assumptions is made whether Arg is a variable or not.
Built-in predicates
A few useful built-in predicates2
rev(+List, ?Reversed):
true if List and Reversed contain the same elements,
but in reverse order.
sort(+List, -Sorted):
elements from List are sorted in ascending order and duplicates
are removed. The result is uni�ed with Sorted.
perm(+List, -Perm):
true if List and Perm are permutations of each other.
subseq0(+Seq, -SubSeq):
true if SubSeq is a sub-sequence of Seq.
And many others…
2 How to read the predicate signature:
+Term: Term is expected to not be a variable (but may contain variables).
-Var: Var is expected to be a variable.
?Arg: no assumptions is made whether Arg is a variable or not.
What have we learned today?
What are lists in Prolog and how they are represented
How to design predicates to manipulate lists
Which built-in predicates are available to use