recursion - Racket /方案展平说明

Question

有人可以帮我准确分解以下版本的 flatten 的执行顺序吗？我正在使用 Racket 。

版本 1，来自 Racket 本身，而版本 2 是更常见的？执行。

(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) 之前打印，这似乎首先评估了在 append 内部对 flatten 的第一次调用。

我正在阅读 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))))

以及使用标准 Racket 程序实现左折叠版本的另一种方法(与 flatten1 有更多共同点):

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