Path: utzoo!mnetor!uunet!mcvax!ukc!stl!stc!idec!camcon!mb
From: mb@camcon.uucp (Mike Bell)
Newsgroups: comp.lang.prolog
Subject: Re: Embarrassingly simple problem (Embarassingly simple answer)
Message-ID: <1283@titan.camcon.uucp>
Date: 2 Mar 88 11:16:36 GMT
References: <1600005@otter.hple.hp.com>
Organization: Cambridge Consultants Ltd., Cambridge, UK
Lines: 52

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

The problem arises with clause 2 of your reverse/3 method.  Giving it an
uninstantiated variable as a first argument causes lists of increasing length
to be generated. The only return is via clause 1, and there is nothing to
prevent continued backtracking after this solution has been generated.

Zanconato[1] uses the following method to solve this problem:

reverse( List1, List2 ) :-
    gen_list( List1, List2 ),
    reverse( List1, List2, [] ).

reverse( [], List, List ).
reverse( [H|T], List, Accum ):-
    reverse( T, List, [H|Accum] ).

gen_list( [], [] ).
gen_list( [H1|T1], [H2|T2] ) :-
    gen_list( T1, T2 ).


The trick here is to pre-instantiate List1/2 to a list with the correct
number of elements (a symmetric operation) *before* the call to
reverse/3.  By doing this, of course, neither list can change in side,
so reverse/3 can only generate *one* solution. gen_list/2 is the procedure
which generates the multiple solutions.

> I don't remember reverse/2 being asymmetrical before, so what am I doing
> wrong?  

Reverse is *inherently* asymmetrical. One of the lists must be reversed
and unified with the other. You can't reverse both the lists. Hence a 
loss of symmetry is inevitable.

> ...     Has my brain atrophied completely in three years?  Help, somebody,
> please!

No Comment!

-- Mike --

[1]. RAMBO, Rule Based Access to ODDS, CCL Technical Report C2585-UM-001a,
     Zanconato,R., 1987.

-- 
---------------	 UUCP:  ...!ukc!camcon!mb | Cambridge Consultants Ltd
-- Mike Bell --	 or:    mb@camcon.uucp    | Science Park, Milton Road
---------------	 Phone: +44 223 358855    | Cambridge CB4 4DW
[These opinions aren't necessarily my company's, or even my own!]