# Accumulators

# 3.6. Accumulators¶

The condition that the right-hand side of `is`

should not contain variables sometimes determines the ordering of literals in the body of the clause. For instance, in the program below, which computes the length of a list, the `is`

literal should be placed after the recursive `length`

call, which instantiates `M`

. This means that the resolvent first collects as many `is`

literals as there are elements in the list, before doing the actual calculation. Each of these literals contains some ‘local’ variables that require some space in memory. The total memory requirements are thus proportional to the depth of the recursion.

```
naive_length([],0).
naive_length([_H|T],N):-naive_length(T,M),N is M+1.
```

Programs with tail recursion need less memory because they do all the work on one recursive level before proceeding to the next. There is a common trick to transform even the `length`

predicate above into a tail recursive program, using an auxiliary argument called an *accumulator*.

```
length_acc(L,N):-length_acc(L,0,N).
length_acc([],N,N).
length_acc([_H|T],N0,N):-N1 is N0+1,length_acc(T,N1,N).
```

`length_acc(L,N0,N)`

is true if `N`

is the number of elements in `L`

plus `N0`

. Initialising `N0`

to `0`

results in `N`

returning the length of `L`

. Note that the actual counting is done by the second argument: only when the list is empty is the third argument unified with the second argument. The main point is that, since the accumulator is given an initial value of `0`

, it is always instantiated, such that the `is`

literal can be placed before the recursive call.

Accumulators can be used in very many programs. Suppose we want to reverse the order of elements in a list. We could do this by recursively reversing the tail of the list, and putting the head at the end of the result:

```
naive_reverse([],[]).
naive_reverse([H|T],R):-naive_reverse(T,R1),append(R1,[H],R).
append([],Y,Y).
append([H|T],Y,[H|Z]):-append(T,Y,Z).
```

This predicate is called ‘naive’ because a lot of unnecessary work is done by the `append`

calls in the recursive clause.
By using an accumulator, we can get rid of the `append`

predicate, as follows:

```
reverse(X,Y):- reverse(X,[],Y).
reverse([],Y,Y).
reverse([H|T],Y0,Y):- reverse(T,[H|Y0],Y).
```

`reverse(X,Y0,Y)`

is true if `Y`

consists of the reversal of `X`

followed by `Y0`

. Initialising `Y0`

to `[]`

results in `Y`

returning the reversal of `X`

.

Draw the proof tree for the query `?-naive_reverse([a,b,c],R)`

.

The use of an accumulator in this more efficient program for reversing a list is closely related to another programming trick for increasing the efficiency of list handling. The idea is not to represent a list by a single term, but instead by a pair of terms `L1-L2`

, such that the list actually represented is the **difference** between `L1`

and `L2`

. The term `L1-L2`

is appropriately called a *difference list*; `L1`

is called the *plus list*, and `L2`

is called the *minus list*. For instance, the difference list `[a,b,c,d]-[d]`

represents the simple list `[a,b,c]`

, as does the difference list `[a,b,c,1234,5678]-[1234,5678]`

, and even the difference list `[a,b,c|X]-X`

. The last difference list can be seen as summarising every possible difference list representing the same simple list, by introducing a variable for the part which is not contained in the simple list.

As was remarked above, `reverse(X,Y0,Y)`

is true if `Y`

consists of the reversal of `X`

followed by `Y0`

. Another way to say the same thing is that the reversal of `X`

is the difference between `Y`

and `Y0`

. That is, the reversal of `X`

is represented by the difference list `Y-Y0`

! We can make this explicit by a small syntactic change to `reverse`

, resulting in the following program:

```
reverse_dl(X,Y):- reverse(X,Y-[]).
reverse([],Y-Y).
reverse([H|T],Y-Y0):- reverse(T,Y-[H|Y0]).
```

For instance, the third clause in this program says: if the reversal of `T`

is represented by the difference list `Y-[H|Y0]`

, then adding `H`

to the head of `T`

is the same as removing `H`

from the minus list in the difference list.

If the minus list is a variable, it can be used as a pointer to the end of the represented list. It is this property which makes difference lists so useful. For instance, if we unify `[a,b,c|X]-X`

with `Y-[d,e]`

, we get `Y=[a,b,c,d,e]`

– we have managed to append two lists together in a single unification step! In this example, the second term is not a difference list, nor is the result. If we want to append two difference lists

```
[a,b,c|XMinus]-XMinus
```

and

```
[d,e|YMinus]-YMinus
```

we must unify `XMinus`

with `[d,e|YMinus]`

(the plus list of the second difference list), such that the first difference list becomes

```
[a,b,c,d,e|YMinus]-[d,e|YMinus]
```

Combining the plus list of this difference list with `YMinus`

, we get exactly what we want.

In general, given two difference lists `XPlus-XMinus`

and `YPlus-YMinus`

, we unify `XMinus`

with `YPlus`

, and the result is given by `XPlus-YMinus`

(Figure 3.13):

```
append_dl(XPlus-XMinus,YPlus-YMinus,XPlus-YMinus):-
XMinus=YPlus.
```

or even shorter

```
append_dl(XPlus-YPlus,YPlus-YMinus,XPlus-YMinus).
```

Appending a simple list to another simple list of \(n\) elements requires \(n\) resolution steps; appending two difference lists requires no resolution at all, just one unification. Using difference lists is almost always a good idea if you have to do a lot of list processing.