The main difference is this:
flatten1
works by storing the output elements (first from thecdr
side, then from thecar
side) into an accumulator. This works because lists are built from right to left, so working on thecdr
side first is correct.flatten2
works by recursively flattening thecar
andcdr
sides, thenappend
ing them together.
flatten1
is faster, especially if the tree is heavy on the car
side: the use of an accumulator means that there is no extra list copying, no matter what. Whereas, the append
call in flatten2
causes the left-hand side of the append
to be copied, which means lots of extra list copying if the tree is heavy on the car
side.
So in summary, I would consider flatten2
a beginner's implementation of flatten, and flatten1
a more polished, professional version. See also my implementation of flatten, which works using the same principles as flatten1
, but using a left-fold instead of the right-fold that flatten1
uses.
(A left-fold solution uses less stack space but potentially more heap space. A right-fold solution uses more stack and usually less heap, though a quick read of flatten1
suggests in this case that the heap usage is about the same as my implementation.)