3.3.3 · Представление изменяемых таблиц

Изменяемая таблица за lookup и insert!

Ассоциативный список за lookup и insert! меняет запись на месте, привязывает новую к таблице и вводит вложенную подтаблицу по второму ключу.

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

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

Использование assoc для поиска изменяемой записи за заголовком таблицы
Обновление существующей записи с помощью set-cdr!
Вставка новой записи путем изменения хвоста таблицы
Представление таблицы с двумя ключами в виде подтаблиц, содержащих записи
Различение неудачного поиска и сохраненного значения

Таблица с одним ключом представляет собой изменяемый список, первым элементом которого является закрытый заголовок. lookup ищет только среди записей после этого заголовка. insert! изменяет cdr существующей пары ключ-значение при наличии ключа, в противном случае она изменяет пару заголовка таблицы, так что новая запись становится частью ассоциативного списка. Клиентский код не зависит от порядка вставки или расположения пар.

Таблица с двумя ключами хранит запись первого ключа, чей cdr сам является ассоциативным списком. Вставка нового второго ключа изменяет эту подтаблицу, тогда как новый первый ключ связывает целую подтаблицу с внешней таблицей. Обновление arithmetic с 10 до 11 изменяет существующую самую глубоко вложенную запись вместо создания дубликата. В этих примерах #f используется в качестве результата отсутствия значения, поэтому сохранение #f потребовало бы более богатого протокола lookup.

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

(begin
  (define (make-table) (list '*table*))
  (define (lookup key table)
    (let ((record (assoc key (cdr table))))
      (if record (cdr record) #f)))
  (define (insert! key value table)
    (let ((record (assoc key (cdr table))))
      (if record
          (set-cdr! record value)
          (set-cdr! table
                    (cons (cons key value)
                          (cdr table)))))
    'ok)
  (define table (make-table))
  (insert! 'alpha 4 table)
  (insert! 'beta 5 table)
  (insert! 'alpha 9 table)
  (list (lookup 'alpha table)
        (lookup 'beta table)
        (lookup 'gamma table)
        table))

Примеры

Результат—

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

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

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

Первая программа возвращает (9 5 #f (*table* (beta . 5) (alpha . 9))). Вторая программа возвращает (11 20 30 #f (*table* (language (scheme . 30)) (math (algebra . 20) (arithmetic . 11)))).

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

Сравните обходы assoc, которые находят alpha, с обходом gamma, достигающим конца. Отличите set-cdr! для существующей записи от set-cdr! для заголовка таблицы или подтаблицы, который связывает новую запись. Во вложенном запуске проследите за внешним ключом перед внутренним ключом и убедитесь, что обновление arithmetic изменяет одну существующую пару.

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

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

Добавьте physics в math, обновите scheme до 31 и добавьте вторую запись language. Предскажите порядок внешних и внутренних записей перед запуском, затем объясните, какие обновления изменяют записи, а какие изменяют хвосты таблиц.

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

Присутствующий ключ изменяет cdr своей записи. Отсутствующий ключ создает новую пару и связывает ее в начале соответствующего ассоциативного списка.

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

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