Working with lists in Prolog
Please work in SWISH or locally, using swipl
command.
1. List notation
A list is an ordered collection of items.
An element can be any Prolog structure (term).
We denote the list:
[a,b,c]
[2,4,6, ala, has, a, cat]
[]
Each list consists of:
head , which is always the 1st list element, and
tail , which is always a list
The head and tail are separated by the operator |
(vertical bar), e.g .:
? - [X | Y] = [a, b, c, d].
X = a
Y = [b, c, d];
The decomposition and structuring of lists is mainly carried out by the unification mechanism.
For example:
? - [X, Y | Z] = [a, b, c, d].
X = a
Y = b
Z = [c, d];
? - [X, Y, a] = [Z, b, Z].
X = a
Y = b
Z = a;
Exercise
Please check the following unification:
? - X = [a, b, c].
? - [X | Y] = [a, b, c].
? - [[a, b], c] = [X, Y].
? - [a(b), c(X)] = [Z, c(a)].
? - [X | Y] = [a].
Selecting an Item:
third([A, B, C | Rest], C).
Define a predicate that compares 2 selected list items, e.g. 3 and 4.
Example of use:
? - compare([a, b, c, d]).
false
? - compare([a, b, c, c]).
true
Define a predicate that replaces 2 selected list items, e.g. 3 and 4.
? - replace ([a, b, c, d], X).
X = [a, b, d, c]
true
2. List membership
belongs(X, [X | _]).
belongs(X, [_ | Ytail]) :- belongs(X, Ytail).
Exercise
Add the predicate belongs
to your program.
Check and think about the operation of the following:
? - belongs(c, [a, b, c, d]).
? - belongs(x, [a, b, c, d]).
? - belongs(X, [a, b, c, d]).
? - belongs(x, a).
? - belongs(X, a).
3. Counting items
list_length([], 0).
list_length([_ | Tail], Length):-
list_length(Tail, X),
Length is X + 1.
Exercise
Add the predicate list_length
to the file.
Check and think about the operation of the following:
? - list_length ([a, b, c], X).
4. Recursive list analysis
(source: LearnPrologNow))
a2b([], []).
a2b([a | Ta], [b | Tb]): -
a2b(Ta, Tb).
Exercise
Add the predicate a2b
to the file.
Check and think about the operation of the following:
? - a2b([a, a, a], [b, b, b]).
? - a2b([a, a, a, a], [b, b, b]).
? - a2b([a, s, d], [b, s, d]).
? - a2b([a, a, a, a], X).
? - a2b(X, [b, b]).
? - a2b(X, Y).
Note: this predicate does “something interesting” only for lists starting with 'a' and 'b'!
5. Merging lists
list_merge([], X, X).
list_merge([X | L1], L2, [X | L3]): -
list_merge(L1, L2, L3).
Exercise
Add the predicate list_merge
to the file.
Check and think about the operation of the following:
? - list_merge([a, b], [c, d], X).
? - list_merge([a, b], X, [c, d]).
? - list_merge([a, b], X, [a, b, c, d]).
? - list_merge(A, B, [a, b, c, d, e]).
? - list_merge([1,2,3], [a, b, c], X).
? - list_merge([1,2,3], [a (e), b (f), c (d, g)], X).
? - list_merge(Before, [5 | After], [1,2,3,4,5,6,7,8,9]).
? - list_merge(_, [A, 5, B, _], [1,2,3,4,5,6,7,8,9]).
? - list_merge(A, [x, x, x | _], [a, b, x, x, c, x, x, x, d, e]).
Note: add and test the predicate:
belongs(X, L) :- list_merge(_, [X | _], L).
Define a predicate that checks if the Item is the last element of the List:
last(Item, List).
With and without the use of “list_merge”.
6. Adding items
list_add(X, L, [X | L]).
In practice, an additional predicate would not be needed here.
Exercise
Add the predicate list_add
to the file.
Check and think about the operation of the following:
? - list_add(a, [c, d], X).
? - list_add([a, b], [c, d], X).
7. Deleting items
list_remove(X, [X | Remainder], Remainder).
list_remove(X, [Y | Tail], [Y | Rest]) :-
list_remove(X, Tail, Rest).
Exercise
Add the predicate list_remove
to the file.
Check and think about the operation of the following:
? - list_remove(a, [a, b, a, c, a, a], X).
? - list_remove(a, [a, b, c, d], X).
? - list_remove(c, [a, b, c, d], X).
? - list_remove(c, X, [a, b, c, d]).
? - list_remove(1, X, [a, b, c, d]).
Please find all solutions (;).
Note: add and test the predicate:
list_insert(X, L, Large) :- list_remove(X, Large, L).
Note: add and test the predicate:
belongs2 (X, L) :- list_remove(X, L, _).
8. Lists containment
list_contains(S, L) :-
list_merge(_, L2, L),
list_merge(S, _, L2).
Exercise
Add the predicate list_contains
to the file.
Check and think about the operation of the following:
? - list_contains(a, [a, b, c]).
? - list_contains([a], [a, b, c]).
? - list_contains(X, [a, b, c]).
? - list_contains([X], [a, b, c]).
? - list_contains([X, Y], [a, b, c]).
? - list_contains([X, Y, Z], [a, b, c]).
9. List permutations
permutation([],[]).
permutation([X | L], P) :-
permutation(L, L1),
list_insert(X, L1, P).
permutation2([], []).
permutation2(L, [X | P]) :-
list_remove(X, L, L1),
permutation2(L1, P).
Exercise
Add the predicate permutation
to the file.
Check and think about the operation of the following:
? - permutation([a, b, c], X).
? - permutation2([a, b, c], X).
10. Reversing Lists
list_reverse([], []).
list_reverse([H | T], L): -
list_reverse(T, R), list_merge(R, [H], L).
Exercise
Add the predicate list_reverse
to the file.
Check and think about the operation of the following:
? - list_reverse([a, b, c, d], X).
? - list_reverse([a, b, c, d], [d, c, b, a]).
11. Lists and strings
A string in Prolog may be represented by:
an atom - difficult to process,
a list of ASCI codes of characters,
a list of one-letter atoms.
List representation increases the string processing possibilities.
Useful predicate:
write_string([H | T]) :-
put(H), write_string(T).
write_string([]).
Another situation: An example of using the built-in predicates name
and append
to transform strings.
Predicate plural (Noun, Pl)
- converts an English regular noun from singular to plural.
plural(Noun, PL) :-
name(Noun, L),
name(s, T),
append(L, T, NL),
name(PL, NL).
Exercise
Check and think about the operation of the following:
? - write('ala').
? - write('ala has a cat').
? - write("ala").
? - write("ala has a cat").
? - X = 'a', put(X).
? - X = 'ala', put(X).
? - X = "a", put(X).
? - put(65), put(66), put(67).
Add the predicates write_string
and plural
to the file.
Check and think about the operation of the following:
? - write_string("ala has a cat").
? - permutation ("abc", X), write_string(X), nl, fail.
? - list_insert("", "abcdefgh", Z), write_string(Z), nl, fail.
? - plural(day, PL).
If you want to know more...