在方案中附加反向列表

Question

我正在学习 Scheme 并想编写一个递归程序来反转给定列表。

然而，在一个测试用例中，我注意到 a (b c) e -> e (b c) a。

我想要得到的是 a (b c) e -> e (c b) a。

这是我的：

(define (deep-reverse lst)
(if (null? lst)
  '()
  (begin
    (display (car lst))
    (display "\n")
    (if (null? (cdr lst))
        '()
        (append (deep-reverse (cdr lst)) (list (reverse (car lst))))
        ) //End of inner if
))) //End of begin, outer if, define

当我尝试运行带有

的代码时

(deep-reverse '(1 (b c) (a b)))

我得到：

1
(b c)
(a b)
mcdr: contract violation
expected: mpair?
given: 1

问题出在 (list (reverse (car lst)))，尽管在一个孤立的测试用例中它工作正常。这让我相信这个问题可能与追加有关。

提前谢谢你。

编辑： 从 (list (reverse (car lst))) 到 (reverse (list(car lst))) 使代码运行没有错误但不会反转 (a b) 到 (b a).

Answer 1

正如错误消息所解释的那样，您的问题是您正在尝试反转数字。首先，让我们删除程序中一些不必要的条件和调试内容，得到这个更简单的程序。让我们逐步完成这个程序，看看发生了什么：

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

我们从

开始

(deep-reverse '(1 (b c) (a b)))

代入我们得到的参数

(if (null? '(1 (b c) (a b)))
    '()
    (append (deep-reverse (cdr '(1 (b c) (a b))))
            (list (reverse (car '(1 (b c) (a b)))))))

因为条件是#f，这简化为

(append (deep-reverse (cdr '(1 (b c) (a b))))
                (list (reverse (car '(1 (b c) (a b))))))

要计算第一个参数，首先找到 cdr，然后调用 deep-reverse。我将跳过此处的步骤，但您应该能够轻松地测试它是否正常工作。

(append '((b a) (c b)) (list (reverse (car '(1 (b c) (a b))))))

接下来我们评估 car:

(append '((b a) (c b)) (list (reverse 1)))

这里我们看到了问题所在：我们无法反转单个数字！

问题是您的 deep-reverse 应该有两种不同的递归行为：

在数字、符号或其他非列表实体上，不要做任何事情，因为反转数字没有意义
在列表中，深度反转它

您当前的程序无法正确执行此操作的原因有两个：

它只对列表的元素进行浅层反转；也就是说，它不会深度反转 '(((a b) (c d)) ((e f) (g h))) 正确
如果遇到数字或其他非列表，如符号，它将失败

简单的解决方法是添加一个条件，在尝试反转它之前先检查它是否是 pair?。如果它不是 pair?，那么 lst 必须是 nil（我们可以保持原样）或非列表对象（我们也可以保持原样）

(define (deep-reverse lst)
  (if (pair? lst)
      (append (deep-reverse (cdr lst)) (list (deep-reverse (car lst))))
      lst))

最后，我要注意我们在这里使用的模式实际上是 foldr 模式。我们可以用 foldr:

抽象掉这个模式

(define (deep-reverse xs)
  (cond ((pair? xs)
         (foldr (lambda (x y) (append y (list (deep-reverse x)))) '() xs))
        (else xs)))

但我们也注意到这是低效的，因为 append 是一项昂贵的操作。将算法修改为尾递归可以清楚地看出这实际上是一个 foldl:

(define (deep-reverse xs)
  (cond ((pair? xs)
         (foldl (lambda (x y) (cons (deep-reverse x) y)) '() xs))
        (else xs)))

在典型的惯用 Scheme 中，或者如 Will Ness 所指出的那样，这样的函数可能是这样写的，

(define (deep-reverse xs)
  (cond ((pair? xs) (reverse (map deep-reverse xs)))
        (else xs)))

在方案中附加反向列表

Appending reversed list in Scheme

scheme

reverse

functional-programming

list

append