🚀 go-pugleaf

"PS" == Paul Singleton <csa09@keele.ac.uk> writes:
  PS> I wish to collapse a list of lists into a tree by recursively
  PS> factoring out common initial elements, e.g.
  .
  .
  .
  PS> Is there an established name for this latter data structure?  Is there
  PS> published code for creating it?

The tree data structure has been call a "layered stream"; more information
in 

@InProceedings{Okumura:87,
  author = 	"A. Okumura and Y. Matsumoto",
  title = 	"Parallel Programming with Layered Streams",
  pages = 	"224-233",
  crossref = {SLP-87}
}

   I wish to collapse a list of lists into a tree by recursively factoring
   out common initial elements, e.g.

       [ [ a, b, l, e],
	 [ a, b, o],
	 [ a, b, o, r, t],
	 ...

   into

     - a - b - l - e - []
	     \
	       o - []
		 \
		   r - t - []

   Is there an established name for this latter data structure?  Is there
   published code for creating it?

Rule #1 for Algorithms: Look up Knuth.

In this particular case:
Knuth, D. E. The Art of Computer Programming
Vol 3 Sorting & Searching
pp 481-489

The data-structure you're talking about is called a ``Trie''.
For a neato application, have a look at the TeX source code...

Cheers,
Dipankar Gupta
HP Labs Bristol UK
dg@hplb.hpl.hp.com
--
--

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

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