Как уже́ говорилось в первой лекции, основой функциональной парадигмы программирования в большей мере являются такие направления развития математической мысли, как комбинаторная логика и λ-исчисление. В свою очередь последнее более тесно связано с функциональным программированием, и именно λ-исчисление называют теоретическими основами функционального программирования.
Для того, чтобы рассматривать теоретические основы функционального программирования, необходимо в первую очередь ввести некоторые соглашения, описать обозначения и построить некоторую формальную систему.
Пусть заданы объекты некоторого первичного типа
. Сейчас совершенно не важно, что именно представляют собой эти выделенные объекты. Обычно считается, что на этих объектах определён набор базисных операций и предикатов. По традиции, которая пошла ещё от Маккарти (автора Лиспа), такие объекты называются атомами. В теории фактический способ реализации базисных операций и предикатов совершенно не важен, их существование просто постулируется. Поэтому каждый конкретный функциональный язык реализует базисный набор по-своему.
В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:
- Операция создания пары —
. Эта операция также называется конструктором или составителем.
- Операция отсечения головы —
. Это первая селективная операция.
- Операция отсечения хвоста —
. Это вторая селективная операция.
Селективные операции отсечения головы и хвоста также называют просто селекторами. Выделенные операции связаны друг с другом следующими тремя аксиомами:



Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество
-выражений (обозначение —
). Например:
Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу
. Этот атом в дальнейшем будет называться «пустым списком» и обозначаться символами
(хотя в разных языках функционального програмирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество
, которое называется «список над
».
Определение:
- Пустой список
![{\displaystyle [\,]\in \operatorname {List} (A)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7dfa43a83bdab173d7b5c70d33b71c824fcb130a)

Главное свойство списка:
.
Для обозначения списка из
элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая:
. Применяя к такому списку определённым образом операции
и
можно добраться до любого элемента списка, так как:
(при
).
Кроме списков вводится ещё один тип данных, который носит название «списочная структура над
» (обозначение —
), при этом можно построить следующую структуру отношений:
. Определение списочной структуры выглядит следующим образом:
Определение:
.
.
Т. е. видно, что списочная структура — либо атом, либо список состоящий из списочных структур. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение:
. Для списочных структур вводится такое понятие, как уровень вложенности.
Несколько слов о программной реализации[править]
Пришло время уделить некоторое внимание рассмотрению программной реализации списков и списочных структур. Это необходимо для более тонкого понимания того, что происходит во время работы функциональной программы, как на каком-либо реализованном функциональном языке, так и на абстрактном языке.
Каждый объект занимает в памяти машины какое-то место. Однако атомы представляют собой указатели (адреса) на ячейки, в которых содержатся объекты. В этом случае пара
графически может быть представлена так, как показано на рисунке 1.
Рисунок 1. Представление пары в памяти компьютера
Адрес ячейки, которая содержит указатели на
и
, и есть объект
. Как видно на рисунке, пара представлена двумя адресами — указатель на голову и указатель на хвост. Традиционно первый указатель (на рисунке выделен голубым цветом) называется a-поле, а второй указатель (на рисунке — зеленоватый) называется d-поле.
Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечёркнутым квадратом (указатель ни на что не указывает).
Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее (
) может быть представлена так, как показано на рисунке 2.
Рисунок 2. Графическое представление списочной структуры
![{\displaystyle {\bigg [}a_{1},\;{\Big [}a_{2},\;a_{3},\;[a_{4}]\,{\Big ]},\;a_{5}{\bigg ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8061f4901eada0cc3debdb64b689a6f4540162ae)
На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы
и
имеют уровень вложенности 1, атомы
и
— 2, а атом
— 3 соответственно.
Остаётся отметить, что операция
требует расхода памяти, ибо при конструировании пары выделяется память под указатели. С другой стороны обе операции
и
не требуют памяти, они просто возвращают адрес, который содержится соответственно в a- или d-поле.
Пример 5. Операция
.
Для начала необходимо рассмотреть более подробно работу операции
. Пояснение работы будет проведено на трёх более или менее общих примерах:
(при этом результат не является элементом
).
![{\displaystyle \operatorname {prefix} {\Big (}a_{1},\;[b_{1},\;b_{2}]{\Big )}=[a_{1},\;b_{1},\;b_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3465584c10481572ffc4e223909c185c0c63a1f)
![{\displaystyle \operatorname {prefix} {\Big (}[a_{1},\;a_{2}],\;[b_{1},\;b_{2}]{\Big )}={\Big [}[a_{1},\;a_{2}],\;b_{1},\;b_{2}{\Big ]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cdf3f43dabecb4b73cf2bde6ae2b67c9996513fa)
Пример 6. Функция определения длины списка
.
Перед тем, как собственно начать реализовывать функцию
, необходимо понять, что она должна возвращать. Понятийное определение результата функции
может звучать как «количество элементов в списке, который передан функции в качестве параметра». Здесь возникает два случая — функции передан пустой список и функции передан непустой список. С первым случаем всё ясно — результат должен быть нулевым. Во втором случае задачу можно разбить на две подзадачи, путём разделения переданного списка на голову и хвост при помощи операций
и
.
Осмысленно, что операция
возвращает первый элемент списка, а операция
возвращает список из оставшихся элементов. Пусть известна длина списка, полученного при помощи операции
, тогда длина исходного списка будет равна известной длине, увеличенной на единицу. В этом случае можно легко записать определение самой функции
:
Пример 7. Функция слияния двух списков
.
Реализовать функцию слияния (или сцепления) списков можно многими способами. Первое, что приходит в голову — деструктивное присваивание. Т. е. заменить указатель на
в конце первого списка на указатель на голову второго списка и тем самым получить результат в первом списке. Однако здесь изменяется сам первый список. Такие приёмы запрещены в функциональном программировании (хотя, в очередной раз необходимо заметить, что в некоторых функциональных языках всё-таки есть такая возможность).
Второй способ состоит в копировании верхнего уровня первого списка и помещении в последний указатель копии ссылку на первый элемент второго списка. Этот способ хорош с точки зрения деструктивности (не выполняет деструктивных и побочных действий), однако требует дополнительных затрат памяти и времени.
Последний пример показывает, как при помощи постепенного конструирования можно построить новый список, который равен сцепке двух заданных.
- Построить функции, вычисляющие
-ый элемент следующих рядов:





- Объяснить результаты операции
, показанные в примере 5. Для объяснения можно воспользоваться графическим методом.
- Объяснить результат работы функции
(пример 7). Пояснить, почему функция не является деструктивной.
- Построить функции, работающие со списками:
— функция вычленения
-ого элемента из заданного списка.
— функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
— функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
— функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
— функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
Ответы для самопроверки[править]
Большинство ответов для самопроверки представляют собой лишь одни из возможных вариантов (в большинстве случаев наиболее интуитивные).
- Функции, вычисляющие
-ый элемент рядов:
:


:


:


:


:




- Объяснение работы операции
можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции
также используется инфиксная запись посредством символа двоеточия.
- Первый пример работы операции — определение самой операции. Рассматривать его нет смысла, ибо операция
определяется именно таким образом.
(Эти преобразование проведены по определению списка).
.
- В качестве примера работы функции
рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов:
и
. Опять же для того, чтобы не загромождать объяснение, для записи операции
используется инфиксная форма. Для более полного понимания приведённого объяснения необходимо помнить определение списка.
![{\displaystyle \operatorname {append} {\Big (}[a,\;b],\;[c,\;d]{\Big )}=a:\operatorname {append} {\Big (}[b],\;[c,\;d]{\Big )}=}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3d6e243c8e928814f8d501e7cbdb6dfbaab86f6c)
.
- Функции, работающие со списками:
:
![{\displaystyle \operatorname {getN} (n,\;[\,])=\_}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f9ba3df95ed3a753821e3753e04b7878f174642)


:
![{\displaystyle \operatorname {listSumm} ([\,],\;L)=L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/55373433e6a2769603ed3059baa4bfff623b94d7)
![{\displaystyle \operatorname {listSumm} (L,\;[\,])=L}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc40a16a09e05cc39c959efddc406a99c363d3d2)

:
![{\displaystyle \operatorname {oddEven} ([\,])=[\,]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e40088176cdae4a5e61ca2b642cf4a5018c6130)
![{\displaystyle \operatorname {oddEven} ([x])=[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07c6c5b15712fafe797c948f84910f82d8825adc)

:
![{\displaystyle \operatorname {reverse} ([\,])=[\,]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8fc25d9e5d42ba243afd6c1b47000e88ee5cc9f)
![{\displaystyle \operatorname {reverse} (L)=\operatorname {append} {\bigg (}\operatorname {reverse} {\Big (}\operatorname {tail} (L){\Big )},\;{\Big [}\operatorname {head} (L){\Big ]}{\bigg )}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e5d07cf219d1d38fd115c89e0a4f92ee11fe984)
:
![{\displaystyle \operatorname {map} (f,\;[\,])=[\,]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2d1e9f49a9505b6efb8ab07c3501ec3ab636399)
