scheme - 帮助解释 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)中测试，结果是:

如果(缺点'()'(a b c))

(() a b c)

如果 (缺点 '(a b c) '())

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