Краткий ответ: первая версия reverse неправильно строит неправильный список, вторая версия неэффективно строит правильный список. Мы можем работать лучше, если понимаем разницу между append и cons.
append объединяет два списка. Если мы будем использовать его для простого добавления элемента в конец одного списка, мы будем делать гораздо больше работы, чем нужно: нам придется проходить весь список каждый раз, чтобы поместить последний элемент (см.: алгоритм Шлемиэля-художника). Следовательно, реализация reverse, использующая append, может быть настолько же плохой, как O(n^2) по сложности.
С другой стороны, cons добавляет один элемент в начало списка для O(n) сложности реализации reverse. В общем, в Scheme вы должны стараться избегать использования 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, который использует < em>неизменяемые cons ячейки по умолчанию и будут напечатаны так, как вы ожидаете.
person
Óscar López
schedule
17.01.2015
