球拍/方案展平说明 [英] Racket/Scheme Flatten Explanations

问题描述

有人可以帮我准确分解以下版本的flatten的执行顺序吗?我正在使用球拍.

Can someone help me to break down exactly the order of execution for the following versions of flatten? I'm using Racket.

版本1是来自球拍本身，而版本2是更常见?实施.

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

现在，使用'(1 2 3)运行第一个示例将产生:

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)

而第二个产生:

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

执行顺序似乎有所不同.在第一个示例中，由于'(2 3)立即打印，因此看起来第二个循环(loop (cdr l) acc)在第一个循环之前触发.而在第二个示例中，1在'(2 3)之前打印，这似乎是首先评估了在append内部进行扁平化的第一次调用.

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.

我正在研究Little Schemer，但是这些是更困难的示例，我确实可以在其中使用一些帮助.

I'm going through the Little Schemer but these are more difficult examples that I could really use some help on.

非常感谢.

推荐答案

主要区别在于:

• flatten1通过将输出元素(首先从cdr端，然后从car端)存储到累加器中来工作.之所以可行，是因为列表是从右到左构建的，因此首先在cdr一侧工作是正确的.
• flatten2的工作方式是递归地展平car和cdr边，然后append将它们在一起.

• 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更快，尤其是如果树在car端很重的情况下:使用累加器意味着无论如何都没有多余的列表复制.而flatten2中的append调用将导致append的左侧被复制，这意味着如果树在car侧较重，则将进行大量额外的列表复制.

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.

因此，总而言之，我将考虑flatten2是flatten的初学者实现，而flatten1是更精练的专业版本.另请参见我的展平实现，其使用与flatten1相同的原理，但使用左折而不是flatten1使用的右折.

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.

(左折解决方案使用较少的堆栈空间，但可能会使用更多的堆空间.右折解决方案使用更多的堆栈，通常使用较少的堆，尽管快速阅读flatten1表示在这种情况下堆的使用量约为与我的实现相同.)

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

这篇关于球拍/方案展平说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！