| << Prev | - Up - | Next >> |
Append is a useful predicate, and it is important to know how to use it. But it is just as important to know that it can be a source of inefficiency, and that you probably don't want to use it all the time.
Why is append a source of inefficiency? If you think about the way it works, you'll notice a weakness: append doesn't join two lists in one simple action. Rather, it needs to work its way down its first argument until it finds the end of the list, and only then can it carry out the concatenation.
Now, often this causes no problems. For example, if we have two lists and we just want to concatenate them, it's probably not too bad. Sure, Prolog will need to work down the length of the first list, but if the list is not too long, that's probably not too high a price to pay for the ease of working with append.
But matters may be very different if the first two arguments are given as variables. As we've just seen, it can be very useful to give append variables in its first two arguments, for this lets Prolog search for ways of splitting up the lists. But there is a price to pay: a lot of search is going on, and this can lead to very inefficient programs.
To illustrate this, we shall examine the problem of reversing a list. That is, we will examine the problem of defining a predicate which takes a list (say [a,b,c,d]) as input and returns a list containing the same elements in the reverse order (here [d,c,b,a]).
Now, a reverse predicate is a useful predicate to have around. As you will have realized by now, lists in Prolog are far easier to access from the front than from the back. For example, to pull out the head of a list L, all we have to do is perform the unification [H|_] = L; this results in H being instantiated to the head of L. But pulling out the last element of an arbitrary list is harder: we can't do it simply using unification. On the other hand, if we had a predicate which reversed lists, we could first reverse the input list, and then pull out the head of the reversed list, as this would give us the last element of the original list. So a reverse predicate could be a useful tool. However, as we may have to reverse large lists, we would like this tool to be efficient. So we need to think about the problem carefully.
And that's what we're going to do now. We will define two reverse predicates: a naive one, defined with the help of append, and a more efficient (and indeed, more natural) one defined using accumulators.
| << Prev | - Up - | Next >> |