球拍/方案展平解释

Question

有人可以帮我打破以下版本的flatten的执行顺序吗？我正在使用Racket.

版本1,是从球拍本身,而第二版是更常见的？实现.

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

现在,用'(1 2 3)运行第一个例子产生:

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)

而第二个产生:

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

执行顺序似乎不同.在第一个例子中,看起来第二个循环(loop (cdr l) acc)在第一个循环之前触发,因为'(2 3)正在立即打印.而在第二个例子中,1在'(2 3)之前打印,这似乎是第一次调试以平展附加内部.

我正在浏览Little Schemer,但这些是我可以真正使用一些帮助的更难的例子.

非常感谢.

Answer 1

不是你的问题的答案(克里斯提供了一个很好的答案!),但为了完整性,这里还有另一种实现方式flatten,类似flatten2但更简洁:

(define (atom? x)
  (and (not (null? x))
       (not (pair? x))))

(define (flatten lst)
  (if (atom? lst)
      (list lst)
      (apply append (map flatten lst))))

另一种flatten1使用标准球拍程序实现左折版本(更常见)的方法:

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