Основы функционального программирования/Структуры данных и базисные операции
Введение Править
Как уже́ говорилось в первой лекции, основой функциональной парадигмы программирования в большей мере являются такие направления развития математической мысли, как комбинаторная логика и λ-исчисление. В свою очередь последнее более тесно связано с функциональным программированием, и именно λ-исчисление называют теоретическими основами функционального программирования.
Для того, чтобы рассматривать теоретические основы функционального программирования, необходимо в первую очередь ввести некоторые соглашения, описать обозначения и построить некоторую формальную систему.
Пусть заданы объекты некоторого первичного типа . Сейчас совершенно не важно, что именно представляют собой эти выделенные объекты. Обычно считается, что на этих объектах определён набор базисных операций и предикатов. По традиции, которая пошла ещё от Маккарти (автора Лиспа), такие объекты называются атомами. В теории фактический способ реализации базисных операций и предикатов совершенно не важен, их существование просто постулируется. Поэтому каждый конкретный функциональный язык реализует базисный набор по-своему.
В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:
- Операция создания пары — . Эта операция также называется конструктором или составителем.
- Операция отсечения головы — . Это первая селективная операция.
- Операция отсечения хвоста — . Это вторая селективная операция.
Селективные операции отсечения головы и хвоста также называют просто селекторами. Выделенные операции связаны друг с другом следующими тремя аксиомами:
Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество -выражений (обозначение — ). Например:
Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу . Этот атом в дальнейшем будет называться «пустым списком» и обозначаться символами (хотя в разных языках функционального програмирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество , которое называется «список над ».
Определение:
- Пустой список
Главное свойство списка: .
Для обозначения списка из элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: . Применяя к такому списку определённым образом операции и можно добраться до любого элемента списка, так как:
(при ).
Кроме списков вводится ещё один тип данных, который носит название «списочная структура над » (обозначение — ), при этом можно построить следующую структуру отношений: . Определение списочной структуры выглядит следующим образом:
Определение:
- .
- .
Т. е. видно, что списочная структура — либо атом, либо список состоящий из списочных структур. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: . Для списочных структур вводится такое понятие, как уровень вложенности.
Несколько слов о программной реализации Править
Пришло время уделить некоторое внимание рассмотрению программной реализации списков и списочных структур. Это необходимо для более тонкого понимания того, что происходит во время работы функциональной программы, как на каком-либо реализованном функциональном языке, так и на абстрактном языке.
Каждый объект занимает в памяти машины какое-то место. Однако атомы представляют собой указатели (адреса) на ячейки, в которых содержатся объекты. В этом случае пара графически может быть представлена так, как показано на рисунке 1.
Адрес ячейки, которая содержит указатели на и , и есть объект . Как видно на рисунке, пара представлена двумя адресами — указатель на голову и указатель на хвост. Традиционно первый указатель (на рисунке выделен голубым цветом) называется a-поле, а второй указатель (на рисунке — зеленоватый) называется d-поле.
Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечёркнутым квадратом (указатель ни на что не указывает).
Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее ( ) может быть представлена так, как показано на рисунке 2.
На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы и имеют уровень вложенности 1, атомы и — 2, а атом — 3 соответственно.
Остаётся отметить, что операция требует расхода памяти, ибо при конструировании пары выделяется память под указатели. С другой стороны обе операции и не требуют памяти, они просто возвращают адрес, который содержится соответственно в a- или d-поле.
Примеры Править
Пример 5. Операция .
Для начала необходимо рассмотреть более подробно работу операции . Пояснение работы будет проведено на трёх более или менее общих примерах:
- (при этом результат не является элементом ).
Пример 6. Функция определения длины списка .
Перед тем, как собственно начать реализовывать функцию , необходимо понять, что она должна возвращать. Понятийное определение результата функции может звучать как «количество элементов в списке, который передан функции в качестве параметра». Здесь возникает два случая — функции передан пустой список и функции передан непустой список. С первым случаем всё ясно — результат должен быть нулевым. Во втором случае задачу можно разбить на две подзадачи, путём разделения переданного списка на голову и хвост при помощи операций и .
Осмысленно, что операция возвращает первый элемент списка, а операция возвращает список из оставшихся элементов. Пусть известна длина списка, полученного при помощи операции , тогда длина исходного списка будет равна известной длине, увеличенной на единицу. В этом случае можно легко записать определение самой функции :
Пример 7. Функция слияния двух списков .
Реализовать функцию слияния (или сцепления) списков можно многими способами. Первое, что приходит в голову — деструктивное присваивание. Т. е. заменить указатель на в конце первого списка на указатель на голову второго списка и тем самым получить результат в первом списке. Однако здесь изменяется сам первый список. Такие приёмы запрещены в функциональном программировании (хотя, в очередной раз необходимо заметить, что в некоторых функциональных языках всё-таки есть такая возможность).
Второй способ состоит в копировании верхнего уровня первого списка и помещении в последний указатель копии ссылку на первый элемент второго списка. Этот способ хорош с точки зрения деструктивности (не выполняет деструктивных и побочных действий), однако требует дополнительных затрат памяти и времени.
Последний пример показывает, как при помощи постепенного конструирования можно построить новый список, который равен сцепке двух заданных.
Упражнения Править
- Построить функции, вычисляющие -ый элемент следующих рядов:
- Объяснить результаты операции , показанные в примере 5. Для объяснения можно воспользоваться графическим методом.
- Объяснить результат работы функции (пример 7). Пояснить, почему функция не является деструктивной.
- Построить функции, работающие со списками:
- — функция вычленения -ого элемента из заданного списка.
- — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
- — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
- — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
- — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
Ответы для самопроверки Править
Большинство ответов для самопроверки представляют собой лишь одни из возможных вариантов (в большинстве случаев наиболее интуитивные).
- Функции, вычисляющие -ый элемент рядов:
- :
- :
- :
- :
- :
- :
- Объяснение работы операции можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции также используется инфиксная запись посредством символа двоеточия.
- Первый пример работы операции — определение самой операции. Рассматривать его нет смысла, ибо операция определяется именно таким образом.
- (Эти преобразование проведены по определению списка).
- .
- В качестве примера работы функции рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов: и . Опять же для того, чтобы не загромождать объяснение, для записи операции используется инфиксная форма. Для более полного понимания приведённого объяснения необходимо помнить определение списка.
- .
- Функции, работающие со списками:
- :
- :
- :
- :
- :
- :