Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!mcsun!unido!ecrcvax!micha
From: micha@ecrcvax.UUCP (Micha Meier)
Newsgroups: comp.lang.prolog
Subject: Re: Prolog Brain Teaser
Message-ID: <815@ecrcvax.UUCP>
Date: 7 Mar 90 08:29:31 GMT
References: <5091.25e18bfa@mva.cs.liv.ac.uk>
Reply-To: micha@ecrcvax.UUCP (Micha Meier)
Organization: ECRC, Munich 81, West Germany
Lines: 27

In article <5091.25e18bfa@mva.cs.liv.ac.uk> duncan@mva.cs.liv.ac.uk writes:
>  The problem is this. Using this definition,  define append/4 which will
>append 3 lists to form a 4th *AND* will work reversibly to generate all
>sublist solutions without looping on backtracking.

In Sepia one writes (in other Prologs with coroutining it is something similar)

delay append(A, _, C) if var(A), var(C).
append([], L, L).
append([X|L1], L2, [X|L3]) :-
	append(L1, L2, L3).

append(A, B, C, D) :-
	append(A, B, L1),
	append(L1, C, D).

I know you ment something else, but I just cannot resist :-)
The call to append/3 delays if both first and third arguments are
uninstantiated. I think it was Lee Naish who first mentioned this predicate.

It is interesting to note that this predicate does not run much slower
than the solution which does not use coroutining and defines
append/4 with several clauses. The reason is that the cost for
scheduling of suspended and woken append/3 calls in the former is balanced
by the list unifications in the head of append/4 in the latter.

--Micha Meier