Основы функционального программирования/Структуры данных и базисные операции: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
м Отформатированы формулы |
||
Строка 12:
В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:
#Операция создания пары — <math>prefix(x,\;y) \equiv x:y \equiv [x \mid y]</math>. Эта операция также называется конструктором или составителем.
#Операция отсечения головы — <math>head(x) \equiv h(x)</math>. Это первая селективная операция.
#Операция отсечения хвоста — <math>tail(x) \equiv t(x)</math>. Это вторая селективная операция.
Строка 20:
#<math>head(x:y) = x</math>
#<math>tail(x:y) = y</math>
#<math>prefix\Big(head(x:y),\; tail(x:y)\Big) = (x:y)</math>
Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество <math>S</math>-выражений (обозначение — <math>SExpr(A)</math>). Например:
Строка 37:
Для обозначения списка из <math>n</math> элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: <math>[a_{1},\; a_{2}, \;\ldots,\; a_{n}]</math>. Применяя к такому списку определённым образом операции <math>head</math> и <math>tail</math> можно добраться до любого элемента списка, так как:
<math>head\Big([a_{1},\; a_{2},\; \ldots,\; a_{n}]\Big) = a_{1}</math>
<math>tail\Big([a_{1},\; a_{2},\; \ldots,\; a_{n}]\Big) = [a_{2}, \;\ldots,\; a_{n}]</math> (при <math>n > 0</math>).
Кроме списков вводится ещё один тип данных, который носит название «списочная структура над <math>A</math>» (обозначение — <math>ListStr(A)</math>), при этом можно построить следющую структуру отношений: <math>List(A) \subset ListStr(A) \subset SExpr(A)</math>. Определение списочной структуры выглядит следующим образом:
Строка 46:
#<math>a \in A \Rightarrow a \in ListStr(A)</math>.
#<math>List\Big(ListStr(A)\Big) \in ListStr(A)</math>.
Т. е. видно, что списочная структура — это список, элементами которого могут быть как атомы, так и другие списочные структуры, в том числе и обыкновенные списки. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: <math>\bigg[a_{1},\; \Big[a_{2},\; a_{3},\; [a_{4}]\,\Big],\; a_{5}\bigg]</math>. Для списочных структур вводится такое понятие, как уровень вложенности.
== Несколько слов о программной реализации ==
Строка 62:
Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечёркнутым квадратом (указатель ни на что не указывает).
Таким образом, списочная структура, которая рассмотрена несколькими параграфами ранее (<math>\bigg[a_{1},\; \Big[a_{2},\; a_{3},\; [a_{4}]\,\Big],\; a_{5}\bigg]</math>) может быть представлена так, как показано на рисунке 2.
[[Изображение:Fp_figure_02.gif|thumb|Рисунок 2. Графическое представление списочной структуры <math>\bigg[a_{1},\; \Big[a_{2},\; a_{3},\; [a_{4}]\,\Big],\; a_{5}\bigg]</math>]]
На этом рисунке также хорошо проиллюстрировано понятие уровня вложенности — атомы <math>a_{1}</math> и <math>a_{5}</math> имеют уровень вложенности 1, атомы <math>a_{2}</math> и <math>a_{3}</math> — 2, а атом <math>a_{4}</math> — 3 соответственно.
Строка 77:
#<math>prefix(a_{1}, a_{2}) = a_{1}:a_{2}</math> (при этом результат не является элементом <math>ListStr(A)</math>).
#<math>prefix\Big(a_{1},\; [b_{1},\; b_{2}]\Big) = [a_{1},\; b_{1},\; b_{2}]</math>
#<math>prefix\Big([a_{1},\; a_{2}],\; [b_{1},\; b_{2}]\Big) = \Big[[a_{1},\; a_{2}],\; b_{1},\; b_{2}\Big]</math>
'''Пример 6. Функция определения длины списка <math>length</math>.'''
Строка 88:
<math>length([]) = 0</math>
<math>length(L) = 1 + length \Big(tail(L)\Big)</math>
'''Пример 7. Функция слияния двух списков <math>append</math>.'''
Строка 96:
Второй способ состоит в копировании верхнего уровня первого списка и помещении в последний указатель копии ссылку на первый элемент второго списка. Этот способ хорош с точки зрения деструктивности (не выполняет деструктивных и побочных действий), однако требует дополнительных затрат памяти и времени.
<math>append([],\; L_{2}) = L_{2}</math>
<math>append(L_{1},\; L_{2}) = prefix\bigg(head\left(L_{1}\right),\; append\Big(tail(L_{1}),\; L_{2}\Big)\bigg)</math>
Последний пример показывает, как при помощи постепенного конструирования можно построить новый список, который равен сцепке двух заданных.
Строка 125:
#Функции, вычисляющие <math>N</math>-ый элемент рядов:
##<math>power</math>:
##*<math>power(x,\; 0) = 1</math>
##*<math>power(x,\; n) = x
##<math>summT</math>:
##*<math>summT(1) = 1</math>
Строка 134:
##*<math>summP(n) = summT(n) + summP (n - 1)</math>
##<math>summPower</math>:
##*<math>summPower(n,\; 0) = 1</math>
##*<math>summPower(n,\; p) =
##<math>exponent</math>:
##*<math>exponent(n,\; 0) = 1</math>
##*<math>exponent(n,\; p) = \frac{power(n,\; p)}{factorial(p)} + exponent(n,\; p - 1)</math>
##*<math>factorial(0) = 1</math>
##*<math>factorial(n) = n
#Объяснение работы операции <math>prefix</math> можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции <math>prefix</math> также используется инфиксная запись посредством символа двоеточия.
##Первый пример работы операции — определение самой операции. Рассматривать его нет смысла, ибо операция <math>prefix</math> определяется именно таким образом.
##<math>prefix\Big(a_{1},\; [b_{1},\; b_{2}]\Big) = prefix\Big(a_{1},\; b_{1}:(b_{2}:[])\Big) = a_{1}:\Big(b_{1}:(b_{2}:[])\Big) = [a_{1},\; b_{1},\; b_{2}]</math> (Эти преобразование проведены по определению списка).
##<math>prefix\Big([a_{1},\; a_{2}],\; [b_{1},\; b_{2}]\Big) = prefix\Big([a_{1},\; a_{2}],\; b_{1}:(b_{2}:[])\Big) = \Big([a_{1},\; a_{2}]\Big):\Big(b_{1}:(b_{2}:[])\Big) = \Big[[a_{1},\; a_{2}],\; b_{1},\; b_{2}\Big]</math>.
##В качестве примера работы функции <math>append</math> рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов: <math>[a,\; b]</math> и <math>[c,\; d]</math>. Опять же для того, чтобы не загромождать объяснение, для записи операции <math>prefix</math> используется инфиксная форма. Для более полного понимания приведённого объяснения необходимо помнить определение списка.
##*<math>append\Big([a,\; b],\; [c,\; d]\Big) = a:append\Big([b],\; [c,\; d]\Big) = a:\bigg(b: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>getN</math>:
##*<math>getN(n,\; []) = \_</math>
##*<math>getN(1,\; L) = head(L)</math>
##*<math>getN(n,\; L) = getN\Big(n - 1,\; tail(L)\Big)</math>
##<math>listSumm</math>:
##*<math>listSumm([],\; L) = L</math>
##*<math>listSumm(L,\; []) = L</math>
##*<math>listSumm(L_{1},\; L_{2}) = prefix\bigg(\Big(head(L_{1}) + head(L_{2})\Big),\; listSumm\Big(tail(L_{1}),\; tail(L_{2})\Big)\bigg)</math>
##<math>oddEven</math>:
##*<math>oddEven([]) = []</math>
##*<math>oddEven([x]) = [x]</math>
##*<math>oddEven(L) = prefix\bigg(prefix\Big(head(tail(L)),\; head(L)\Big),\; oddEven\Big(tail(tail(L))\Big)\bigg)</math>
##<math>reverse</math>:
##*<math>reverse([]) = []</math>
##*<math>reverse(L) = append\bigg(reverse\Big(tail(L)\Big),\; \Big[head(L)\Big]\bigg)</math>
##<math>map</math>:
##*<math>map(f,\; []) = []</math>
##*<math>map(f,\; L) = prefix\bigg(f\Big(head(L)\Big),\; map\Big(f,\; tail(L)\Big)\bigg)</math>
| |||