帮助解释Scheme中的"cons"如何工作？

Question

这是删除列表最后一个元素的函数.

(define (remove-last ll)
  (if (null? (cdr ll))
      '()
      (cons (car ll) (remove-last (cdr ll)))))

所以根据我的理解,如果我们cons是一个列表(例如,a b c有一个空列表,即'()我们应该得到 a b c.但是,在交互窗口(DrScheme)中测试,结果是:

如果(cons'()'(abc))

(() a b c)

如果(cons'(abc)'())

((a b c))

我喜欢哎呀:(然后我回到我的问题,删除所有相邻重复的元素.例如, (a b a a c c)将是(a b).

(define (remove-dup lst)
  (cond ((null? lst) '())
        ((null? (cdr lst)) (car lst))
        ((equal? (car lst) (car (cdr lst))) (remove-dup (cdr (cdr lst))))
        (else (cons (car lst) (car (cdr lst))))
        )

  )

这不正确,但我意识到答案.之间有一个a b.怎么会发生这种情况？

`(a . b)`

在cons上面的代码中只有一个调用,我无法看到哪个部分可以生成这个..任何的想法？

谢谢,

Answer 1

cons构建对,而不是列表.Lisp解释器使用"点"来直观地分离对中的元素.所以(cons 1 2)将打印(1 . 2).car并cdr分别返回一对的第一和第二元素.列表建立在对之上.如果cdr一对指向另一对,则将该序列视为列表.在cdr最后一对将指向所谓的特殊对象null(表示为'()),这告诉它已经达到了列表的末尾解释.例如,'(a b c)通过计算以下表达式来构建列表:

> (cons 'a (cons 'b (cons 'c '())))
(a b c)

该list过程提供了创建列表的快捷方式:

> (list 'a 'b c)
(a b c)

表达式(cons '(a b c) ())创建一对,其第一个元素是列表.

您的remove-dup程序正在该else条款中创建一对.相反,它应该通过递归调用remove-dup并将结果作为对的第二个元素来创建列表.我已经清理了一下程序:

(define (remove-dup lst)
  (if (>= (length lst) 2)
      (if (eq? (car lst) (cadr lst))
          (cons (car lst) (remove-dup (cddr lst)))
          (cons (car lst) (remove-dup (cdr lst))))
      lst))

测试:

> (remove-dup '(a b c))
(a b c)
> (remove-dup '(a a b c))
(a b c)
> (remove-dup '(a a b b c c))
(a b c)

另请参见SICP中的 2.2节(分层数据和关闭属性).

为了完整性,这里有一个版本remove-dup删除所有相同的相邻元素:

(define (remove-dup lst)
  (if (>= (length lst) 2)
      (let loop ((f (car lst)) (r (cdr lst)))
        (cond ((and (not (null? r))(eq? f (car r)))
               (loop f (cdr r)))               
              (else
               (cons (car lst) (remove-dup r)))))
      lst))