了解深度逆向

Question

假设我有一个列表 '(1 2 3 (4 5 6) 7 8 9)。使用以下代码应返回 (9 8 7 (6 5 4) 3 2 1)。我试图理解这个迭代过程是如何运作的。展示这是如何一步一步完成的将会非常有帮助。

我最困惑的部分是此时深度反向被调用两次
（附加 （深度反向（cdr lst）） (list (deep-reverse (car lst)))))

我不知道接下来会发生什么。

(define (deep-reverse lst) 
   (cond ((null? lst) '() ) 
         ((pair? (car lst)) 
          (append 
           (deep-reverse (cdr lst)) 
           (list (deep-reverse (car lst))))) 
         (else 
          (append 
           (deep-reverse (cdr lst)) 
           (list (car lst)))))) 

Answer 1

好吧，我刚刚回答了这样的问题

发生的情况是，它会反转恰好是列表的每个项目，然后将其附加到列表末尾。想象一下，如果它没有对列表中的汽车调用 deep-reverse 会发生什么： (reverse '(a (bcd) e) is

(list
   'e
   '(b c d)
   'a
)

With deep-reverse it's won't like

(list
    'e
    (deep-reverse '(b c d))
    'a
)

Which is

(list
    'e
    '(d c b)
    'a
)

Here是深度反向的另一个版本，写法不同，如果这样更清楚的话，

(define (deep-reverse ls)
  (define (deep-reverse-2 ls acc)
    (if (null? ls)
        acc
        (if (list? (car ls))
            (deep-reverse-2 (cdr ls) (cons (deep-reverse (car ls)) acc));  If adding  a list, reverse it first
            (deep-reverse-2 (cdr ls) (cons (car ls) acc)))))
  (deep-reverse-2 ls '()))

这个版本的深度复制使用累加器并且是尾递归的，

它在将元素添加到列表之前检查它是否是一个列表，如果是。是的，首先将其反转。由于它调用自身来反转内部列表，

(deep-reverse '(a (b c d) e)) -> '(e (d c b) a)

因此它可以处理按相反字母顺序排列的任意嵌套，尽管它的计算结果如下：

(deep-reverse-2 '(a (b c d) e) '()); Which calls
(deep-reverse-2 '((b c d) e)  '(a)); which is the same as
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(b c d) '()) '(a))); it calls deep-reverse on the list '(b c d) before consing it on.
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(c d)  '(b)) '(a)))
(deep-reverse-2 '(e) (cons (deep-reverse-2 '(d)  '(c b)) '(a)))
(deep-reverse-2 '(e) (cons '(d c b) '(a)))
(deep-reverse-2 '(e)  '((d c b) a))
(deep-reverse-2 '() '(e (d c b) a))
'(e (d c b) a)

Answer 2

很简单，您不知道头是整数还是列表，因此您还必须对其应用deep-reverse，然后将其附加到当前列表的反向尾部。

所以：

((1 2) 3 4)

必须变成

(4 3 (2 1))

注意我们如何必须颠倒头部和尾部。