duncan@mva.cs.liv.ac.uk (02/21/90)
With apologies to the many readers who will be familiar with
this little Prolog Puzzle which came to my notice some time ago.
I thought it was worth posting. It has (to me at least) a pleasing but
non-obvious solution. Here goes!
You are given the standard definition of append/3
append( [], L, L).
append( [H|T], L, [H|T1]):- append( T, L, T1).
which can be used reversibly to append two lists and to generate sublists.
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.
There are four obvious definitions but only one of them works. Try to
solve it first without testing on a Prolog system.
Have fun.
Duncan Lowes
P.S. Before I get flamed this is not my homework :-) :-)coop@hawksnest.cerc.wvu.wvnet.edu (Cooperate) (02/24/90)
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. > Here is my solution ... append([],L,L). append([H|T],L,[H|T1]) :- append(T,L,T1). app4([],[],L,L). app4([],[H|T],L1,[H|T1]) :- append(T,L1,T1). app4([H|T],L1,L2,[H|T1]) :- app4(T,L1,L2,T1). First, narrow it down to two lists, then use regular append. Also works in generation of sublists recursively. Note that on the second clause, an [H|T] notation was used for the second argument in order to disable binding to an empty list and therefore duplicating results on sublists. Boris Pelakh "Software - a spell one casts on a pelakh@cerc.wvu.wvnet.edu computer to transform input into coop@cerc.wvu.wvnet.edu errors." -- Me Disclaimer : If my employer knew what I did with the time I get paid for, I would be out of a job. Let's keep this between us, OK ?
micha@ecrcvax.UUCP (Micha Meier) (03/07/90)
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
lee@munnari.oz.au (Lee Naish) (03/08/90)
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