Racket/Scheme Flatten Explanations
flatten, racket, recursion, scheme
Solution
The main difference is this:
- `flatten1` works by storing the output elements (first from the `cdr` side, then from the `car` side) into an accumulator. This works because lists are built from right to left, so working on the `cdr` side first is correct.
- `flatten2` works by recursively flattening the `car` and `cdr` sides, then `append`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.)
Problem
Can someone help me to break down exactly the order of execution for the following versions of flatten? I'm using Racket. version 1, is from racket itself, while version two is a more common? implementation. ``` (define (flatten1 list) (let loop ([l list] [acc null]) (printf "l = ~a acc = ~a\n" l acc) (cond [(null? l) acc] [(pair? l) (loop (car l) (loop (cdr l) acc))] [else (cons l acc)]))) (define (flatten2 l) (printf "l = ~a\n" l) (cond [(null? l) null] [(atom? l) (list l)] [else (append (flatten2 (car l)) (flatten2 (cdr l)))])) ``` Now, running the first example with '(1 2 3) produces: ``` l = (1 2 3) acc = () l = (2 3) acc = () l = (3) acc = () l = () acc = () l = 3 acc = () l = 2 acc = (3) l = 1 acc = (2 3) '(1 2 3) ``` while the second produces: ``` l = (1 2 3) l = 1 l = (2 3) l = 2 l = (3) l = 3 l = () '(1 2 3) ``` The order of execution seems different. In the first example, it looks like the second loop `(loop (cdr l) acc)` is firing before the first loop since '(2 3) is printing right away. Whereas in the second example, 1 prints before the '(2 3), which seems like the first call to flatten inside of append is evaluated first. I'm going through the Little Schemer but these are more difficult examples that I could really use some help on. Thanks a lot.