home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / prolog / 2043 < prev    next >
Encoding:
Internet Message Format  |  1992-11-09  |  2.7 KB
  1. Path: sparky!uunet!pipex!warwick!uknet!edcastle!aiai!ken
  2. From: ken@aiai.ed.ac.uk (Ken Johnson)
  3. Newsgroups: comp.lang.prolog
  4. Subject: Re: collapsing lists to tree
  5. Message-ID: <7869@skye.ed.ac.uk>
  6. Date: 9 Nov 92 13:26:43 GMT
  7. References: <Bx5CFy.I6F@gabriel.keele.ac.uk>
  8. Followup-To: comp.lang.prolog
  9. Organization: Bugs-R-Us
  10. Lines: 88
  11.  
  12.  
  13. In article <Bx5CFy.I6F@gabriel.keele.ac.uk> csa09@keele.ac.uk (Paul
  14. Singleton) writes:
  15.  
  16. #  I wish to collapse a list of lists into a tree by recursively factoring
  17. #  out common initial elements, e.g.
  18.  
  19. The following code will do it.
  20. The invocation is
  21.  
  22.    ?- collapse(+Lists,-Tree)
  23.  
  24. I think it is worth documenting the following restrictions: (a) it is
  25. not bidirectional, (b) it does not enforce a canonical form of Tree, so
  26. that Trees which contain the same information may compare as unequal,
  27. (c) variables in Lists will be spuriously instantiated.  (Challenge:
  28. Write a bi-directional version without using var/1).
  29.  
  30. Sample successful queries:
  31.  
  32. 1.   ?- collapse([[a,b,d,e], [a,c,f,h], [a,c,f,i], [a,c,g,j], [k,l,m],
  33.         [k,n]], Tree). 
  34.  
  35.    Tree=[[a,[b,[d,[e,[]]]],[c,[f,[h,[]],[i,[]]],[g,[j,[]]]]],[k,[l,[m,[]]],
  36.      [n,[]]]]
  37.  
  38. which is a representation of
  39.  
  40.    a --- b --- d --- e
  41.      \
  42.       \  c --- f --- h
  43.            \     \
  44.             \     \  i
  45.              \
  46.                g --- j
  47.  
  48.    k --- l --- m
  49.      \
  50.       \  m
  51.  
  52.  
  53. 2. Your own example
  54.  
  55.    ?- collapse([[a,b,l,e],[a,b,o],[a,b,o,r,t]],Tree).
  56.  
  57.    Tree = [[a,[b,[l,[e,[]]],[o,[],[r,[t,[]]]]]]]
  58.  
  59. Note the use of [] as an end-of-sequence marker.  Without this, you
  60. would not be able to work out that [a,b,o] and [a,b,o,r,t] are both
  61. present in the tree, whereas [a,b,o,r] is absent.  (The need for a
  62. marker scuppered my first attempt, by the way.)
  63.  
  64.  
  65. % Code follows. Cut Here ------------ 8< ------------------------------------
  66. %
  67. %  Copyright Ken Johnson, November 1992.  You may use and distribute this
  68. %  code freely, but please acknowledge the source, and if you sell copies
  69. %  at a profit I want a share. 
  70.  
  71. % mode collapse(+,-).
  72.  
  73. collapse([],[]).
  74.  
  75. collapse([[]|Lists],[[]|More]) :-
  76.     collapse(Lists,More).
  77.  
  78. collapse([[H|T]|Lists],[[H|Sub]|More]) :-
  79.     group(H,[[H|T]|Lists],Grouped,Residue),
  80.     collapse(Grouped,Sub),
  81.     collapse(Residue,More).
  82.  
  83.  
  84. group(_,[],[],[]).
  85.  
  86. group(X,[[X|T]|Lists],[T|Grouped],Residue) :-
  87.     group(X,Lists,Grouped,Residue).
  88.  
  89. group(X,[[H|T]|Lists],Grouped,[[H|T]|Residue]) :-
  90.     \+ (X = H),
  91.     group(X,Lists,Grouped,Residue).
  92.  
  93.  
  94.  
  95. -- 
  96.                                   //// Ken Johnson, A I Applications Institute
  97. Don't get off while it's moving. ////       80 South Bridge, EDINBURGH EH1 1HN
  98.                                 ////                  E-mail ken@aiai.ed.ac.uk
  99.                                ////       Phone 031-650 2756  Fax 031-650 6513
  100.