Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 40 ยท Lists and Recursion

Prolog Accumulators, Reverse and Tail Recursion

Learn the accumulator technique in Prolog: naive reverse versus accumulator reverse, tail recursion and last-call optimization, helper predicates and an intro to difference lists.

Recursive list predicates like len/2 and sum/2 do their work on the way back: they wait for the recursive call to return before adding. That is clear but sometimes wasteful. The accumulator technique carries a partial result down the recursion, so when the list is exhausted the answer is already built. It is the Prolog counterpart of a loop variable, and it turns many slow definitions into fast ones.

Prolog is read-only on this site. The runnable blocks use the Python mini-Prolog stand-in; one of them counts goal calls so you can measure the speedup.

Reversing a list, the slow way

PROLOG
naive_reverse([], []).
naive_reverse([H | T], R) :-
    naive_reverse(T, RT),
    append(RT, [H], R).

To reverse [a, b, c]: reverse the tail [b, c] to get [c, b], then append [a] at the end: [c, b, a]. The definition is correct and obviously right. It is also quadratic: append/3 walks the whole partial result each time, so reversing n elements takes about nยฒ/2 steps. For 10,000 elements that is fifty million steps instead of ten thousand.

The accumulator version

Introduce an extra argument, the accumulator, that collects the answer while we walk the list:

PROLOG
reverse_acc([], Acc, Acc).
reverse_acc([H | T], Acc, R) :-
    reverse_acc(T, [H | Acc], R).

reverse(L, R) :- reverse_acc(L, [], R).

Walk through reverse([a, b, c], R):

Call Accumulator
reverse_acc([a, b, c], [], R) []
reverse_acc([b, c], [a], R) [a]
reverse_acc([c], [b, a], R) [b, a]
reverse_acc([], [c, b, a], R) [c, b, a]

When the input is empty, the accumulator is the answer, so the base case simply says R = Acc. Each element is moved with one step, so this takes n steps: linear. Pushing onto the front of a list with [H | Acc] is constant time; that is the trick.

The pattern has two predicates: a public wrapper (reverse/2) that hides the accumulator and starts it with [], and a private worker (reverse_acc/3) that does the loop. SWI-Prolog's library reverse/2 is defined this way.

PROLOG
?- reverse([a, b, c], R).
R = [c, b, a].

Accumulators for numbers

The same idea applies to arithmetic. A sum that adds on the way back:

PROLOG
sum([], 0).
sum([H | T], S) :- sum(T, S1), S is H + S1.

Accumulator version:

PROLOG
sum_list(L, S) :- sum_acc(L, 0, S).

sum_acc([], S, S).
sum_acc([H | T], Acc, S) :-
    Acc1 is Acc + H,
    sum_acc(T, Acc1, S).

The partial total is carried in Acc. The recursive call is the last goal of its clause. Likewise for length, counting, minimum and maximum:

PROLOG
length_acc(L, N) :- len(L, 0, N).
len([], N, N).
len([_ | T], N0, N) :- N1 is N0 + 1, len(T, N1, N).

max_acc([H | T], Max) :- max_acc(T, H, Max).
max_acc([], M, M).
max_acc([H | T], M0, M) :- M1 is max(H, M0), max_acc(T, M1, M).

Tail recursion and last-call optimization

A call is a tail call when it is the very last thing a clause does. If the clause is also deterministic (no choice points left), Prolog can reuse the current stack frame for the recursive call instead of piling up a new one. This is last-call optimization (LCO). A tail-recursive predicate runs in constant stack space, so it can loop millions of times without overflowing.

The non-tail sum/2 above must remember "add H afterwards" in every frame, so a list with ten million elements uses ten million frames and may overflow the stack. sum_acc/3 does not. Remember two requirements:

  1. The recursive call is the last goal in the body.
  2. No choice points remain when it is reached. In sum_acc, the first argument pattern ([] versus [H|T]) lets SWI-Prolog's first-argument indexing see that only one clause can match, so there is no choice point. If clauses overlap, add guards or use if-then-else.

Note that recursion that you write as N1 is N - 1, count(N1) inside a clause that left an earlier choice point is not optimized; the choice point keeps the frame alive.

Palindromes and other uses

A list is a palindrome if it equals its reverse:

PROLOG
palindrome(L) :- reverse(L, L).
PROLOG
?- palindrome([r, a, c, e, c, a, r]).
true.

Accumulators also give you the last element, build the list of squares, collect partial results, and carry state through a small interpreter. If you find your recursion needs to know "what happened so far", add an accumulator.

Difference lists (a first glimpse)

Appending at the end of a list is expensive because you must walk to the end. A difference list keeps a pointer to the end as an unbound tail. It is written List-Tail, for example [a, b | T]-T. Appending two difference lists needs just one unification:

PROLOG
append_dl(A-B, B-C, A-C).
PROLOG
?- append_dl([1, 2 | T1]-T1, [3, 4 | T2]-T2, Result-[]).
T1 = [3, 4],
T2 = [],
Result = [1, 2, 3, 4].

Difference lists give constant-time append and are the basis of grammar rules (DCGs), which you will meet in chapter 6. You do not need them for everyday list processing.

Measuring the difference

The stand-in counts goal calls by running with its trace turned on and counting Call: lines. Compare naive and accumulator reverse for several list sizes.

Python Naive vs accumulator reverse (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive column grows roughly with the square of the size (doubling the list about quadruples the count), the accumulator column roughly doubles. That is the difference between O(nยฒ) and O(n).

Try it: accumulators for sum, length and maximum

Python Accumulator predicates (mini-Prolog stand-in)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Forgetting to initialize the accumulator in the wrapper (starting with the wrong value, such as [0] instead of 0).
  • Leaving an overlapping clause so a choice point defeats last-call optimization.
  • Naming the accumulator result and the final result the same: the base case should copy the accumulator into the result (reverse_acc([], Acc, Acc)).
  • Using append(L, [X], R) in a loop, which silently makes your code quadratic.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is naive_reverse quadratic?

    Each step appends one element at the end, which costs time proportional to the current length.
  2. 2. In reverse_acc([H|T], Acc, R) :- reverse_acc(T, [H|Acc], R), what does [H|Acc] do?

    Pushing on the front of a list is a single unification, which is why the accumulator version is linear.
  3. 3. What is needed for last-call optimization?

    When the recursive call is last and the clause is deterministic, the frame can be reused.
  4. 4. What is the wrapper predicate for?

    The user calls reverse/2; the worker reverse_acc/3 carries the extra argument.

Summary

  • An accumulator carries a partial result down the recursion; the base case returns it.
  • Accumulator reverse is linear; naive reverse with append/3 is quadratic.
  • Put the recursive call last and avoid choice points to get last-call optimization.
  • Use a public wrapper and a private worker.
  • Difference lists give constant-time append and underlie grammar rules.

Next: Built-in List Predicates