Список как цепочка пар и соглашение
Пары становятся последовательностями, когда программа принимает соглашение о том, что каждый car содержит один элемент, а каждый cdr содержит остаток списка.
Как рекурсивные процедуры следуют форме списка?
- Чтение списка как первого элемента и оставшейся последовательности
- Определение базового случая с пустым списком
- Построение нового списка без мутации входных данных
- Сравнение связного и индексированного доступа к последовательности
length проверяет, осталась ли последовательность. Каждая непустая пара прибавляет единицу и оставляет cdr для подзадачи меньшего размера. Пустой список останавливает рекурсию.
append следует той же форме при перестроении левой последовательности. Последний cdr указывает на правую последовательность, поэтому результат сохраняет порядок обоих входных списков.
Вектор использует соглашение об индексированной последовательности. vector-ref выбирает элемент по позиции, а vector-set! изменяет одну позицию без перестроения всего вектора.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает (4 (a b c d)).
Следите за тем, как cdr сокращает текущую задачу. append создает по одной новой паре на каждый элемент левого входа и затем достигает правого входа. В примере с вектором найдите обновление и последующее чтение по индексу 2. Трасса выполнения точно фиксирует построение списка и мутацию вектора в выбранном запуске.
Измените программу и сравните результат.
Определите reverse с помощью вспомогательной процедуры, накапливающей построенный результат. Проверьте ее на списке (a b c d).
Показать подсказку
Переносите car оставшегося входа в начало аккумулятора.