SICP -练习2.27 -颠倒列表和子列表的要素

Question

来自SICP

练习2.27:修改练习2.18的深度反转过程，生成一个以列表作为参数并返回其值的深-深-反向过程，并返回其元素深反转的列表，以及所有深-深-反的子列表。例如，(定义x(列表(列表12)(列表3 4)) x((12) (3 4) )(深反向x) ((3 4) (1 2)) (深深反向x) ((4 3) (2 1))

请检查我的密码。

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

我花了一个小时来做这件事，实际上我对这段代码到底有多小感到非常惊讶。如何改进这段代码？也许能让它更快？

Answer 1

如果您实际上是这样缩进的，请使用一个自动的编辑器--通常cond的个别情况应该对齐，例如：

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

功能看起来不错。为了清晰起见，将中间的情况移到末尾也许是有意义的，但这并没有多大变化。

但是，考虑到以这种方式使用的append相当昂贵，因为它反复重新创建一个“长”列表(来自cdr递归)，以便将“短”列表(来自car部分)放在末尾。

(作为读者的练习)，您可以使用累加器来完全避免append (而cons就足够了)。这个函数看起来非常相似：

(define (deep-deep-reverse2 lst)
  (define (aux lst acc)
    ...)
  (aux lst '()))

Answer 2

如前所述，追加的开销很大，时间和内存约束行与第一个参数的大小相同。实际上，当输入是列表列表的列表时，在列表的每个cdr上重复出现的函数使得整个函数n^2。

要记住的另一件事是那份名单？也需要时间线性时间来完成。(导致另一个n^2时间约束。)另外一对？在固定时间内运行，但不保护/保护不受正确列表的影响。(然而，当您担心输入不当时，您应该继续在函数开始时检查它。)

您也可以通过在列表上折叠cons来反转列表。

(define (deep-deep-reverse3 x)
    (fold (lambda (x acc) 
            (cons (if (pair? x)
                      (deep-deep-reverse3 x)
                      x)
                  acc))
          '()
           x))