Skip to content
LumenaryAcademy
Practice 55 min

Recursion and lists

Prolog has no loops, so repetition is recursion; lists are its everyday data structure, and accumulators make list code fast.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

No loops, no problem

Prolog has no for and no while. It does not need them. Repetition in Prolog is recursion: a predicate defined in terms of itself on a smaller problem, with a base case where the problem is trivially small. If you learned recursion in another language as an exotic technique, here it becomes everyday practice, and you will find that the shape of the data tells you the shape of the code.

The data structure you will recurse over most is the list. Lists in Prolog are simple, immutable chains of elements, and the patterns that take them apart are written directly in clause heads. By the end of this lesson you will write the classic list predicates yourself, understand why one innocent-looking version of reverse is a hundred times slower than another, and know the library predicates that professionals use instead of writing loops.

DefinitionsH

Lists and recursion

Definition— List

Either the empty list [], or a cell holding a first element (the head) and the rest of the list (the tail), written [Head|Tail]. The list [a, b, c] is shorthand for [a|[b|[c|[]]]].

The notation is flexible. [a, b | T] matches any list of at least two elements, binding T to what follows. [X] matches exactly one element. [_, _, _] matches any three. Because a list is a chain of cells, adding an element at the front is a single step, [New|Old], and leaves the old list untouched. Reaching the last element, or the hundredth, means walking along the chain, one cell at a time. A Prolog list is a singly linked list, not an array.

A recursive predicate over lists usually has two clauses that mirror the definition:

  • a base case for [], and
  • a recursive case for [H|T], which handles H and calls itself on T.

Because T is shorter than [H|T], every call is on a smaller list, and the recursion must eventually reach []. That is an induction argument, and it is the same one you would use to prove the predicate correct.

Definition— Accumulator

An extra argument that carries a partial result down the recursion. The base case returns the accumulator as the final answer. A predicate whose recursive call is its last goal is tail-recursive, and Prolog runs it in constant stack space, like a loop (last-call optimisation).

A note on text: in SWI-Prolog, "hello" in double quotes is a string object, not a list. To work on characters one by one, convert with atom_chars/2 or string_chars/2, which give a list of one-character atoms such as [h, e, l, l, o]. (Other Prologs, following the ISO standard, read "hello" as a list of character codes by default; the flag double_quotes controls this.)

Worked examplesH

Writing list predicates

Three classics, written by hand

Every Prolog programmer writes these once, to understand them. (The library provides them as length/2, sum_list/2 and append/3; we use different names to avoid clashing with the built-ins. is evaluates arithmetic; lesson 5 covers it.)

prolog
:- initialization(main, main).

% len(List, N): N is the number of elements of List.
len([], 0).
len([_|T], N) :-
    len(T, N0),
    N is N0 + 1.

% total(List, Sum): Sum of a list of numbers, with an accumulator.
total(List, Sum) :-
    total(List, 0, Sum).

total([], Acc, Acc).
total([X|Xs], Acc0, Sum) :-
    Acc is Acc0 + X,
    total(Xs, Acc, Sum).

% app(Xs, Ys, Zs): Zs is Xs followed by Ys.
app([], Ys, Ys).
app([X|Xs], Ys, [X|Zs]) :-
    app(Xs, Ys, Zs).

main :-
    len([kiwi, mango, guava], N),
    format("len: ~w~n", [N]),
    total([12, 30, 8], S),
    format("total: ~w~n", [S]),
    app([a, b], [c, d], L),
    format("app forwards: ~w~n", [L]),
    app(Front, [d], [a, b, c, d]),
    format("app to remove a known ending: ~w~n", [Front]),
    format("app to split [1,2,3] every way:~n"),
    forall(app(X, Y, [1, 2, 3]), format("  ~w + ~w~n", [X, Y])).
text
len: 3
total: 50
app forwards: [a,b,c,d]
app to remove a known ending: [a,b,c]
app to split [1,2,3] every way:
  [] + [1,2,3]
  [1] + [2,3]
  [1,2] + [3]
  [1,2,3] + []

Look at each one:

  • len/2 is plain recursion: the length of [_|T] is one more than the length of T. The addition happens after the recursive call returns, so each call must wait on the stack for the one below it.
  • total/3 carries the running sum in an accumulator. The addition happens before the recursive call, which is the last goal, so this is tail recursion. total/2 is the friendly entry point that starts the accumulator at 0. total/2 and total/3 are different predicates; Prolog identifies a predicate by name and arity, and this pairing is a common idiom.
  • app/3 is the most famous predicate in Prolog. Appending [] to Ys gives Ys; appending [X|Xs] gives a list starting with X whose rest is Xs appended to Ys. Notice that it builds the output in the head, [X|Zs], before the recursive call fills in Zs.

And then the surprise: app/3 runs backwards. Given the result and the second argument, it finds the first. Given only the result, it enumerates every way to split it. One three-line definition is concatenation, prefix removal and splitting, because unification does not care which arguments are known. Many library predicates work like this, and documentation lists their modes.

Accumulators matter: two ways to reverse

The obvious way to reverse a list is "reverse the tail, then append the head at the end". It is correct and it is slow, because append must walk the whole partial result each time. The accumulator version pushes each element onto the front of a growing list, a single step each. SWI-Prolog's statistics(inferences, N) counts the logical inferences (roughly, predicate calls) a goal makes, so we can measure:

prolog
:- initialization(main, main).

% naive_rev(Xs, Ys): reverse by appending each head at the end.
naive_rev([], []).
naive_rev([X|Xs], Ys) :-
    naive_rev(Xs, Rs),
    append(Rs, [X], Ys).

% acc_rev(Xs, Ys): reverse with an accumulator.
acc_rev(Xs, Ys) :-
    acc_rev(Xs, [], Ys).

acc_rev([], Acc, Acc).
acc_rev([X|Xs], Acc, Ys) :-
    acc_rev(Xs, [X|Acc], Ys).

% inferences(Goal, N): N is the number of logical inferences Goal used.
inferences(Goal, N) :-
    statistics(inferences, I0),
    call(Goal),
    statistics(inferences, I1),
    N is I1 - I0.

main :-
    naive_rev([a, b, c], R1),
    acc_rev([a, b, c], R2),
    format("~w ~w~n", [R1, R2]),
    forall(member(Len, [100, 200, 400]),
           (   numlist(1, Len, L),
               inferences(naive_rev(L, _), Naive),
               inferences(acc_rev(L, _), Acc),
               format("length ~w: naive ~w inferences, accumulator ~w~n",
                      [Len, Naive, Acc])
           )).
text
[c,b,a] [c,b,a]
length 100: naive 5152 inferences, accumulator 103
length 200: naive 20302 inferences, accumulator 203
length 400: naive 80602 inferences, accumulator 403

Doubling the length of the list roughly quadruples the naive version's work: it is quadratic, O(n2)O(n^2), because the kk-th append walks kk elements and 1+2+⋯+n=n(n+1)/21 + 2 + \dots + n = n(n+1)/2. The accumulator version does one inference per element plus a constant: linear, O(n)O(n). On a list of 100,000 elements, that is the difference between a fraction of a second and minutes. Counting inferences is a good habit: it is deterministic, unlike timing, and it tells you the growth rate directly.

Pattern matching on two elements at a time

Run-length encoding replaces repeated characters by a character and a count. The interesting part is run/5, which looks at the next element and compares it with the current character:

prolog
:- initialization(main, main).

% encode(Chars, Runs): Runs is the run-length encoding of Chars,
% as a list of Char-Count pairs.
encode([], []).
encode([C|Cs], [C-N|Runs]) :-
    run(C, Cs, 1, N, Rest),
    encode(Rest, Runs).

% run(C, Cs, N0, N, Rest): count further copies of C at the front of Cs;
% N0 is the count so far, Rest is what follows the run.
run(_, [], N, N, []).
run(C, [C|Cs], N0, N, Rest) :-
    N1 is N0 + 1,
    run(C, Cs, N1, N, Rest).
run(C, [D|Ds], N, N, [D|Ds]) :-
    D \== C.

% decode(Runs, Chars): expand Char-Count pairs back into characters.
decode([], []).
decode([C-N|Runs], Chars) :-
    length(Copies, N),
    maplist(=(C), Copies),
    decode(Runs, More),
    append(Copies, More, Chars).

main :-
    atom_chars(aaabccdddd, Chars),
    encode(Chars, Runs),
    format("encoded: ~w~n", [Runs]),
    decode(Runs, Back),
    atom_chars(Atom, Back),
    format("decoded: ~w~n", [Atom]),
    atom_chars(mississippi, M),
    encode(M, MRuns),
    format("mississippi: ~w~n", [MRuns]).
text
encoded: [a-3,b-1,c-2,d-4]
decoded: aaabccdddd
mississippi: [m-1,i-1,s-2,i-1,s-2,i-1,p-2,i-1]

run/5 has three clauses, one per situation: the list is empty, the next character is the same ([C|Cs], with the same variable C in the head, so this clause matches only a repeat), or it is different (D \== C). Exactly one applies in each case, so the predicate is deterministic: it leaves no useless choice points behind. Writing clauses that are mutually exclusive, so that Prolog never has to backtrack into a wrong alternative, is how you write list code that is both correct and efficient. decode/2 shows length/2 used to build a list of a given length, which maplist(=(C), Copies) then fills with copies of C.

ExplanationH

A recipe for recursive predicates

Experienced Prolog programmers write list predicates almost mechanically, following the same few questions. Here they are, applied to take(N, List, Prefix): the first N elements of a list, or the whole list if it is shorter.

  1. State the relation in words, with every argument named. "Prefix is the first N elements of List (all of List if it is shorter)." Write that as the comment above the predicate before writing any code.
  2. List the cases from the shape of the data. Here two things can run out: the count (N is 0) or the list ([]). Otherwise both continue (N > 0 and [X|Xs]).
  3. Write the simple cases first. Taking 0 elements gives []; taking from [] gives [].
  4. Write the recursive case assuming the predicate already works on smaller inputs. If Ys is the first N - 1 elements of Xs, then [X|Ys] is the first N of [X|Xs]. Do not trace the recursion in your head; trust the smaller case, exactly as in a proof by induction.
  5. Make the cases exclusive, so no answer is produced twice and no useless choice point is left. The guards N > 0 do that here.
prolog
% take(N, List, Prefix): Prefix is the first N elements of List
% (all of List if it is shorter).
take(0, _, []).
take(N, [], []) :-
    N > 0.
take(N, [X|Xs], [X|Ys]) :-
    N > 0,
    N1 is N - 1,
    take(N1, Xs, Ys).

With this definition, take(2, [a,b,c], P) gives P = [a,b], take(5, [a,b], Q) gives Q = [a,b], take(0, [a], R) gives R = [], and collecting every answer to the first query with findall gives exactly one, [[a,b]], so the exclusive cases did their job.

  1. Test the modes you care about, including the edge cases: empty lists, zero, one element, and the "wrong" direction if the predicate is meant to work backwards.

Library documentation describes each predicate's modes and determinism with a compact notation, for example nth1(?Index, ?List, ?Elem) or msort(+List, -Sorted) is det. det means "succeeds exactly once", semidet "succeeds at most once", nondet "may succeed several times". Learning to read these annotations, and adding them to the comments of your own predicates, is part of writing Prolog that others can use.

ComputationC

The library: lists without writing recursion

Professional Prolog code writes explicit recursion less often than you might think, because the standard library covers the common patterns. library(lists) and library(apply) are loaded automatically in SWI-Prolog when you first use one of their predicates.

prolog
:- initialization(main, main).

% Daily rainfall in millimetres for one week.
week([3, 0, 12, 7, 0, 21, 5]).

double(X, Y) :- Y is 2 * X.
wet(X) :- X > 4.

main :-
    week(W),
    sum_list(W, Total),
    max_list(W, Max),
    nth1(3, W, Third),
    last(W, Last),
    format("total ~w, max ~w, third ~w, last ~w~n", [Total, Max, Third, Last]),
    maplist(double, W, Doubled),
    format("maplist double: ~w~n", [Doubled]),
    include(wet, W, Wet),
    exclude(wet, W, Dry),
    format("include wet: ~w, exclude wet: ~w~n", [Wet, Dry]),
    maplist([X, Y]>>(Y is X * 10), [1, 2, 3], Tens),
    format("maplist with a lambda: ~w~n", [Tens]),
    foldl([X, A0, A]>>(A is max(X, A0)), W, 0, Biggest),
    format("foldl max: ~w~n", [Biggest]),
    msort(W, Sorted),
    sort(W, SortedUnique),
    sort(0, @>=, W, Descending),
    format("msort ~w~nsort ~w~nsort descending ~w~n",
           [Sorted, SortedUnique, Descending]),
    split_string("the cat and the dog and the bird", " ", "", Parts),
    msort(Parts, SortedWords),
    clumped(SortedWords, Counts),
    format("word counts: ~w~n", [Counts]),
    length(Zeros, 3),
    maplist(=(0), Zeros),
    format("length/2 builds a list to fill: ~w~n", [Zeros]).
text
total 48, max 21, third 12, last 5
maplist double: [6,0,24,14,0,42,10]
include wet: [12,7,21,5], exclude wet: [3,0,0]
maplist with a lambda: [10,20,30]
foldl max: 21
msort [0,0,3,5,7,12,21]
sort [0,3,5,7,12,21]
sort descending [21,12,7,5,3,0,0]
word counts: [and-2,bird-1,cat-1,dog-1,the-3]
length/2 builds a list to fill: [0,0,0]

What each does:

PredicateMeaning
sum_list/2, max_list/2Sum and maximum of a list of numbers
nth1(I, List, E)The I-th element, counting from 1 (nth0 counts from 0); it walks the list
last/2The last element; also a walk
maplist(P, Xs, Ys)Applies P to corresponding elements: P(X1, Y1), P(X2, Y2), ...
include(P, Xs, Ys), exclude/3Keep (or drop) the elements for which P succeeds
foldl(P, Xs, V0, V)Combine the elements into one value, left to right
msort/2Sort, keeping duplicates
sort/2Sort and remove duplicates
sort(Key, Order, List, Sorted)Sort on an argument (0 means the whole term) with order @<, @>, @=< or @>=; @=< and @>= keep duplicates
clumped/2Turn runs of equal elements into Element-Count pairs

[X, Y]>>(Y is X * 10) is a lambda, from the yall library that ships with SWI-Prolog: an anonymous predicate with parameters X and Y. Lambdas save you from writing small helper predicates like double/2, but named helpers are often clearer, and they can be tested on their own. The word count shows a common idiom: split, sort with msort, then clumped to count each run of equal words. (split_string/4 returns strings, which print without quotes.)

Common misconceptionsH

Common misconceptions

Misconception

"Lists are arrays." They are linked chains. Prepending is constant time; append, last, nth1 and length walk the list. If you need fast access by position, SWI-Prolog has other structures: compound terms with arg/3 for fixed-size records, and association lists or dictionaries (library(assoc), SWI-Prolog's dicts) for keys.

Misconception

"Recursion is slow and uses lots of memory." Tail-recursive predicates run in constant stack space, thanks to last-call optimisation; they are Prolog's loops. Non-tail recursion like len/2 uses stack proportional to the list's length, which is usually fine, but on very long lists an accumulator version is safer.

Misconception

"append/3 is how you add an element to a list." To add one element, put it at the front: [X|List]. Appending at the end copies the whole list. If you need the elements in their original order, build the list backwards and reverse once at the end, as walk/4 did in lesson 3.

Misconception

"A predicate has one direction." app/3, length/2, member/2 and many others work in several modes. When you write your own, ask which modes it should support, and test them.

Exercises

Exercises

Try each question before opening the hints. Every answer about program output was checked by running the program with SWI-Prolog 10.1.

1. Recursion and lists

Warm-upComputational

Using the lesson's app/3, what does app(X, [c], [a, b, c]) bind X to?

2. Recursion and lists

CoreComputational

How many solutions does app(X, Y, [p, q, r, s]) have?

3. Recursion and lists

CoreComputational

What is S after foldl([E, A0, A]>>(A is A0 + E*E), [1, 2, 3], 0, S)?

4. Recursion and lists

Warm-upComputational

What does sort([b, a, c, a], L) bind L to? (msort would give [a,a,b,c].)

5. Recursion and lists

Warm-upComputational

What does len([a, [b, c], d], N) give for N?

6. Recursion and lists

CoreComputational

Using the lesson's encode/2 on the characters of bookkeeper, how many Char-Count pairs are in the result?

7. Recursion and lists

StretchHuman

The naive reverse used 20,302 inferences for a 200-element list. About how many would you expect for 800 elements?

Choose one

Further reading and resources