| << Prev | - Up - |
The better way is to use an accumulator. The underlying idea is simple and natural. Our accumulator will be a list, and when we start it will be empty. Suppose we want to reverse [a,b,c,d]. At the start, our accumulator will be []. So we simply take the head of the list we are trying to reverse and add it as the head of the accumulator. We then carry on processing the tail, thus we are faced with the task of reversing [b,c,d], and our accumulator is [a]. Again we take the head of the list we are trying to reverse and add it as the head of the accumulator (thus our new accumulator is [b,a]) and carry on trying to reverse [c,d]. Again we use the same idea, so we get a new accumulator [c,b,a], and try to reverse [d]. Needless to say, the next step yields an accumulator [d,c,b,a] and the new goal of trying to reverse []. This is where the process stops: and our accumulator contains the reversed list we want. To summarize: the idea is simply to work our way through the list we want to reverse, and push each element in turn onto the head of the accumulator, like this:
List: [a,b,c,d] Accumulator: []
List: [b,c,d] Accumulator: [a]
List: [c,d] Accumulator: [b,a]
List: [d] Accumulator: [c,b,a]
List: [] Accumulator: [d,c,b,a]This will be efficient because we simply blast our way through the list once: we don't have to waste time carrying out concatenation or other irrelevant work.
It's also easy to put this idea in Prolog. Here's the accumulator code:
accRev([H|T],A,R) :- accRev(T,[H|A],R).
accRev([],A,A).This is classic accumulator code: it follows the same pattern as the arithmetic examples we examined in the previous lecture. The recursive clause is responsible for chopping of the head of the input list, and pushing it onto the accumulator. The base case halts the program, and copies the accumulator to the final argument.
As is usual with accumulator code, it's a good idea to write a predicate which carries out the required initialization of the accumulator for us:
rev(L,R) :- accRev(L,[],R). Again, it is instructive to run some traces on this program and compare it with naiverev. The accumulator based version is clearly better. For example, it takes about 20 steps to reverse an eight element list, as opposed to 90 for the naive version. Moreover, the trace is far easier to follow. The idea underlying the accumulator based version is simpler and more natural than the recursive calls to append.
Summing up, append is a useful program, and you certainly should not be scared of using it. However you also need to be aware that it is a source of inefficiency, so when you use it, ask yourself whether there is a better way. And often there are. The use of accumulators is often better, and (as the reverse example show) accumulators can be a natural way of handling list processing tasks. Moreover, as we shall learn later in the course, there are more sophisticated ways of thinking about lists (namely by viewing them as difference lists) which can also lead to dramatic improvements in performance.
| << Prev | - Up - |