Что такое добавление двух списков, как это, возвращает один список, а не ячейку cons из двух списков?

Обычный и простой способ добавления двух списков выглядит следующим образом:

(define (append a b)
  (if (null? a)
      b
      (cons (car a) (append (cdr a) b))))

Почему это работает? Когда мы достигнем последнего элемента a, мое явно неверное мнение состоит в том, что мы будем вызывать (cons [the original list a, built out of many calls to (cons (car a) ...)] [the original list b]). Короче говоря, я не понимаю, почему функция не возвращает (cons a b), которая была бы ячейкой cons, содержащей два списка. Даже если я ошибаюсь насчет части a, почему допустимо добавлять b к нашему выводу в виде целого списка, не разбивая его сначала на отдельные элементы?

Я подозреваю, что рабочий пример будет иметь большое значение для ответа.


list append lisp scheme cons
person J. Mini    schedule 23.01.2021    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Нигде a не сводится к b. Вместо этого элементы a преобразуются в b, начиная с последнего элемента a. Рассмотреть возможность:

(append '() '(1 2 3))
--> '(1 2 3)  ; there are no elements in `a` to cons onto `b`

(append '(y) '(1 2 3))
--> (cons (car '(y)) (append (cdr '(y)) '(1 2 3)))
--> (cons 'y (append '() '(1 2 3)))
--> (cons 'y '(1 2 3))  ; the last element of `a` is consed onto `b`
--> '(y 1 2 3)

(append '(x y) '(1 2 3))
--> (cons (car '(x y)) (append (cdr '(x y)) '(1 2 3)))
--> (cons 'x (append '(y) '(1 2 3)))
--> (cons 'x (cons (car '(y)) (append (cdr '(y)) '(1 2 3))))
--> (cons 'x (cons 'y (append '() '(1 2 3))))
--> (cons 'x (cons 'y '(1 2 3)))  ; the last element of `a` is consed onto `b`
--> (cons 'x '(y 1 2 3))  ; then the next-to-last element of `a`, and so on
--> '(x y 1 2 3)
person ad absurdum    schedule 23.01.2021
comment
Ты был умнее, чем когда-либо должен был быть. Моя ошибка заключалась в том, что я не понял, что (cons [any singleton] [any list]), очевидно, сам по себе является списком. - person J. Mini; 24.01.2021