在计划中追加反向列表

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 

当我试图运行与

（深反向“（1（BC）（AB）））

代码

我收到：

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

它是如何这样的功能可能会被写在典型的惯用方案，或由威尔·内斯指出，

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