4

有人可以帮我准确分解以下扁平化版本的执行顺序吗？我正在使用球拍。

版本 1，来自球拍本身，而版本 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，但这些是更难的例子，我真的可以使用一些帮助。

非常感谢。

4

2 回答 2

5

不是你的问题的真正答案（克里斯已经提供了一个很好的答案！），但为了完整起见，这里还有另一种实现方式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 '())))
于 2012-11-25T04:22:29.110 回答
4

主要区别在于：

  • flatten1通过将输出元素（首先从cdr侧面，然后从car侧面）存储到累加器中来工作。这是可行的，因为列表是从右到左构建的，所以cdr首先从侧面工作是正确的。
  • flatten2通过递归地展平carandcdr边，然后将append它们组合在一起来工作。

flatten1更快，尤其是在树很重的情况下car：使用累加器意味着无论如何都没有额外的列表复制。然而，append调用flatten2会导致左侧被复制，这意味着如果树在一侧append很重，则需要大量额外的列表复制。car

所以总而言之，我会考虑flatten2一个初学者的 flatten 实现，以及flatten1一个更精致、更专业的版本。另请参阅我的 flatten 实现，它使用与 相同的原理flatten1，但使用左折叠而不是使用的右折叠flatten1。

（左折叠解决方案使用更少的堆栈空间，但可能使用更多的堆空间。右折叠解决方案使用更多的堆栈，通常使用更少的堆，尽管快速阅读flatten1表明在这种情况下堆使用与我的实现大致相同。 )

于 2012-11-25T03:50:51.367 回答