Чтобы смотреть видео нужно иметь активную платную подписку и вступить в курс. Войти или зарегистрироваться.

Пары и списки

В этом уроке мы реализовали абстрактный тип данных Список на основе ранее пройденных пар. Ключевой особенностью списка является его интерфейс, а именно функции, реализующие такие операции, как "получить голову" (возвращает первый элемент списка), "получить хвост" (возвращает новый список, полученный из исходного списка отсечением у него первого элемента), "добавить новую голову" (добавление элемента в начало списка). И здесь следует обратить внимание на несколько вещей.

Во-первых, не стоит отождествлять между собой пары и списки. Пары в данном случае были использованы как подходящий инструмент для создания списка. Абстрактный список (см. первый абзац) может быть реализован в конкретных структурах данных - в нашем случае это односвязный список. Важной характеристикой этой структуры данных является то, что каждый элемент списка содержит, помимо определённого хранимого значения (числа, строки, даты, адреса, имени и любой другой информации), ссылку на другой такой же (по структуре) элемент. Таким образом, между элементами списка существует связь, и мы можем последовательно "путешествовать" (перемещаться) от текущего элемента к следующему, от начала списка к его концу.

И, как видим, пары вполне позволяют реализовать особенности списка как структуры данных. Ведь пара, помимо хранения основного значения, может содержать ещё другую пару аналогичной структуры (значение + ссылка на другую пару) - и такая последовательность может длиться бесконечно.

cons(1, cons(2, cons(3, cons(4, cons(5, ...
cons('one', cons('two', cons('three', cons('four', cons('five', ...

Однако, надо понимать, что сделать это можно не только с помощью пар. Представимы списки на основе массивов, а также некоторых других типов данных. Поэтому, если мы пользуемся списком, то к нему нельзя напрямую применять функции по работе с парами (даже, если мы знаем, что данный конкретный список состоит из пар). Для этого вводятся специальные функции для работы со списками, которые учитывают внутреннюю реализацию списка (которая (внутренняя реализация списка), как мы уже знаем, может изменяться).

Во-вторых, коль скоро мы реализовали список именно на основе пар, то следует понимать, что не каждая пара, с которой мы имеем дело (какой бы "сложной" она ни была), является списком (представляет список). Как уже говорилось, список предполагает, что у него есть начало и конец, также мы должны иметь возможность последовательно перемещаться от элемента к элементу. Для того, чтобы понять, что мы достигли последнего элемента списка и перемещаться дальше уже нет смысла, мы вводим специальный маркер конца списка - пустую пару l() (также, по предварительному соглашению, в роли маркера могут выступать другие подходящие значения, например, null). Как только мы встречаем очередную пару, в cdr которой находится пустая пара, то это означает, что очередное значение списка, лежащее в car пары, является последним элементом списка. Отметим также, что у пустого списка (списка, в котором нет ни одного элемента) не может быть ни головы, ни хвоста. Поэтому соответствующие операции (взятие head или tail) в таких ситуациях приводят к возникновению ошибки. Чтобы её избежать, вводят функцию для проверки списка на "пустоту" (например, isEmpty), а далее берут голову или хвост у списка, только предварительно убедившись, что он не является пустым.

Ниже приведены примеры пар, которые нельзя назвать списками. Они не реализуют требования, предъявляемые к односвязным спискам, отсутствует последовательная связь между элементами и/или нет маркера конца списка:

cons(1, cons(cons(3, null), 2));
cons(1, cons(2, cons(3, 4)));
cons(cons(1, 2), cons(3, cons(4, null)));

Теперь покажем пары, которыми мы можем смело пользоваться как списками:

cons(1, cons(2, cons(3, null)));
cons('This', cons('is', cons('a', cons('list', null))));

l() - отвлекаемся от деталей и повышаем уровень абстракции

В уроке мы отметили, что следующие две записи, конструирующие список, являются эквивалентными:

cons(1, cons(2, cons(3, cons(4, cons(5, null))))); // (1, 2, 3, 4, 5)
l(1, 2, 3, 4, 5); // (1, 2, 3, 4, 5)

Причин, достаточных для принятия решения о создании функции l, много. Отметим наиболее важные из них (конечно, все они взаимосвязаны):

  • Выделив код создания списка в отдельную функцию и дав ей имя l (сокращ. от list), мы ввели отдельную и понятную абстракцию, отвечающую за создание списков (и ничего другого!). Выше говорилось, что списки могут быть реализованы не только на парах, но и на массивах, а также других типах данных. Так вот, наша абстракция l позволяет отвлечься от внутреннего устройства списка (тот, кто будет пользоваться этой функцией, не обязан знать, какими способами она конструирует список), а в случае необходимости и изменить это устройство "незаметно и безболезненно" для пользователей l.
  • Хорошая абстракция делает код более понятным, повышает его читабельность. Теперь, видя в коде l, мы вполне однозначно понимаем, что здесь происходит. Тогда как в ином случае, цепляясь глазом за множественные, разбросанные среди строк cons, мы каждый раз должны будем определять, что же делает данная конкретная пара: то ли список создаёт, то ли временные данные хранит, то ли пирожки печёт?! ;)

Посмотрите на "безликие" нагромождения пар, создающие разные сущности (которые мы проходили в прошлых курсах). Только комментарии помогают понять, что здесь происходит.

cons(5, cons(2, cons(7, cons(11, cons(6, cons(14, null)))))); // создание списка
cons(3, 17); // создание точки
cons(8, 17); // создание рационального числа
cons(cons(3, 33), cons(-2, -22)); // создание сегмента (отрезка)
const rectangle = cons(cons(-2, 23), cons(5, 11)); // создание прямоугольника
2 * (car(cdr(rectangle)) + cdr(cdr(rectangle))); // вычисление периметра прямоугольника

А вот как выглядит код с введёнными абстракциями (и комментарии здесь уже не нужны!):

list(5, 2, 7, 11, 6, 14);
makePoint(3, 17);
makeRational(8, 17);
makeSegment(makePoint(3, 33), makePoint(-2, -22));
const point = makePoint(-2, 23);
const rectangle = makeRectangle(point, 5, 11);
perimeter(rectangle);

Естественно, введение функции устраняет дублирование кода. Каждый раз писать при создании списка такое нагромождение кода в виде вложенных cons, демонстрируя при этом все внутренности создаваемой конструкции - не лучший стиль написания кода.