Path: utzoo!mnetor!uunet!lll-winken!lll-lcc!ames!pasteur!ucbvax!hplabs!otter!ijd
From: ijd@otter.hple.hp.com (Ian Dickinson)
Newsgroups: comp.lang.prolog
Subject: Embarrassingly simple problem
Message-ID: <1600005@otter.hple.hp.com>
Date: 17 Feb 88 16:18:35 GMT
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 50

I have just returned to writing Prolog code again, after an absence of a few
years (and what a joy it is :-).  Since my library of useful predicates has
dissappeared in the mists of time, I thought I'd bash out a new one.  Nothing
fancy, just the usual append/3 etc, and including reverse/2.  First year
undergraduate stuff really, or so I thought.

My first attempt at reverse/2 looked like:
%
% reverse( ?List1, ?List2 )
% True when List2 is the same as List1 with the elements reversed.
reverse( List1, List2 ) :-
	reverse( List1, List2, [] ).

reverse( [], List, List ).
reverse( [Head | Tail], List, Accum ) :-
	reverse( Tail, List, [Head | Accum] ).

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.

OK, in the declarative reading there is exactly one reverse of each list (it
is a one-to-one relation), so we could cheat by:

reverse( [], List, List ) :-
	!.
reverse( [Head | Tail], List, Accum ) :-
	reverse( Tail, List, [Head | Accum] ).

The problem then is that you only get one solution to:
	reverse( X, Y ).
instead of infinitely many.

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!

Thanks in advance,
Ian.

+-------------------------------------------------------------------------+
|Ian Dickinson,           Hewlett Packard Laboratories,  Bristol,  England|
|net: ijd@hplb.uucp   ijd%idickins@hplabs.HP.COM     ..!mcvax!ukc!hplb!ijd|
|"I've been to every single book I know               +-------------------+
| To soothe the thoughts that plague me so"  -Sting   | voice: 0272-799910|
|Nevertheless,  my opinions are entirely my own fault |                   |
+-----------------------------------------------------+-------------------+