9 - Recursion With An Accumulator

In this example we'll introduce the technique of recursion with an accumulator. We'll also walk through fixing a bug aided by tracing.

% Example 09 - Recursion With An Accumulator

% recursive definition
step([], L2, L2). 
step([H1|T1], Y, L2) :- step(T1, Y, [H1|L2]).

% convenience property around step
reversed(X, Y) :- step(X, Y, []).

The task of reversing a list, for example from [a,b,c] to [c,b,a], appears trivial. In many programming languages, there is either an instruction for doing this, or it is easy enough to work backwards along a list. In prolog, the only built in support for working with lists is the [H|T] construct which allows us to split the head from the rest of a list. Can we use this to reverse a list?

Reversing A List

The following diagram shows how we can grow a list L2 to be the reverse of a list L1 by taking the head of L1 at each step of a repeated process.

The list L2 starts empty and, with each step, grows towards the answer we want. The list L2 is an example of an accumulator.

Let's see how we can do this in prolog. We know how to get the head of a given list. Unifying L1 with [H|T] leaves H as the head of that list, as long as it is not empty. 

How do we add that item H to be the new head of an existing list? We use the construct [H|T] again. If we unify L2 with [H|L] then L2 is L with H added to it as a new head. 

Let's try it. The following uses the [H|T] construct to extend the list [1,4,1,5,9] with a new head 3 to give [3,1,4,1,5,9].

? - L2 = [3 | [1,4,1,5,9]].

L2 = [3, 1, 4, 1, 5, 9]

Recursive Definition

The diagram shows visually how, at each step, the size of the problem is reduced by one. This is a common feature of recursive systems. Step 1 reduces the length of the list L1 by one, and increases the length of the second list L2 by one. Step 2 does the same.

We should recognise the list L2 is not the reverse of the initial L1 until the end of the process. As such, we should avoid calling the property that relates L1 and L2 at each step reverse. Let's call it step.

Let's see if we can write a continuation rule.

• Continuation - the step property between (L1) and (L2) is true if the step property between (L1 without its head H) and (L2 extended with a new head H) is true.

If we keep applying this rule, the list L1 will keep reducing in length by one, and the list L2 will keep growing in length by one. It's clear our termination rule will need to deal with the case when L1 is empty.

• Termination - the step property between (an empty list) and (a list L2) is true.

From step/2 To step/3

Let's try turning this recursive definition into prolog code.

step([],L2). 
step([H1|T1], L2) :- step(T1, [H1|L2]).

Now let's try asking “which X is the reverse of [1,2,3]?”

?- step([1,2,3], X).

true

This didn't give us X=[3,2,1]. Let's find out what happened by tracing the query.

?- trace, step([1,2,3], X).

  Call:step([1, 2, 3],_4852)
  Call:step([2, 3],[1|_494])
  Call:step([3],[2, 1|_494])
  Call:step([],[3, 2, 1|_494])
  Exit:step([],[3, 2, 1|_494])
  Exit:step([3],[2, 1|_494])
  Exit:step([2, 3],[1|_494])
  Exit:step([1, 2, 3],_494)
true

We can see that at each step, the first list is being reduced from its head, and the second list is being extended from the front with the head from the first list. We can also see the second list starts as an anonymous variable. We should have initiated the second list as an empty list [].

Let's try again.

?- trace, step([1,2,3], []).

  Call:step([1, 2, 3],[])
  Call:step([2, 3],[1])
  Call:step([3],[2, 1])
  Call:step([],[3, 2, 1])
  Exit:step([],[3, 2, 1])
  Exit:step([3],[2, 1])
  Exit:step([2, 3],[1])
  Exit:step([1, 2, 3],[])
true

This time the second list correctly starts empty [] and grows to [3,2,1] as expected. 

The next challenge is working out why prolog is merely reporting back true, and not giving us the reversed second list. The main query step([1,2,3],[]) has no variable for prolog to try to find a value for. Prolog is merely being asked whether the property step is true or not. If we think about it, the property will always be true for a given list L1 of finite length, because the continuation rule can be applied a finite number of times and then the termination rule always succeeds. 

For prolog to give us an answer, our query needs to contain an unbound variable. That variable needs to be passed through the continuation rule, and only bound to the fully reversed list in the termination rule. This is a common pattern for recursion with an accumulator.

We see this idea in the following rules for step/3, which now has an arity of 3.

step([],L2,L2). 
step([H1|T1], X, L2) :- step(T1, X,[H1|L2]).

The variable X is passed through the continuation rule unchanged, and is only bound to the second list L2 in the termination rule. The termination rule step([],L2,L2) is the concise form for the longer step([],X,L2):-X=L2.

Let's check this step/3 works as expected.

?-  step([1,2,3], X, []).

X = [3, 2, 1]

reversed/2 Wraps step/3

If we're writing prolog code for others to use, we don't want to give them step/3, which takes one more parameter than really required, and a burdensome requirement to initialise the accumulator with an empty list [].

We can write a more intuitive reversed/2 property which wraps step/3 and hides of the implementation detail of initialising the accumulator as an empty list.

% convenience property around step/3
reversed(X, Y) :- step(X, Y, []).

This is much more intuitive. The property reversed(X,Y) is true if the list Y is the reverse of the list X. Let's try it.

?-  reversed([1, 2, 3],Y).

Y = [3, 2, 1]

Key Points

• The construct [H|T] can be used to extend a list with a new head. For example, L2=[H|L1] leaves L2 as the list L1 extended with a new head H.
• Some problems are solved by growing the solution through the repeated application of a process. The growing solution is called an accumulator.
• A common pattern is to pass a variable from the query, through the continuation rule, and only unify it with the accumulator in the termination rule.
• It is common to wrap a rule that uses an accumulator with a simpler rule that hides the initialisation of the accumulator.