🚀 go-pugleaf

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, e.g.

The following code will do it.
The invocation is

   ?- collapse(+Lists,-Tree)

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

Sample successful queries:

1.   ?- collapse([[a,b,d,e], [a,c,f,h], [a,c,f,i], [a,c,g,j], [k,l,m],
        [k,n]], Tree). 

   Tree=[[a,[b,[d,[e,[]]]],[c,[f,[h,[]],[i,[]]],[g,[j,[]]]]],[k,[l,[m,[]]],
     [n,[]]]]

which is a representation of

   a --- b --- d --- e
     \
      \  c --- f --- h
           \     \
            \     \  i
             \
               g --- j

   k --- l --- m
     \
      \  m


2. Your own example

   ?- collapse([[a,b,l,e],[a,b,o],[a,b,o,r,t]],Tree).

   Tree = [[a,[b,[l,[e,[]]],[o,[],[r,[t,[]]]]]]]

Note the use of [] as an end-of-sequence marker.  Without this, you
would not be able to work out that [a,b,o] and [a,b,o,r,t] are both
present in the tree, whereas [a,b,o,r] is absent.  (The need for a
marker scuppered my first attempt, by the way.)


% Code follows. Cut Here ------------ 8< ------------------------------------
%
%  Copyright Ken Johnson, November 1992.  You may use and distribute this
%  code freely, but please acknowledge the source, and if you sell copies
%  at a profit I want a share. 

% mode collapse(+,-).

collapse([],[]).

collapse([[]|Lists],[[]|More]) :-
	collapse(Lists,More).

collapse([[H|T]|Lists],[[H|Sub]|More]) :-
	group(H,[[H|T]|Lists],Grouped,Residue),
	collapse(Grouped,Sub),
	collapse(Residue,More).


group(_,[],[],[]).

group(X,[[X|T]|Lists],[T|Grouped],Residue) :-
	group(X,Lists,Grouped,Residue).

group(X,[[H|T]|Lists],Grouped,[[H|T]|Residue]) :-
	\+ (X = H),
	group(X,Lists,Grouped,Residue).



-- 
                                  //// Ken Johnson, A I Applications Institute
Don't get off while it's moving. ////       80 South Bridge, EDINBURGH EH1 1HN
                                ////                  E-mail ken@aiai.ed.ac.uk
                               ////       Phone 031-650 2756  Fax 031-650 6513