Racket/Scheme Flatten Explanations

Question

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.

Answer 1

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 appending 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.)

Answer 2

Not really an answer to your question (Chris provided an excellent answer already!), but for completeness' sake here's yet 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 another way to implement the left-fold version (with more in common to 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 '())))