Помогите объяснить, как работают "минусы" в Схеме?

Question

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

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

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

If (cons '()' (abc))

(() a b c)

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

Также см. Раздел 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))

Answer 2

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

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

функция cons (Объект слева, Объект справа) {вернуть новую пару (слева, справа)};

Итак, 1. минусы ('A,' B) => пара ('A,' B) 2. минусы ('A, NIL) => Пара (' A, NIL) 3. минусы (NIL, 'A) => Пара (NIL,' A) 4. cons ('A, cons (' B, NIL)) => Пара ('A, Pair (' B, NIL)) 5. cons (cons ('A' B), NIL)) => Пара (Pair ('A, B), NIL)

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

Надеюсь, у вас есть идея.

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

(б) пара и список (a. b) пара не указана

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