`(mcons (mcons '() 25) 16)` 和 `(mcons 25 (mcons 16 `()))` 有什么区别
What is the difference between `(mcons (mcons '() 25) 16)` and `(mcons 25 (mcons 16 `()))`
我在忙Structure and Interpretation of Computer Programs exercise 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).
然后在a solution中发现了类似如下的内容：
(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)？
简短回答：reverse 的第一个版本错误地构建了一个 不正确的 列表，第二个版本低效地构建了一个 正确的 [=49] =] 列表。只要弄清楚append和cons.
的区别，我们就能做得更好
append 连接两个 列表 。如果我们只用它在一个列表的末尾添加一个元素，我们将做比需要更多的工作：我们将不得不遍历整个列表每次只是为了放置最后一个元素（参见：Schlemiel the Painter's algorithm）。因此，使用 append 的 reverse 实现在复杂性上可能与 O(n^2) 一样糟糕。
另一方面，cons 将单个元素添加到列表的头部，因为 reverse 的实现复杂度 O(n)。一般来说，在 Scheme 中你应该尽量避免使用 append 来构建一个新的输出列表，总是首选 cons。现在让我们看看你的算法使用 cons:
返回了什么
(reverse '(1 2 3 4 5))
=> '(((((() . 5) . 4) . 3) . 2) . 1)
这是为什么？因为要用 cons 构建一个正确的列表，第二个参数必须是另一个正确的列表，但是你传递的是一个元素。正确的实现需要一个累加器参数——顺便说一句，这样效率更高，因为它使用了尾递归，这个概念你应该已经很熟悉了，因为它在这本书。试试这个：
(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 单元格 可变 ) 由于您使用的语言，请尝试切换到 #lang racket，它默认使用 immutable cons 单元格，并将按您的预期打印.
我在忙Structure and Interpretation of Computer Programs exercise 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).
然后在a solution中发现了类似如下的内容：
(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)？
简短回答：reverse 的第一个版本错误地构建了一个 不正确的 列表，第二个版本低效地构建了一个 正确的 [=49] =] 列表。只要弄清楚append和cons.
append 连接两个 列表 。如果我们只用它在一个列表的末尾添加一个元素，我们将做比需要更多的工作：我们将不得不遍历整个列表每次只是为了放置最后一个元素（参见：Schlemiel the Painter's algorithm）。因此，使用 append 的 reverse 实现在复杂性上可能与 O(n^2) 一样糟糕。
另一方面，cons 将单个元素添加到列表的头部，因为 reverse 的实现复杂度 O(n)。一般来说，在 Scheme 中你应该尽量避免使用 append 来构建一个新的输出列表，总是首选 cons。现在让我们看看你的算法使用 cons:
(reverse '(1 2 3 4 5))
=> '(((((() . 5) . 4) . 3) . 2) . 1)
这是为什么？因为要用 cons 构建一个正确的列表，第二个参数必须是另一个正确的列表，但是你传递的是一个元素。正确的实现需要一个累加器参数——顺便说一句，这样效率更高，因为它使用了尾递归，这个概念你应该已经很熟悉了，因为它在这本书。试试这个：
(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 单元格 可变 ) 由于您使用的语言，请尝试切换到 #lang racket，它默认使用 immutable cons 单元格，并将按您的预期打印.