Помогите объяснить, как работают `cons` в Scheme?

Это функция, которая удаляет последний элемент списка.

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

Итак, из моего понимания, если мы cons список (например. a b c с пустым списком, т.е. '(), мы должны получить a b c. Однако при тестировании в окнах взаимодействия (DrScheme) результатом был:

Если (cons '()' (a b c))

(() a b c)

Если (cons '(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, я не мог видеть, какая часть может сгенерировать этот .. Любая идея?

Спасибо,

Ответ 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)

Также см. раздел 2.2 (Иерархические данные и свойство закрытия) в 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))

Ответ 2

Здесь в псевдокоде:

класс Pair { Объект слева, Правка объекта}.

function cons (Object left, Object right) {return new Pair (слева, справа)};

Итак, 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, Pair (' B, NIL)) 5. минус (минус ('A' B), NIL)) = > Пара (пара ('A,' B), NIL)

Посмотрите слева и права во всех случаях: 1. "A" и "B" являются атомами, а целая пара не является списком, поэтому (const 'a' b) дает (a. B) в схеме 2. NIL - пустой список, а "A - атом" (cons "a" ()) дает список (a) 3. NIL и "A", как указано выше, но поскольку слева список (!), (Cons '()' a) дает пару ((). A) 4. Простой случай, у нас есть правильный список здесь (a b). 5. Правильный список, голова - пара (a. B), хвост пуст.

Надеюсь, у вас появилась идея.

Относительно вашей функции. Вы работаете над LIST, но создаете PAIRS. Списки представляют собой пары (пар), но не все пары являются списками! Для того, чтобы быть пар списком, должен иметь NIL как хвост.

(a b) и список (a. b) не список

Несмотря на минус, ваша функция имеет ошибки, она просто не работает на '(a b a a c c d). Поскольку это не связано с вашим вопросом, я не буду публиковать исправление для этого здесь.