Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!brutus.cs.uiuc.edu!apple!uokmax!munnari.oz.au!lee
From: lee@munnari.oz.au (Lee Naish)
Newsgroups: comp.lang.prolog
Subject: Re: Prolog Brain Teaser
Message-ID: <3298@munnari.oz.au>
Date: 8 Mar 90 01:24:18 GMT
References: <5091.25e18bfa@mva.cs.liv.ac.uk> <815@ecrcvax.UUCP>
Sender: news@cs.mu.oz.au
Reply-To: lee@munmurra.UUCP (Lee Naish)
Organization: Comp Sci, University of Melbourne
Lines: 30

In article <815@ecrcvax.UUCP> micha@ecrcvax.UUCP (Micha Meier) writes:
>append(A, B, C, D) :-
>	append(A, B, L1),
>	append(L1, C, D).
>
> I think it was Lee Naish who first mentioned this predicate.

Yes, to illustrate how easy it is to get reversible procedures when you
have a decent coroutining system.  As Ken Kahn (and others I'm sure) has
pointed out is actually rather more efficient to write it as follows,
so the elements of A are not scanned twice:

append3(A, B, C, D) :-
       append(B, C, BC),
       append(A, BC, D).

As Richard O'Keefe (I think, and others) has pointed out, we can now
reverse the two calls to append/3 to make it works forwards and
backwards without coroutines:

append3(A, B, C, D) :-
       append(A, BC, D),
       append(B, C, BC).

This is the best way to write it, but it does require a fair bit of
thought.  If you have coroutines you can be lazy and write it any way
you want - its got a very good chance of working in all modes which
result in a finite number of solutions.

	lee