Path: utzoo!mnetor!uunet!seismo!sundc!pitstop!sun!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Embarrassingly simple problem
Message-ID: <664@cresswell.quintus.UUCP>
Date: 19 Feb 88 04:05:27 GMT
References: <1600005@otter.hple.hp.com>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 50

In article <1600005@otter.hple.hp.com>,
ijd@otter.hple.hp.com (Ian Dickinson) writes:
{I have taken the liberty of switching the arguments of reverse/3 into
 the usual inputs-precede-outputs order.
}
> reverse(List1, List2) :-
> 	reverse(List1, [], List2).
> 
> reverse([], List, List).
> reverse([Head|Tail], Accum, List) :-
> 	reverse(Tail, [Head|Accum], List).
> 
> So far, so good.  Works fine for goals like
> 	reverse([a,b,c], X).
> 
> It fails, however, for
> 	reverse(X, [a,b,c]).
> I mean, it gives one (correct) solution, but then goes into infinite loop on
> backtracking.  Bad news.
> 
> 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!

You have lost your memory, but not your mind (:-).
What you have coded is the operation the Quintus Prolog library
calls rev/2, and it is and has always been asymmetric like this.
The basic reason is that reverse/3 is trying to guess its first
argument, and it never gives up hope that a longer guess might
work.

There is a standard workaround for things like this.

reverse(List, Reversed) :-
	same_length(List, Reversed),
	rev(List, [], Reversed).

rev([], R, R).
rev([H|T], L, R) :-
	rev(T, [H|L], R).

same_length([], []).
same_length([_|X], [_|Y]) :-
	same_length(X, Y).

I think it was Ed Stabler who showed me this solution, in the
context of the N-Queens program.  The same dodge works very
nicely for permutation/2 (just as we have both rev/2 for speed
and reverse/2 for purity, we have perm/2 and permutation/2),
and for several other cases.