Very interesting!
(progn
(defun Flatten ( lst )
;; by Doug Broad
(cond
((null lst) nil)
((atom lst) (list lst))
((atom (car lst)) (cons (car lst) (Flatten (cdr lst))))
((append (Flatten (car lst))(Flatten (cdr lst))))
)
)
(defun Squish ( lst )
;; © 2005 Michael Puckett
(apply 'append
(mapcar 'SquishEx lst)
)
)
(defun SquishEx ( x / a )
;; © 2005 Michael Puckett
(if x
(if (listp x)
(if (listp (setq a (car x)))
(append (Squish a) (Squish (cdr x)))
(cons a (Squish (cdr x)))
)
(list x)
)
'(nil)
)
)
(setq lst
'(1 (2 (3 (4 (5 (6 (7 (8))))))))
)
(while t
(princ
(strcat
"\nFlattened length = "
(itoa (length (squish lst)))
"\n"
)
)
(Benchmark
'( (flatten lst)
(squish lst)
)
)
(setq lst (append lst lst))
)
(princ)
)
Results --
Flattened length = 8, 16384 iteration(s): Flatten performing better
(FLATTEN LST).....1656 / 1.35 <fastest>
(SQUISH LST)......2234 / 1.00 <slowest>
Flattened length = 16, 8192 iteration(s):
(FLATTEN LST).....1344 / 1.37 <fastest>
(SQUISH LST)......1843 / 1.00 <slowest>
Flattened length = 32, 4096 iteration(s):
(FLATTEN LST).....1265 / 1.31 <fastest>
(SQUISH LST)......1656 / 1.00 <slowest>
Flattened length = 64, 2048 iteration(s):
(FLATTEN LST).....1360 / 1.17 <fastest>
(SQUISH LST)......1594 / 1.00 <slowest>
Flattened length = 128, 1024 iteration(s): Squish performing better
(SQUISH LST)......1547 / 1.03 <fastest>
(FLATTEN LST).....1594 / 1.00 <slowest>
Flattened length = 256, 512 iteration(s):
(SQUISH LST)......1562 / 1.35 <fastest>
(FLATTEN LST).....2109 / 1.00 <slowest>
Flattened length = 512, 256 iteration(s):
(SQUISH LST)......1531 / 2.09 <fastest>
(FLATTEN LST).....3203 / 1.00 <slowest>
Flattened length = 1024, 128 iteration(s):
(SQUISH LST)......1562 / 3.51 <fastest>
(FLATTEN LST).....5484 / 1.00 <slowest>
Flattened length = 2048, 64 iteration(s):
(SQUISH LST).......1562 / 6.64 <fastest>
(FLATTEN LST).....10375 / 1.00 <slowest>
Flattened length = 4096, 32 iteration(s):
(SQUISH LST).......1578 / 12.68 <fastest>
(FLATTEN LST).....20016 / 1.00 <slowest>
Flattened length = 8192, 16 iteration(s):
(SQUISH LST).......1438 / 23.54 <fastest>
(FLATTEN LST).....33844 / 1.00 <slowest>
Flattened length = 16384, 8 iteration(s):
(SQUISH LST).......1312 / 38.73 <fastest>
(FLATTEN LST).....50813 / 1.00 <slowest>
Flattened length = 32768, 4 iteration(s):
(SQUISH LST).......1265 / 72.90 <fastest>
(FLATTEN LST).....92218 / 1.00 <slowest>
Flattened length = 65536, 2 iteration(s):
(SQUISH LST)........1187 / 104.07 <fastest>
(FLATTEN LST).....123532 / 1.00 <slowest>
Flattened list length = 131072
*KAFREAKINBOOM*, Hard error occurred ***
Flatten crashed when the list had grown to 131072 items (when denested) because it blew up the stack. Squish still crushed the big 'ol list down, in 1250 milliseconds (1 iteration), very reasonable! :)
Nonetheless, flatten remains an eloquent example of recursion and Doug Broad an excellent codesmith (a very nice gentlemen too I might add).