1

我正忙于计算机程序的结构和解释练习 2.18。在这里，我们必须定义一个过程 reverse 来反转一个列表。它应该执行以下操作：

(reverse (list 1 4 9 16 25))
;; => (25 16 9 4 1)

我提出了以下定义：

(define (reverse list)
  (if (null? list) 
      list
      (cons (reverse (cdr list)) (car list))))
;; => (mcons (mcons (mcons (mcons (mcons '() 25) 16) 9) 4) 1).

然后在一个解决方案中发现类似如下：

(define (reverse items) 
  (if (null? (cdr items)) 
      items 
      (append (reverse (cdr items)) 
              (cons (car items) nil))))
;; => (mcons 25 (mcons 16 (mcons 9 (mcons 4 (mcons 1 '()))))).

append和这里有区别cons，我不能指手画脚。

我的问题：有什么区别，为什么结果不显示为(25 16 9 4 1)？

4

1 回答 1

5

简短的回答：第一个版本reverse错误地构建了一个不正确的列表，第二个版本低效地构建了一个正确的列表。只要我们了解 和 之间的区别，我们就可以append做得更好cons。

append连接两个列表。如果我们用它来在一个列表的末尾添加一个元素，我们将做比需要更多的工作：我们每次都必须遍历整个列表才能放入最后一个元素（参见：Schlemiel画家算法）。因此reverse，使用的实现可能与复杂性append一样糟糕O(n^2)。

另一方面，cons将单个元素添加到列表的头部，以O(n)实现reverse. 一般来说，在Scheme中你应该尽量避免使用append来构建一个新的输出列表，总是更喜欢cons. 现在让我们看看你的算法返回了什么cons：

(reverse '(1 2 3 4 5))
=> '(((((() . 5) . 4) . 3) . 2) . 1)

这是为什么？因为要使用第二个参数构建正确的列表cons必须是另一个正确的列表，但是您传递的是单个元素。正确的实现需要一个累加器参数——顺便说一句，这更有效，因为它使用尾递归，你应该已经熟悉这个概念，正如本书第 1.2 节中介绍的那样。试试这个：

(define (reverse lst acc)
  (if (null? lst)
      acc
      (reverse (cdr lst) (cons (car lst) acc))))

(reverse '(1 2 3 4 5) '())
=> '(5 4 3 2 1)

对于问题的最后一部分：由于您使用的语言，列表正在显示mcons（m意味着cons单元格是mutable#lang racket ），请尝试切换到默认情况下使用不可变 cons单元格的列表，并将按预期打印.

于 2015-01-17T23:21:26.440 回答