home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / lisp / mcl / 1248 < prev    next >
Encoding:
Text File  |  1992-08-17  |  2.0 KB  |  68 lines
  1. Path: sparky!uunet!portal!apple!apple!cambridge.apple.com!straz@cambridge.apple.com
  2. From: straz@cambridge.apple.com (Steve Strassmann)
  3. Newsgroups: comp.lang.lisp.mcl
  4. Subject: delistifying lists...
  5. Message-ID: <9208171910.AA04590@cambridge.apple.com>
  6. Date: 17 Aug 92 20:09:04 GMT
  7. Sender: info-mcl-request@cambridge.apple.com
  8. Lines: 54
  9. Approved: comp.lang.lisp.mcl@Cambridge.Apple.C0M
  10. Full-Name: Steve Strassmann
  11. Original-To: Luke Hohmann <hohmann@csmil.umich.edu>
  12. Original-Cc: info-mcl
  13.  
  14. >Date: Mon, 17 Aug 92 07:49:04 -0400
  15. >From: Luke Hohmann <hohmann@csmil.umich.edu>
  16. >To: info-macl@cambridge.apple.com
  17. >Subject: delistifying lists...
  18. >
  19. >
  20. >I needed a function to "delistofy" lists. Here is the function I wrote
  21. >and some sample runs. My question to you is: can you submit a faster/better/
  22. >cleaner/more robust version of this function? THANKS!
  23. >
  24. >? (defun delistify (l)
  25. >  (cond ((null l) nil)
  26. >        ((atom l) l)
  27. >        ((listp (car l))
  28. >         (delistify (append (car l) (cdr l))))
  29. >        (t
  30. >         (cons (delistify (car l))
  31. >               (delistify (cdr l))))))
  32. >
  33. >delistify
  34. >? (delistify '(1 2 3))
  35. >(1 2 3)
  36. >? (delistify '((1 2 3) 4 5 6))
  37. >(1 2 3 4 5 6)
  38. >? (delistify '(1 2 3 (4 5 6)))
  39. >(1 2 3 4 5 6)
  40. >? (delistify '((1 2 3) 4 5 6 ((7 8 9))))
  41. >(1 2 3 4 5 6 7 8 9)
  42. >? 
  43. >
  44. >  -- Luke
  45.  
  46.  This is called "flatten" in most lisp textbooks. There's an excellent
  47. discussion in Norvig's "Paradigms of AI Programming" (chapter 10.4,
  48. page 328) of why the APPEND version is inefficient.
  49.  
  50. Here's what most people will write. Due to the APPEND (which
  51. always copies its first arg) it can cons O(N^2) cells on
  52. an input with N atoms.
  53.  
  54. (defun flatten (input)
  55.   (cond ((null input) nil)
  56.         ((atom input) (list input))
  57.         (t (append (flatten (first input))
  58.                    (flatten (rest input))))))
  59.  
  60.  
  61. Here's a more efficient version:
  62.  
  63. (defun flatten (input &optional accumulator)
  64.   (cond ((null input) accumulator)
  65.         ((atom input) (cons input accumulator))
  66.         (t (flatten (first input)
  67.                     (flatten (rest input) accumulator)))))
  68.