SICP. Списки

В прошлых статьях мы работали с парами: создавали пары, писали через них библиотеку обыкновенных дробей и библиотеку интервалов. Теперь усложняемся: будем строить иерархические типы данных на основе пар.

Строить иерархические объекты можно благодаря абстрактной алгебре. Мы писали статью про области видимости и замыкание, но там мы имели в виду программистское замыкание, а сейчас математическое.

Математическое замыкание, это когда множество замкнуто относительно операции и при использовании элементов множества операцией, получается новый элемент множества. Объясняем на томатах: есть 5 грядок разных видов томатов на одном участке. Участок — это множество, грядки — подмножество, а кусты томатов — элементы. Делаем операцию по пересадке: берём по одному кусту и высаживаем шестую грядку. Множества разрослись за счёт элементов этого же множества.

Списки

Мы пропустим момент с созданием библиотеки для списков и возьмём уже готовые скимовские библиотеки, весь код можно проверять на реплите, в этой статье весь код на скиме.

Чтобы создать список нужно написать ключевое слово list и последовательность элементов, которая будет в нём храниться

(list 2 3 4 5 6 7) ; => (2 3 4 5 6 7)

Для списков тоже работает car и cdr, только немного по-другому:

  • car — возвращает первый элемент списка, обычно его называют хэд или же голова
  • cdr — возвращает все кроме первого, их называют тэил или же хвост

Есть ещё несколько базовых операций, но мы их напишем сами чтобы лучше понять устройство списков, сделаем три: получение элемента по индексу, вычисление длины и склеивание двух списков.

Получаем элемент по индексу

Чтобы достать что-то из списка нужен сам список и номер этого чего-то. Это аргументы, теперь продумываем алгоритм:

  1. Если индекс = 0, то возвращаем первое значение в списке
  2. Если нет, то вызываем функцию снова с хвостом списка и индексом − 1
В других языках можно выбрать только последний элемент, но не в скиме

Вычисляем длину

Здесь нужна встроенная функция null?, она определяет пустой список или нет.

Будем проверять по одному элементу и прибавлять к счётчику 1 за каждый новый шаг. За самым последним элементом остаётся пустое пространство, на нём null? и сработает:

  1. Если список пустой, то возвращаем 0
  2. Если не пустой, то прибавляем 1 и вызываем функцию снова с хвостом списка
Сначала функция создаст цепочку отложенных операций, потом вычислит её и получит значение 3

Склеиваем два списка

Разделяем первый список на элементы и приклеиваем по одному элементу ко второму списку. Вытаскивать из первого списка будем командой car. Получится список наоборот, но из-за свёртки рекурсивных вызовов на выходе получится красиво.

Если бы рекурсивные вызовы сворачивались в прямом порядке, всё было бы плохо: (2 4 8) + (16 32 64) = (8 4 2 16 32 64)
Но рекурсия сворачивается в обратном порядке и всё встаёт нормально: (2 4 8) + (16 32 64) = (2 4 8 16 32 64)

Получается такой алгоритм:

  1. Если первый список пустой, то возвращаем второй список
  2. Если второй список не пустой, то собираем пару
Функция создаёт цепочку отложенных операций, потом ко второму списку по одному начинают приклеиваться элементы первого

Тестим

Соберём и проверим наши функции в одном файлике. К слову, тут у нас абстракция чёрным ящиком, потому что мы не знаем как работают функции list, car и cdr внутри.

Поделиться
Отправить
Запинить
 18   1 мес   sicp
Популярное