home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / prolog / 2056 < prev    next >
Encoding:
Text File  |  1992-11-10  |  1.8 KB  |  57 lines
  1. Newsgroups: comp.lang.prolog
  2. Path: sparky!uunet!munnari.oz.au!cs.mu.OZ.AU!munta.cs.mu.OZ.AU!lee
  3. From: lee@munta.cs.mu.OZ.AU (Lee Naish)
  4. Subject: Re: collapsing lists to tree
  5. Message-ID: <9231618.4770@mulga.cs.mu.OZ.AU>
  6. Sender: news@cs.mu.OZ.AU
  7. Organization: Department of Computer Sci, University of Melbourne
  8. References: <Bx5CFy.I6F@gabriel.keele.ac.uk> <7869@skye.ed.ac.uk>
  9. Date: Wed, 11 Nov 1992 07:04:22 GMT
  10. Lines: 45
  11.  
  12. In article <7869@skye.ed.ac.uk> ken@aiai.ed.ac.uk (Ken Johnson) writes:
  13. >
  14. >In article <Bx5CFy.I6F@gabriel.keele.ac.uk> csa09@keele.ac.uk (Paul
  15. >Singleton) writes:
  16. >
  17. >#  I wish to collapse a list of lists into a tree by recursively factoring
  18. >#  out common initial elements
  19. >
  20. >The following code will do it.
  21.  
  22. >I think it is worth documenting the following restrictions: (a) it is
  23. >not bidirectional, (b) it does not enforce a canonical form of Tree, so
  24. >that Trees which contain the same information may compare as unequal,
  25. >(c) variables in Lists will be spuriously instantiated.  (Challenge:
  26. >Write a bi-directional version without using var/1).
  27.  
  28. Trivial if you have NU-Prolog.  Replace the unsound negation (\+) by a
  29. sound version, declare the predicates pure, run the code through ``nac''
  30. to automatically produce some control information and presto, out pops a
  31. reversible version!  Takes less than a minute and virtually no thinking.
  32.  
  33. % the following code has been nac'ed
  34. % 
  35. % procedure collapse/2 is locally deterministic.
  36.  
  37. ?- pure collapse/2.
  38. ?- collapse(A, B) when A or B.
  39. collapse([], []).
  40. collapse([[]|A], [[]|B]) :-
  41.     collapse(A, B).
  42. collapse([[A|B]|C], [[A|D]|E]) :-
  43.     group(A, [[A|B]|C], F, G),
  44.     collapse(F, D),
  45.     collapse(G, E).
  46.  
  47. ?- pure group/4.
  48. ?- group(A, B, C, D) when (B or C) and (B or D).
  49. group(A, [], [], []).
  50. group(A, [[A|B]|C], [B|D], E) :-
  51.     group(A, C, D, E).
  52. group(A, [[B|C]|D], E, [[B|C]|F]) :-
  53.     A ~= B,
  54.     group(A, D, E, F).
  55.  
  56.     lee
  57.