"(mcons (mcons '() 25) 16)' 和 '(mcons 25 (mcons 16 '()))' 有什么区别

  • 本文关键字:mcons 区别 scheme racket sicp cons cdr
  • 更新时间 :
  • 英文 :


我正忙于计算机程序的结构和解释练习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).

然后在解决方案中 In 发现类似的东西如下:

(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 '()))))).

appendcons之间是有区别的,我无法把手指放在上面。

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

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

append连接两个列表。如果我们只使用它在一个列表的末尾添加一个元素,我们将做比需要的更多的工作:我们每次都必须遍历整个列表,只是为了放置最后一个元素(参见:画家施莱米尔算法)。因此,使用appendreverse实现可能与复杂性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)

对于问题的最后一部分:由于您使用的语言,列表显示为mconsm表示cons单元格是可变的),请尝试切换到 #lang racket ,默认情况下使用不可变cons单元格,并将按预期打印。

相关内容

  • 没有找到相关文章

最新更新