recursion - 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
" 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
" 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

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 '())))