帮助解释 Scheme 中的 `cons` 如何工作? [英] Help explaining how `cons` in Scheme work?

问题描述

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

This is the function that removes the last element of the list.

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

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

So from my understanding if we cons a list (eg. a b c with an empty list, i.e. '(), we should get a b c. However, testing in interaction windows (DrScheme), the result was:

如果 (cons '() '(a b c))

If (cons '() '(a b c))

(() a b c)

如果 (cons '(a b c) '())

If (cons '(a b c) '())

((a b c))

我喜欢什么:(！然后我回到我的问题，删除所有具有相邻重复项的元素.例如，(a b a c c) 将是 (a b).

I'm like what the heck :(! Then I came back to my problem, remove all elements which have adjacent duplicate. For example, (a b a a c c) would be (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 之间有一个 ..怎么会这样?

It was not correct, however I realize the answer have a . between a b. How could this happen?

`(a . b)`

在我上面的代码中只有一个对 cons 的调用，我看不出哪个部分可以生成这个 ..有什么想法吗?

There was only one call to cons in my code above, I couldn't see which part could generate this .. Any idea?

谢谢，

推荐答案

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

cons build pairs, not lists. Lisp interpreters uses a 'dot' to visually separate the elements in the pair. So (cons 1 2) will print (1 . 2). car and cdr respectively return the first and second elements of a pair. Lists are built on top of pairs. If the cdr of a pair points to another pair, that sequence is treated as a list. The cdr of the last pair will point to a special object called null (represented by '()) and this tells the interpreter that it has reached the end of the list. For example, the list '(a b c) is constructed by evaluating the following expression:

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

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

The list procedure provides a shortcut for creating lists:

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

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

The expression (cons '(a b c) '()) creates a pair whose first element is a list.

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

Your remove-dup procedure is creating a pair at the else clause. Instead, it should create a list by recursively calling remove-dup and putting the result as the second element of the pair. I have cleaned up the procedure a bit:

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

另请参阅 中的第 2.2 节(分层数据和闭包属性)SICP.

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

For completeness, here is a version of remove-dup that removes all identical adjacent elements:

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

这篇关于帮助解释 Scheme 中的 `cons` 如何工作?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！