3.3.1 · Изменяемая структура списков

Мутация cdr и пути, ведущие к паре

Деструктивное присоединение, псевдонимы в общем хвосте, цикл в структуре и подсчет уникальных пар без бесконечного обхода одного объекта.

Вопрос для размышления

Как изменение и идентичность меняют смысл привычных операций со списками, таких как append и обход?

Поиск последней пары правильного изменяемого списка
Реализация append! через изменение одного существующего cdr
Наблюдение за тем, что псевдоним правого списка остается разделяемым в результате
Создание конечного цикла без попытки напечатать его как правильный список
Подсчет уникальных пар с помощью явного множества просмотренных объектов

Процедура append! не перестраивает левый список. Она находит последнюю пару и изменяет cdr этой пары так, чтобы он указывал на right. Исходное имя left теперь видит объединенную цепочку, тогда как right все еще именует разделяемый хвост, начинающийся с c. Результат eq? напрямую раскрывает это отношение идентичности.

Пример с циклом изменяет последний cdr так, чтобы он указывал обратно на первую пару. Обычный рекурсивный обход списка никогда не достигнет пустого списка. Поэтому count-unique-pairs записывает идентичность каждой пары перед спуском и прибавляет ноль, когда memq находит уже просмотренную пару. Программа сообщает о цикле через eq?, не требуя от принтера бесконечного развертывания.

Код SICP358 из 1,048,576 байт UTF-8

(begin
  (define (last-pair items)
    (if (null? (cdr items))
        items
        (last-pair (cdr items))))
  (define (append! left right)
    (set-cdr! (last-pair left) right)
    left)
  (define left (list 'a 'b))
  (define right (list 'c 'd))
  (define combined (append! left right))
  (list combined
        right
        (eq? (cddr combined) right)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Программа с деструктивным append возвращает ((a b c d) (c d) #t). Программа с циклом возвращает (3 #t).

На что обратить внимание в трассе

Найдите единственный вызов set-cdr!, который соединяет пару b с right, затем сравните все три имени, ведущие к разделяемому хвосту. При запуске с циклом найдите последнюю связь обратно к первой паре и каждое срабатывание memq, предотвращающее повторный спуск.

Попробуйте сами

Измените программу и сравните результат.

Постройте два списка, которые разделяют только свою последнюю пару, затем подсчитайте уникальные пары в структуре, содержащей оба списка. Сравните этот результат с наивным рекурсивным подсчетом пар.

Показать подсказку

Записывайте идентичность пар перед обходом car и cdr. Одинаковое печатное содержимое не означает единое общее выделение памяти.

Завершить этот урок

В этой главе пройдено 0 из 21 урока0%