delistifying lists...

[Steve Strassmann <straz@cambridge.apple.com>]

>Date: Mon, 17 Aug 92 07:49:04 -0400
>From: Luke Hohmann <hohmann@csmil.umich.edu>
>To: info-macl@cambridge.apple.com
>Subject: delistifying lists...
>
>
>I needed a function to "delistofy" lists. Here is the function I wrote
>and some sample runs. My question to you is: can you submit a faster/better/
>cleaner/more robust version of this function? THANKS!
>
>? (defun delistify (l)
>  (cond ((null l) nil)
>        ((atom l) l)
>        ((listp (car l))
>         (delistify (append (car l) (cdr l))))
>        (t
>         (cons (delistify (car l))
>               (delistify (cdr l))))))
>
>delistify
>? (delistify '(1 2 3))
>(1 2 3)
>? (delistify '((1 2 3) 4 5 6))
>(1 2 3 4 5 6)
>? (delistify '(1 2 3 (4 5 6)))
>(1 2 3 4 5 6)
>? (delistify '((1 2 3) 4 5 6 ((7 8 9))))
>(1 2 3 4 5 6 7 8 9)
>? 
>
>  -- Luke

 This is called "flatten" in most lisp textbooks. There's an excellent
discussion in Norvig's "Paradigms of AI Programming" (chapter 10.4,
page 328) of why the APPEND version is inefficient.

Here's what most people will write. Due to the APPEND (which
always copies its first arg) it can cons O(N^2) cells on
an input with N atoms.

(defun flatten (input)
  (cond ((null input) nil)
        ((atom input) (list input))
        (t (append (flatten (first input))
                   (flatten (rest input))))))


Here's a more efficient version:

(defun flatten (input &optional accumulator)
  (cond ((null input) accumulator)
        ((atom input) (cons input accumulator))
        (t (flatten (first input)
                    (flatten (rest input) accumulator)))))