SICP. Иерархические данные

В прошлой статье мы разобрались как создавать списки в скиме и написали три пользовательские абстрактные функции. В этой статье тоже списки, но вложенные и по-абстрактней.

Списки в списках

Иерархические данные могут состоять сами из себя, то есть мы можем сделать список списков, а там ещё список, и ещё, и ещё. Хранить данные в таких структурах просто так нет смысла, но иногда это полезно: кучу чисел можно запихнуть в двоичное дерево чтобы быстрее их искать, связанные друг с другом данные — в граф. Вот такой список со списком, он состоит из 4 элементов: «1 2 3» — просто числа, а («4 5 6») — ещё один список, внутри него лежат обычные числа «4 5 6».

(list 1 2 3 (list 4 5 6))

В статье про Фибоначчи мы говорили, что древовидная рекурсия плохо справляется с вычислениями, но отлично подходит для иерархических объектов. Тут всё сходится, сделаем подсчёт элементов дерева:

  1. Если получаем пустой список, то возвращаем 0
  2. Если получаем число, то возвращаем 1
  3. Если ничего из этого, то возвращаем сумму двух вызовов функции с car и cdr списка

Все чётные числа

В программировании есть такое понятие как последовательная обработка. Это когда несколько функций по очереди делают свои дела. Чтобы показать её на примере, в СИКПе писали функцию для вычисления суммы квадратов чётных чисел дерева. Для наглядности сделали иерархическое дерево, искали, возводили в квадрат все чётные числа, а потом складывали. Алгоритм такой:

  1. Если функция получила пустой список, то возвращает 0
  2. Если функция получила чётное число, то возводит его в квадрат и возвращает
    Если число нечётное, то возвращает 0
  3. Иначе складывает результат вызова функции с car и cdr списка. В цепочке отложенных сложений будут стоять чётные числа и нули, так получается из-за условия во втором шаге.

Пишем код и получается что-то такое

Улучшаем

Пример выше без последовательной обработки, надо исправить.
Из кода понятна схема проверки:

  1. Выбирается элемент дерева
  2. Проверяется на чётность
  3. Если он чётный, то возводится в квадрат
  4. Возведённые числа откладываются в отдельный список

Превращаем эти пункты в отдельные функции:

  1. Перечислитель перебирает и отдаёт элементы дерева
  2. Фильтр собирает новый список из элементов старого по условию
  3. Мап проходится по каждому элементу списка и применяет к нему функцию из аргумента. На выходе получается новый список
  4. Накопитель собирает в себе чётные элементы списка

Пишем эти функции, переписываем код основной функции и проверяем

Функция так же выводит 56, значит мы ничего не сломали. Через последовательную обработку мы сделали код функции sum-even-squares меньше и понятнее, потому что добавили четыре функции accumulate, map, filter, и enumerate-tree.
Их называют стандартными интерфейсами, потому что они не привязаны к конкретным объектам и их можно использовать для других функций и данных, будто они встроены в сам язык программирования.

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