帮忙解释一下Scheme中的“cons”是如何工作的？

Question

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

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

因此，根据我的理解，如果我们cons一个列表（例如ab c与一个空列表，即'()，我们应该得到 ab c。然而，在交互窗口（DrScheme）中进行测试，结果是：

If (cons '() '(abc))

(() a b c)

If (cons '(abc) '())

((a b c))

我想搞什么:(！ 然后我回到我的问题，删除所有具有相邻重复项的元素。例如， (abaacc) 将是 (ab)。

(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 的特殊对象（由 '() 表示），这告诉解释器它有到达列表末尾。例如，列表 '(abc) 是通过计算以下表达式来构造的：

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

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

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

表达式 (cons '( abc) '()) 创建一个第一个元素是列表的对。

您的 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。

为了完整起见，这里有一个 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))

Answer 2

这里是伪代码：

class Pair {
物体离开，
对象正确}。

function cons(Object left, Object right) {return new Pair(left, right)};

所以，
1. cons('A,'B) =>;对('A,'B)
2. cons('A,NIL) =>;对('A,NIL)
3. cons(NIL,'A) =>;对(NIL,'A)
4. cons('A,cons('B,NIL)) =>对（'A，对（'B，NIL））
5. cons(cons('A 'B),NIL)) => Pair(Pair('A,'B),NIL)

让我们看看所有情况下的左和右：
1. 'A 和 'B 是原子，整个 Pair 不是一个列表，所以 (const 'a 'b) 在方案中给出 (a . b)
2. NIL 是一个空列表，'A 是一个原子，(cons 'a '()) 给出列表 (a)
3. NIL 和 'A 如上，但左边是 list(!)，(cons '() 'a) 给出对 (() . a)
4. 简单的情况，我们这里有正确的列表（ab）。
5. 正确的列表，头部是对（a.b），尾部是空的。

希望，你明白了。

关于你的职能。您正在处理“列表”，但构建“对”。
列表是成对的，但并非所有对都是列表！要成为列表对，必须以 NIL 作为尾部。

(ab) 配对 &列表
(a . b) 对未列出

尽管有缺点，但您的函数有错误，它只是不适用于 '(abaaccd)。由于这与您的问题无关，我不会在这里发布修复程序。