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

Пары и списки

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

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

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

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, несмотря на то, что у нас уже есть конструктор cons. Это необходимо по нескольким причинам. Отметим наиболее важные из них:

  • Выделив код создания списка в отдельную функцию и дав ей имя 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, демонстрируя при этом все внутренности создаваемой конструкции, — не лучший стиль написания кода.