Skip to content
Lesson 4 of 7

Step 1 of 5 · Reading · ~1 min

Learn

Recursion and Lists

Lists in Prolog are written [a, b, c]. The cons pattern [H | T] destructures into head H and tail T:

% A list of three elements
[1, 2, 3]

% Same list, written as cons
[1 | [2, 3]]
[1 | [2 | [3 | []]]]

Classic recursive predicates — note the names, which are deliberately not the library ones:

% length of a list
list_length([], 0).
list_length([_ | T], N) :-
    list_length(T, N1),
    N is N1 + 1.

% sum of a list of numbers
list_sum([], 0).
list_sum([H | T], S) :-
    list_sum(T, S1),
    S is H + S1.

% membership
contains(X, [X | _]).
contains(X, [_ | T]) :- contains(X, T).

Do not reuse a library predicate's name

GNU Prolog ships length/2, append/3, reverse/2, member/2, msort/2, sort/2, nth0/3, nth1/3 and sum_list/2 as built-ins, and it treats a clause that redefines one as a fatal compile error, not a warning:

sum_list([], 0).
% fatal error: redefining built-in predicate sum_list/2
% compilation failed

That is why the examples above are called list_sum and contains rather than sum_list and member. When you write your own version of a list operation, pick a name the library has not already taken — and when you only want the behaviour, call the built-in instead of rewriting it.

List comprehensions do not exist. You build new lists by recursion, or you collect the solutions of a goal with findall/3.

Up nextUnification DeepUnification, I/O, Arithmetic

Discussion

Ask a question, share an insight, or help someone who’s stuck.

Sign in to post a comment or reply.

Loading…