Now we produce a variant which achieves a similar (but not identical) effect. We introduce a new kind of variable: the accumulator. Consider the example:
triple([] Y Y).We still have the first argument as the recursion argument but now the third argument is the result argument and the second argument is the accumulator. Now we can see that the recursive call triple(T1 [H2triple([H1
T1] X Y):-
H2 is 3*H1
triple(T1 [H2
X] Y).
X]
Y) is
simpler in the first argument than the head triple([H1
T1]
X
Y)
and more complex in the second argument (the accumulator).
Note that the third argument is unchanged. If this is so how can it take a value at all? Well the recursion stops once we reach a call with its first argument as the empty list. This means that we will need to unify the goal with the head of the first clause. This will result in the second argument (the accumulator) being unified with the third argument (the result) which at this point is an unbound variable. We establish that this up-to-now unchanged variable is bound to the term in the accumulator. Following back along the path of recursive calls we see that (more or less) the result we want is returned.
The goal triple([1 2 3] [] X) will result in X=[9 6 3]. Note two things: the expected order is reversed and that the accumulator has to be initialised in the original call. Sometimes however the order is not too important.
Here is the schema:
process_all( Info [] Acc Acc).process_all( Info [H1
T1] Acc Ans):-
process_one( Info H1 H2)
process_all( Info T1 [H2
Acc] Ans).
where process_one/1 takes Info and H1 as input and outputs H2