Prolog Programming: Lists and Operations
List representation and the classic list/set operations.
Prolog Lists
List Representation
A list in Prolog is a sequence of elements enclosed in square brackets. The empty list is written as []. Internally, a list is represented as a binary tree where the head is the first element and the tail is the rest of the list.
Head and Tail
Every non-empty list can be decomposed into its HEAD (the first element) and its TAIL (the remaining list). The notation [H|T] unifies H with the head and T with the tail. The empty list [] has no head or tail.
1
2
3
4
5
6
7
8
% Examples of list decomposition
?- [H|T] = [a, b, c].
H = a
T = [b, c]
?- [H|T] = [x].
H = x
T = []
Lists can contain any type of term, including other lists (nested lists):
1
2
3
?- [H|T] = [[1, 2], 3, 4].
H = [1, 2]
T = [3, 4]
List Decomposition
The pattern [X|Xs] is the standard way to process lists recursively:
1
2
3
% Print each element of a list
print_all([]).
print_all([H|T]) :- write(H), nl, print_all(T).
Query: print_all([apple, banana, cherry]). prints each fruit on a separate line.
Basic List Operations
Membership
List Membership
list_member(X, L) succeeds if X is an element of list L. The predicate has two clauses: (1) X is the head of the list, or (2) X is a member of the tail.
1
2
list_member(X, [X|_]).
list_member(X, [_|TAIL]) :- list_member(X, TAIL).
Membership Queries
1
2
3
4
5
6
7
8
9
10
?- list_member(b, [a, b, c]).
true
?- list_member(x, [a, b, c]).
false
?- list_member(X, [1, 2, 3]).
X = 1 ;
X = 2 ;
X = 3
The third query demonstrates backtracking: Prolog finds all elements one by one.
Length Calculation
List Length
list_length(L, N) computes the length N of list L. The base case states that the empty list has length 0. The recursive case counts one for the head and adds the length of the tail.
1
2
3
4
list_length([], 0).
list_length([_|TAIL], N) :-
list_length(TAIL, N1),
N is N1 + 1.
Length in Action
1
2
3
4
5
?- list_length([a, b, c], N).
N = 3
?- list_length([], N).
N = 0
Concatenation
List Concatenation
list_concat(L1, L2, L3) succeeds if L3 is the concatenation of L1 followed by L2. The base case concatenates an empty list with L to produce L. The recursive case builds the result element by element.
1
2
3
list_concat([], L, L).
list_concat([X1|L1], L2, [X1|L3]) :-
list_concat(L1, L2, L3).
Concatenation Examples
1
2
3
4
5
?- list_concat([a, b], [c, d], R).
R = [a, b, c, d]
?- list_concat([1, 2], [3], X).
X = [1, 2, 3]
The predicate can also be used to split a list by leaving the third argument unbound.
Deletion
Deletion from a List
list_delete(X, L, R) removes the first occurrence of X from L, producing R. Three cases: (1) deleting X from a singleton list [X] gives [], (2) deleting X from [X|L1] gives L1, (3) deleting X from [Y|L2] preserves Y as the head and recurses on the tail.
1
2
3
4
list_delete(X, [X], []).
list_delete(X, [X|L1], L1).
list_delete(X, [Y|L2], [Y|L1]) :-
list_delete(X, L2, L1).
Deletion Examples
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 0
Only the first occurrence is removed.
Insertion
Insertion into a List
list_insert(X, L, R) inserts X into L at any position, producing R. Insertion is the inverse of deletion: list_delete(X, R, L).
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 1
Insertion Examples
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 2
By backtracking, Prolog finds all possible positions for the insertion.
Set Operations on Lists
Treating lists as sets (ignoring order and duplicates), Prolog can compute union and intersection.
Set Union
Set Union
union(S1, S2, S) computes the set union of S1 and S2. Elements of S1 that already appear in S2 are not added again (using member/2 to check).
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 3
Union Example
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 4
The element a appears only in the first set; b and c are common and not duplicated; d appears only in the second set.
Set Intersection
Set Intersection
intersect(S1, S2, S) computes the set intersection of S1 and S2. An element is included in the result only if it appears in both sets.
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 5
Intersection Example
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 6
Only b and d are common to both sets.
Bubble Sort
Bubble Sort
bubblesort(Input, Sorted) sorts a list using the bubble sort algorithm. It repeatedly swaps adjacent elements that are out of order. Each pass places the largest remaining element at the end. The predicate swap/2 performs one pass, and the sort repeats until no swaps are needed.
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 7
Bubble Sort in Action
prolog ?- [H|T] = [[1, 2], 3, 4]. H = [1, 2] T = [3, 4] 8
The cut (!) in bubblesort/2 prevents backtracking once a swap pass is made, ensuring the recursion proceeds deterministically.