Основы функционального программирования/Структуры данных и базисные операции: различия между версиями

#Операция создания пары — <math>\operatorname{prefix}(x,\;y) \equiv x:y \equiv [x \mid y]</math>. Эта операция также называется конструктором или составителем.

#Операция отсечения головы — <math>\operatorname{head}(x) \equiv h(x)</math>. Это первая селективная операция.

#Операция отсечения хвоста — <math>\operatorname{tail}(x) \equiv t(x)</math>. Это вторая селективная операция.

#<math>\operatorname{head}(x:y) = x</math>

#<math>\operatorname{tail}(x:y) = y</math>

#<math>\operatorname{prefix}\Big(\operatorname{head}(x:y),\; \operatorname{tail}(x:y)\Big) = (x:y)</math>

Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество <math>S</math>-выражений (обозначение — <math>\operatorname{SExpr}(A)</math>). Например:

<center><math>a_{1}a_1:(a_{2}a_2:a_{3}a_3) \in \operatorname{SExpr}(A)</math></center>

Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу <math>A</math>. Этот атом в дальнейшем будет называться «пустым списком» и обозначаться символами <math>[\,]</math> (хотя в разных языках функционального програмирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество <math>\operatorname{List}(A) \subset \operatorname{SExpr}(A)</math>, которое называется «список над <math>A</math>».

#Пустой список <math>[\,] \in \operatorname{List}(A)</math>

#<math>x \in A \and y \in \operatorname{List}(A) \Rightarrow x : y \in \operatorname{List}(A)</math>

Главное свойство списка: <math>x \in \operatorname{List}(A) \and x \neq [\,] \Rightarrow \operatorname{head}(x) \in A,\; \operatorname{tail}(x) \in \operatorname{List}(A)</math>.

Для обозначения списка из <math>n</math> элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: <math>[a_{1}a_1,\; a_{2}a_2, \;\ldots,\; a_{n}a_n]</math>. Применяя к такому списку определённым образом операции <math>\operatorname{head}</math> и <math>\operatorname{tail}</math> можно добраться до любого элемента списка, так как:

<math>\operatorname{head}\Big([a_{1}a_1,\; a_{2}a_2,\; \ldots,\; a_{n}a_n]\Big) = a_{1}a_1</math>

<math>\operatorname{tail}\Big([a_{1}a_1,\; a_{2}a_2,\; \ldots,\; a_{n}a_n]\Big) = [a_{2}a_2, \;\ldots,\; a_{n}a_n]</math> (при <math>n > 0</math>).

Кроме списков вводится ещё один тип данных, который носит название «списочная структура над <math>A</math>» (обозначение — <math>\operatorname{ListStr}(A)</math>), при этом можно построить следющую структуру отношений: <math>\operatorname{List}(A) \subset \operatorname{ListStr}(A) \subset \operatorname{SExpr}(A)</math>. Определение списочной структуры выглядит следующим образом:

#<math>a \in A \Rightarrow a \in \operatorname{ListStr}(A)</math>.

#<math>\operatorname{List}\Big(\operatorname{ListStr}(A)\Big) \in \operatorname{ListStr}(A)</math>.

Т.&nbsp;е. видно, что списочная структура — это список, элементами которого могут быть как атомы, так и другие списочные структуры, в том числе и обыкновенные списки. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: <math>\bigg[a_{1}a_1,\; \Big[a_{2}a_2,\; a_{3}a_3,\; [a_{4}a_4]\,\Big],\; a_{5}a_5\bigg]</math>. Для списочных структур вводится такое понятие, как уровень вложенности.

Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее (<math>\bigg[a_{1}a_1,\; \Big[a_{2}a_2,\; a_{3}a_3,\; [a_{4}a_4]\,\Big],\; a_{5}a_5\bigg]</math>) может быть представлена так, как показано на рисунке 2.

[[Изображение:Fp_figure_02.gif|thumb|Рисунок 2. Графическое представление списочной структуры <math>\bigg[a_{1}a_1,\; \Big[a_{2}a_2,\; a_{3}a_3,\; [a_{4}a_4]\,\Big],\; a_{5}a_5\bigg]</math>]]

На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы <math>a_{1}a_1</math> и <math>a_{5}a_5</math> имеют уровень вложенности 1, атомы <math>a_{2}a_2</math> и <math>a_{3}a_3</math> — 2, а атом <math>a_{4}a_4</math> — 3 соответственно.

ОстаетсяОстаётся отметить, что операция <math>\operatorname{prefix}</math> требует расхода памяти, ибо при конструировании пары выделяется память под указатели. С другой стороны обе операции <math>\operatorname{head}</math> и <math>\operatorname{tail}</math> не требуют памяти, они просто возвращают адрес, который содержится соответственно в a- или d-поле.

'''Пример 5. Операция <math>\operatorname{prefix}</math>.'''

Для начала необходимо рассмотреть более подробно работу операции <math>\operatorname{prefix}</math>. Пояснение работы будет проведено на трёх более или менее общих примерах:

#<math>prefix(a_\operatorname{1prefix}(a_1, a_{2}a_2) = a_{1}a_1:a_{2}a_2</math> (при этом результат не является элементом <math>\operatorname{ListStr}(A)</math>).

#<math>\operatorname{prefix}\Big(a_{1}a_1,\; [b_{1}b_1,\; b_{2}b_2]\Big) = [a_{1}a_1,\; b_{1}b_1,\; b_{2}b_2]</math>

#<math>\operatorname{prefix}\Big([a_{1}a_1,\; a_{2}a_2],\; [b_{1}b_1,\; b_{2}b_2]\Big) = \Big[[a_{1}a_1,\; a_{2}a_2],\; b_{1}b_1,\; b_{2}b_2\Big]</math>

'''Пример 6. Функция определения длины списка <math>\operatorname{length}</math>.'''

Перед тем, как собственно начать реализовывать функцию <math>\operatorname{length}</math>, необходимо понять, что она должна возвращать. Понятийное определение результата функции <math>\operatorname{length}</math> может звучать как «количество элементов в списке, который передан функции в качестве параметра». Здесь возникает два случая — функции передан пустой список и функции передан непустой список. С первым случаем всё ясно — результат должен быть нулевым. Во втором случае задачу можно разбить на две подзадачи, путём разделения переданного списка на голову и хвост при помощи операций <math>\operatorname{head}</math> и <math>\operatorname{tail}</math>.

Осмысленно, что операция <math>\operatorname{head}</math> возвращает первый элемент списка, а операция <math>\operatorname{tail}</math> возвращает список из оставшихся элементов. Пусть известна длина списка, полученного при помощи операции <math>\operatorname{tail}</math>, тогда длина исходного списка будет равна известной длине, увеличенной на единицу. В этом случае можно легко записать определение самой функции <math>\operatorname{length}</math>:

<math>\operatorname{length}([\,]) = 0</math>

<math>\operatorname{length}(L) = 1 + \operatorname{length }\Big(\operatorname{tail}(L)\Big)</math>

'''Пример 7. Функция слияния двух списков <math>\operatorname{append}</math>.'''

Реализовать функцию слияния (или сцепления) списков можно многими способами. Первое, что приходит в голову — деструктивное присваивание. Т.&nbsp;е. заменить указатель на <math>[\,]</math> в конце первого списка на указатель на голову второго списка и тем самым получить результат в первом списке. Однако здесь изменяется сам первый список. Такие приёмы запрещены в функциональном программировании (хотя, в очередной раз необходимо заметить, что в некоторых функциональных языках всё-таки есть такая возможность).

<math>\operatorname{append}([\,],\; L_{2}L_2) = L_{2}L_2</math>

<math>append(L_\operatorname{1append}(L_1,\; L_{2}L_2) = \operatorname{prefix}\bigg(\operatorname{head}\left(L_{1}L_1\right),\; \operatorname{append}\Big(tail(L_\operatorname{1tail}(L_1),\; L_{2}L_2\Big)\bigg)</math>

##<math>a_{n}a_n = x^{n}</math>

##<math>a_{n}a_n = \sum_{i = 1}^{n} i</math>

##<math>a_{n}a_n = \sum_{j = 1}^{n} (\sum_{i = 1}^{j} i)</math>

##<math>a_{n}a_n = \sum_{i = 1}^{p} n^{-i}</math>

##<math>a_{n}a_n = e^{n} = \sum_{i = 0}^{\infty} \frac{n^{i}}{i!}</math>

#Объяснить результат работы функции <math>\operatorname{append}</math> (пример&nbsp;7). Пояснить, почему функция не является деструктивной.

##<math>\operatorname{getN}</math> — функция вычленения <math>N</math>-ого элемента из заданного списка.

##<math>\operatorname{listSumm}</math> — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.

##<math>\operatorname{oddEven}</math> — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.

##<math>\operatorname{reverse}</math> — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).

##<math>\operatorname{map}</math> — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.

##<math>\operatorname{power}</math>:

##*<math>\operatorname{power}(x,\; 0) = 1</math>

##*<math>\operatorname{power}(x,\; n) = x \cdot \operatorname{power}(x,\; n - 1)</math>

##<math>\operatorname{summT}</math>:

##*<math>\operatorname{summT}(1) = 1</math>

##*<math>\operatorname{summT}(n) = n + \operatorname{summT }(n - 1)</math>

##<math>\operatorname{summP}</math>:

##*<math>\operatorname{summP}(1) = 1</math>

##*<math>\operatorname{summP}(n) = \operatorname{summT}(n) + \operatorname{summP }(n - 1)</math>

##<math>\operatorname{summPower}</math>:

##*<math>\operatorname{summPower}(n,\; 0) = 1</math>

##*<math>\operatorname{summPower}(n,\; p) = \frac{1}{\operatorname{power}(n, \; p)} + \operatorname{summPower}(n,\; p - 1)</math>

##<math>\operatorname{exponent}</math>:

##*<math>\operatorname{exponent}(n,\; 0) = 1</math>

##*<math>\operatorname{exponent}(n,\; p) = \frac{\operatorname{power}(n,\; p)}{\operatorname{factorial}(p)} + \operatorname{exponent}(n,\; p - 1)</math>

##*<math>\operatorname{factorial}(0) = 1</math>

##*<math>\operatorname{factorial}(n) = n \cdot \operatorname{factorial}(n - 1)</math>

#Объяснение работы операции <math>\operatorname{prefix}</math> можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции <math>\operatorname{prefix}</math> также используется инфиксная запись посредством символа двоеточия.

##Первый пример работы операции — определение самой операции. Рассматривать его нет смысла, ибо операция <math>\operatorname{prefix}</math> определяется именно таким образом.

##<math>\operatorname{prefix}\Big(a_{1}a_1,\; [b_{1}b_1,\; b_{2}b_2]\Big) = \operatorname{prefix}\Big(a_{1}a_1,\; b_{1}b_1:(b_{2}b_2:[\,])\Big) = a_{1}a_1:\Big(b_{1}b_1:(b_{2}b_2:[\,])\Big) = [a_{1}a_1,\; b_{1}b_1,\; b_{2}b_2]</math> (Эти преобразование проведены по определению списка).

##<math>\operatorname{prefix}\Big([a_{1}a_1,\; a_{2}a_2],\; [b_{1}b_1,\; b_{2}b_2]\Big) = \operatorname{prefix}\Big([a_{1}a_1,\; a_{2}a_2],\; b_{1}b_1:(b_{2}b_2:[\,])\Big) = \Big([a_{1}a_1,\; a_{2}a_2]\Big):\Big(b_{1}b_1:(b_{2}b_2:[\,])\Big) = \Big[[a_{1}a_1,\; a_{2}a_2],\; b_{1}b_1,\; b_{2}b_2\Big]</math>.

##В качестве примера работы функции <math>\operatorname{append}</math> рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов: <math>[a,\; b]</math> и <math>[c,\; d]</math>. Опять же для того, чтобы не загромождать объяснение, для записи операции <math>\operatorname{prefix}</math> используется инфиксная форма. Для более полного понимания приведённого объяснения необходимо помнить определение списка.

##*<math>\operatorname{append}\Big([a,\; b],\; [c,\; d]\Big) = a:\operatorname{append}\Big([b],\; [c,\; d]\Big) = a:\bigg(b:\operatorname{append}\Big([\,],\; [c,\; d]\Big)\bigg) = a:\bigg(b:\Big([c,\; d]\Big)\bigg) = a:\bigg(b:\Big(c:(d:[\,])\Big)\bigg) = [a,\; b,\; c,\; d]</math>.

##<math>\operatorname{getN}</math>:

##*<math>\operatorname{getN}(n,\; [\,]) = \_</math>

##*<math>\operatorname{getN}(1,\; L) = \operatorname{head}(L)</math>

##*<math>\operatorname{getN}(n,\; L) = \operatorname{getN}\Big(n - 1,\; \operatorname{tail}(L)\Big)</math>

##<math>\operatorname{listSumm}</math>:

##*<math>\operatorname{listSumm}([\,],\; L) = L</math>

##*<math>\operatorname{listSumm}(L,\; [\,]) = L</math>

##*<math>listSumm(L_\operatorname{1listSumm}(L_1,\; L_{2}L_2) = \operatorname{prefix}\bigg(\Big(head(L_\operatorname{1head}(L_1) + head(L_\operatorname{2head}(L_2)\Big),\; \operatorname{listSumm}\Big(tail(L_\operatorname{1tail}(L_1),\; tail(L_\operatorname{2tail}(L_2)\Big)\bigg)</math>

##<math>\operatorname{oddEven}</math>:

##*<math>\operatorname{oddEven}([\,]) = [\,]</math>

##*<math>\operatorname{oddEven}([x]) = [x]</math>

##*<math>\operatorname{oddEven}(L) = \operatorname{prefix}\bigg(\operatorname{prefix}\Big(\operatorname{head}(\operatorname{tail}(L)),\; \operatorname{head}(L)\Big),\; \operatorname{oddEven}\Big(\operatorname{tail}(\operatorname{tail}(L))\Big)\bigg)</math>

##<math>\operatorname{reverse}</math>:

##*<math>\operatorname{reverse}([\,]) = [\,]</math>

##*<math>\operatorname{reverse}(L) = \operatorname{append}\bigg(\operatorname{reverse}\Big(\operatorname{tail}(L)\Big),\; \Big[\operatorname{head}(L)\Big]\bigg)</math>

##<math>\operatorname{map}</math>:

##*<math>\operatorname{map}(f,\; [\,]) = [\,]</math>

##*<math>\operatorname{map}(f,\; L) = \operatorname{prefix}\bigg(f\Big(\operatorname{head}(L)\Big),\; \operatorname{map}\Big(f,\; \operatorname{tail}(L)\Big)\bigg)</math>