В чем разница между `(mcons (mcons '() 25) 16)` и `(mcons 25 (mcons 16 `()))`

Question

Я занимаюсь структурой и интерпретацией компьютерных программ упражнение 2.18. Здесь мы должны определить процедуру, обратную к списку. Следует сделать следующее:

(reverse (list 1 4 9 16 25))
;; => (25 16 9 4 1)

Я придумал следующее определение:

(define (reverse list)
  (if (null? list) 
      list
      (cons (reverse (cdr list)) (car list))))
;; => (mcons (mcons (mcons (mcons (mcons '() 25) 16) 9) 4) 1).

Затем в решении В нашли что-то похожее следующим образом:

(define (reverse items) 
  (if (null? (cdr items)) 
      items 
      (append (reverse (cdr items)) 
              (cons (car items) nil))))
;; => (mcons 25 (mcons 16 (mcons 9 (mcons 4 (mcons 1 '()))))).

Есть разница между append а также cons здесь, где я не могу положить палец

Мой вопрос: в чем разница и почему результаты не отображаются как (25 16 9 4 1)?

Answer 1

Краткий ответ: первая версия reverse неправильно создает неправильный список, вторая версия неэффективно создает правильный список. Мы можем добиться большего успеха, если понимаем разницу между append а также cons,

append объединяет два списка. Если мы используем его для простого добавления элемента в конец одного списка, мы будем выполнять гораздо больше работы, чем необходимо: нам придется обходить весь список каждый раз, чтобы поместить один последний элемент (см.: Schlemiel алгоритм художника). Отсюда reverse реализация, которая использует append может быть так же плохо, как O(n^2) в сложности.

С другой стороны, cons добавляет один элемент в начало списка, для O(n) сложность в реализации reverse, В целом, в Схеме следует избегать использования append чтобы создать новый список вывода, всегда предпочитайте cons, Теперь давайте посмотрим, что возвращает ваш алгоритм, используя cons:

(reverse '(1 2 3 4 5))
=> '(((((() . 5) . 4) . 3) . 2) . 1)

Это почему? потому что построить правильный список с cons второй аргумент должен быть другим правильным списком, но вы передаете один элемент. Для правильной реализации требуется параметр аккумулятора - и, между прочим, это более эффективно, поскольку в нем используется хвостовая рекурсия, концепция, с которой вы уже должны быть знакомы, как это было представлено в разделе 1.2 книги. Попробуй это:

(define (reverse lst acc)
  (if (null? lst)
      acc
      (reverse (cdr lst) (cons (car lst) acc))))

(reverse '(1 2 3 4 5) '())
=> '(5 4 3 2 1)

Для последней части вопроса: список отображается с mcons (m означает, что cons изменяемые ячейки) из-за языка, который вы используете, попробуйте переключиться на #lang racket, который использует неизменяемый cons ячейки по умолчанию, и будут напечатаны, как вы ожидаете.