Subject: Re: flatten
From: rpw3@rpw3.org (Rob Warnock)
Date: Wed, 10 Oct 2007 19:06:28 -0500
Newsgroups: comp.lang.lisp
Message-ID: <IbCdnRrcZKCZ9JDanZ2dnUVZ_vKunZ2d@speakeasy.net>
Madhu  <enometh@meer.net> wrote:
+---------------
| * Ken Tilton <kennytilton@optonline.net> <kRYOi.134$I44.81@newsfe12.lga> :
| |> (defun flatten (l)
| |>  (cond ((null l) ())
| |>     ((atom l) (list l))
| |>     (t (append (flatten (car l))
| |>            (flatten (cdr l))))))
| |
| | Super. Just super. No wonder Lisp is slow and, thx to Google, getting
| | slower. Where are all the clowns who laughed when I said a Lisper had
| | to understand consing? Hiding? I understand.
| 
| Unfortunately I had marked as No-Archive the fast stacked version of
| FLATTEN I had posted last year on <m3bqmgigzp.fsf@robolove.meer.net>
| 
| I'd like to think this style is as idiomatic to any "True Lisper" as any
| other :)
| 
| (defun flatten (x &aux stack result)
|   (flet ((rec (item)
|            (if (atom item)
|                (push item result)
|                (loop for elem in item do (push elem stack)))))
|     (declare (inline rec))
|     (rec x)
|     (loop while stack do (funcall #'rec (pop stack)))
|     result))
+---------------

The one inside CMUCL conses much less than yours [and AFAICT,
conses the minimal amount possible], but uses more control
stack and thus will blow up in some cases where yours won't.
From "cmucl-19c/src/compiler/srctran.lisp":

    ;;; Simple utility to flatten a list
    (defun flatten-list (x)
      (labels ((flatten-helper (x r);; 'r' is the stuff to the 'right'.
		 (cond ((null x) r)
		       ((atom x)
			(cons x r))
		       (t (flatten-helper (car x)
					  (flatten-helper (cdr x) r))))))
	(flatten-helper x nil)))


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607