🚀 go-pugleaf

In article <7869@skye.ed.ac.uk> ken@aiai.ed.ac.uk (Ken Johnson) writes:
>
>In article <Bx5CFy.I6F@gabriel.keele.ac.uk> csa09@keele.ac.uk (Paul
>Singleton) writes:
>
>#  I wish to collapse a list of lists into a tree by recursively factoring
>#  out common initial elements
>
>The following code will do it.

>I think it is worth documenting the following restrictions: (a) it is
>not bidirectional, (b) it does not enforce a canonical form of Tree, so
>that Trees which contain the same information may compare as unequal,
>(c) variables in Lists will be spuriously instantiated.  (Challenge:
>Write a bi-directional version without using var/1).

Trivial if you have NU-Prolog.  Replace the unsound negation (\+) by a
sound version, declare the predicates pure, run the code through ``nac''
to automatically produce some control information and presto, out pops a
reversible version!  Takes less than a minute and virtually no thinking.

% the following code has been nac'ed
% 
% procedure collapse/2 is locally deterministic.

?- pure collapse/2.
?- collapse(A, B) when A or B.
collapse([], []).
collapse([[]|A], [[]|B]) :-
	collapse(A, B).
collapse([[A|B]|C], [[A|D]|E]) :-
	group(A, [[A|B]|C], F, G),
	collapse(F, D),
	collapse(G, E).

?- pure group/4.
?- group(A, B, C, D) when (B or C) and (B or D).
group(A, [], [], []).
group(A, [[A|B]|C], [B|D], E) :-
	group(A, C, D, E).
group(A, [[B|C]|D], E, [[B|C]|F]) :-
	A ~= B,
	group(A, D, E, F).

	lee