`(mcons(m)'()25)16)`和`(mcons 25(mcons 16`()))之间有什么区别？

Question

我正忙于计算机程序的结构和解释练习2.18.在这里,我们必须定义一个反向过程以反转列表.它应该做到以下几点:

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

Answer 1

简短回答:第一个版本reverse错误地构建了一个不正确的列表,第二个版本无法有效地构建一个正确的列表.只要我们明白之间的差别,我们可以做的更好append和cons.

append连接两个列表.如果我们使用它只是在一个列表的末尾添加一个元素,我们将完成比需要更多的工作:我们必须每次遍历整个列表只是为了放置最后一个元素(参见:Schlemiel Painter的算法).因此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单元格是可变的)因为您正在使用的语言,请尝试切换到默认情况下#lang racket使用不可变 cons单元格,并将按预期打印.