6.2.1 Naive reverse using append

Here's a recursive definition of what is involved in reversing a list:

1. If we reverse the empty list, we obtain the empty list.

2. If we reverse the list [H|T], we end up with the list obtained by reversing T and concatenating with [H].

To see that the recursive clause is correct, consider the list [a,b,c,d]. If we reverse the tail of this list we obtain [d,c,b]. Concatenating this with [a] yields [d,c,b,a], which is the reverse of [a,b,c,d].

With the help of append it is easy to turn this recursive definition into Prolog:

naiverev([],[]).
naiverev([H|T],R) :- naiverev(T,RevT),append(RevT,[H],R).

Now, this definition is correct, but it is does an awful lot of work. It is very instructive to look at a trace of this program. This shows that the program is spending a lot of time carrying out appends. This shouldn't be too surprising: after, all, we are calling append recursively. The result is very inefficient (if you run a trace, you will find that it takes about 90 steps to reverse an eight element list) and hard to understand (the predicate spends most of it time in the recursive calls to append, making it very hard to see what is going on).

Not nice. And as we shall now see, there is a better way.