Unpacking / smoothing of explanations

Question

Can someone help me break down the exact execution order for future versions of anti-aliasing? I am using Racket.

version 1, from the racket itself, and the second version is 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), do:

 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) 

and the second produces:

 l = (1 2 3) l = 1 l = (2 3) l = 2 l = (3) l = 3 l = () '(1 2 3) 

The execution order seems different. In the first example, it looks like the second cycle (loop (cdr l) acc) starts before the first cycle, because "(2 3) prints immediately. While in the second example, 1 fingerprint before '(2 3) is evaluated first, which , as the first smoothing call inside the append, is evaluated first.

I am experiencing Little Schemer, but these are more complex examples that I could really use.

Thank you very much.

Answer 1

The main difference is as follows:

• flatten1 works by storing the output elements (first from the cdr side, then from the car side) into the battery. This works because lists are created from right to left, so working with the cdr side is correct.
• flatten2 works by recursively aligning the sides of car and cdr , then append them together.

flatten1 runs faster, especially if the tree is heavy on the car side: using the battery means there is no extra copying the list, no matter what. Whereas calling append in flatten2 causes the left side of the append be copied, which means many extra copies of the list if the tree is heavy on the car side.

So, I would consider flatten2 beginner implementation of flatten and flatten1 more polished professional version. See also my flatten implementation , which works on the same principles as flatten1 , but uses the left key instead of the right addition used by flatten1 .

(The left-edge solution uses less stack space, but potentially more heap space. The correct solution uses more stack and usually less heap, although a quick read of flatten1 suggests in this case that using the heap is about the same as my implementation.)

Answer 2

Not quite the answer to your question (Chris gave an excellent answer already!), But for completeness, here is another way to implement flatten , similar to flatten2 , but a bit more concise:

 (define (atom? x) (and (not (null? x)) (not (pair? x)))) (define (flatten lst) (if (atom? lst) (list lst) (apply append (map flatten lst)))) 

And one more way to implement the left-folding version (with a more general one for flatten1 ) using standard Racket procedures:

 (define (flatten lst) (define (loop lst acc) (if (atom? lst) (cons lst acc) (foldl loop acc lst))) (reverse (loop lst '())))