Prolog Brain Teaser
Author Message
Prolog Brain Teaser

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 :-) :-)

Sun, 09 Aug 1992 02:27:06 GMT
Prolog Brain Teaser

Quote:

>  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

Sun, 23 Aug 1992 16:29:31 GMT
Prolog Brain Teaser

Quote:

>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

Mon, 24 Aug 1992 09:24:18 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages
 11. brain teaser