>>17's second implementation is fairly fast, it just traverses the tree, and pushes the nodes into a list, then reverses the list. It could be made even faster by replacing PUSH/NREVERSE idiom with a more elaborate WITH-COLLECTORS or COLLECTING macro (which keeps a tail pointer), but I've done the benchmarks, and it seems PUSH/NREVERSE is actually faster for small lists, since WITH-COLLECTOR(S) introduces a small overhead:
CL-USER> (time (flatten '(1 2 3 4 (a b c (d (e (f (g h j) k) 9 8) 7) 6 ()))))
Evaluation took:
0.000 seconds of real time
0.000000 seconds of total run time (0.000000 user, 0.000000 system)
100.00% CPU
3,285 processor cycles
0 bytes consed
This is reasonably fast for me.
>>29
One point proven here is that while things are possible to do in C, the coder is much lazier to implement everything himself, or he can choose to oversimplify the problem in some way to make it more manageable to solve (I was looking over a book containing various problems used in compsci competitions throughout the world, and I noticed almost all problems have artificial limits imposed upon them so they would be easier solved in C or Pascal or whatever teaching language they had, things like saying there would be no more than 100 items in the input, so the programmer could just use an static array). Sure, I can do everything I can do in Lisp in C, but I have to say, I'm feeling much lazier to write C code than Lisp, since I have to reinvent the wheel a lot of the time, even if I reuse my own libraries. A Lisp programmer is much more likely to be willing to solve a problem, in this thread we have 4 flatten implementations in Lisp/Scheme, and one incomplete C one.