Path: utzoo!mnetor!uunet!mcvax!enea!zyx!bd
From: bd@zyx.UUCP (Bjorn Danielsson)
Newsgroups: comp.lang.prolog
Subject: Re: Embarrassingly simple problem
Message-ID: <2236@zyx.UUCP>
Date: 22 Feb 88 22:38:04 GMT
References: <1600005@otter.hple.hp.com>
Reply-To: bd@zyx.UUCP (Bjorn Danielsson)
Organization: ZYX Sweden AB, Stockholm
Lines: 30

In article <1600005@otter.hple.hp.com> ijd@otter.hple.hp.com (Ian Dickinson) writes:
> [...]
>I don't remember reverse/2 being asymmetrical before, so what am I doing
>wrong?  Has my brain atrophied completely in three years?  Help, somebody,
>please!
>

The problem is not as trivial as it seems.
One symmetrical solution is:

     reverse(X, Y) :- reverse(X, [], Y, []).

     reverse(X, X, Y, Y).
     reverse([A|X1], X2, Y1, Y2) :-
	    reverse(Y1, [A|Y2], X1, X2).

The arguments to reverse/4 are difference pairs for the two lists.
The second clause may look a little strange, but the logical meaning is
simply that if the last element of list Y is A, and the reversal of all but
the last element is X, then the reversal of Y is [A|X].
The reason for swapping the argument pairs in the recursive call is to ensure
that the second clause is used on both of the lists, to avoid infinite loops.
The runtime behaviour is not particularly good if all you want is fast
reversal of fixed-length lists. A choice-point is created and removed at each
recursive call, and one choice-point is left on the stack after succeeding.
Some heap garbage may be created, although not in the typical case when
one of the arguments is uninstantiated.

-- 
Bjorn Danielsson, ZYX Sweden AB, +46 (8) 665 32 05, bd@zyx.SE