СТРУКТУРЫ ДАННЫХ И БАЗИСНЫЕ ОПЕРАЦИИ

Как уже говорилось в первой лекции, основой функциональной парадигмы программирования в большей мере являются такие направления развития математической мысли, как комбинаторная логика и l-исчисление. В свою очередь последнее более тесно связано с функциональным программированием, и именно l-исчисление называют теоретическими основами функционального программирования.
Для того, чтобы рассматривать теоретические основы функционального программирования, необходимо в первую очередь ввести некоторые соглашения, описать обозначения и построить некоторую формальную систему.
Пусть заданы объекты некоторого первичного типа A. Сейчас совершенно не важно, что именно представляют собой эти выделенные объекты. Обычно считается, что на этих объектах определён набор базисных операций и предикатов. По традиции, которая пошла ещё от МакКарти (автор Lisp'а), такие объекты называются атомами. В теории фактический способ реализации базисных операций и предикатов совершенно не важен, их существование просто постулируется. Однако каждый конкретный функциональный язык реализует базисный набор по-своему. В качестве базисных операций традиционно (и в первую очередь это объясняется теоретической необходимостью) выделяются следующие три:
1. Операция создания пары — prefix (x, y) = x : y = [x | y]. Эта операция также называется конструктором или составителем.
2. Операция отсечения головы — head (x) = h (x). Это первая селективная операция.
3. Операция отсечения хвоста — tail (x) = t (x). Это вторая селективная операция.
Селективные операции отсечения головы и хвоста также называют просто селекторами. Выделенные операции связаны друг с другом следующими тремя аксиомами:
1. head (x : y) = x
2. tail (x : y) = y
3. prefix (head (x : y), tail (x : y)) = (x : y)
Всё множество объектов, которые можно сконструировать из объектов первичного типа в результате произвольного применения базисных операций, носит название множество S-выражений (обозначение — Sexpr (A)). Например:
a1 : (a2 : a3) in Sexpr
Для дальнейших исследований вводится фиксированный атом, который также принадлежит первичному типу A. Этот атом в дальнейшем будет называться "пустым списком" и обозначаться символами [] (хотя в разных языках функционального програмирования могут существовать свои обозначения для пустого списка). Теперь можно определить то, чем собственно занимается функциональное программирование — собственное подмножество List (A) Sexpr (A), которое называется "список над A".
Определение:
1°. Пустой список [] in List (A)
2°. x in A & y in List (A) => x : y in List (A)
Главное свойство списка:
x in List (A) & x =/= [] => head (x) in A; tail (x) in List (A).
Для обозначения списка из n элементов можно употреблять множество различных нотаций, однако здесь будет использоваться только такая: [a1, a2, ..., an]. Применяя к такому списку определенным образом операции head и tail можно добраться до любого элемента списка, т.к.:
head ([a1, a2, ..., an]) = a1
tail ([a1, a2, ..., an]) = [a2, ..., an] (при n > 0).
Кроме списков вводится еще один тип данных, который носит название "списочная структура над A" (обозначение — List_str (A)), при этом можно построить следующую структуру отношений: List (A) List_str (A) Sexpr (A).
Определение списочной структуры выглядит следующим образом:
Определение:
1°. a in A => a in List_str (A)
2°. List (List_str (A)) in List_str (A)
Т.е. видно, что списочная структура — это список, элементами которого могут быть как атомы, так и другие списочные структуру, в том числе и обыкновенные списки. Примером списочной структуры, которая в тоже время не является простым списком, может служить следующее выражение: [a1, [a2, a3, [a4]], a5]. Для списочных структур вводится такое понятие, как уровень вложенности.

Несколько слов о программной реализации

Пришло время уделить некоторое внимание рассмотрению программной реализации списков и списочных структур. Это необходимо для более тонкого понимания того, что происходит во время работы функциональной программы, как на каком-либо реализованном функциональном языке, так и на абстрактном языке.
Каждый объект занимает в памяти машины какое-то место. Однако атомы представляют собой указатели (адреса) на ячейки, в которых содержатся объекты.
Адрес ячейки, которая содержит указатели на x и y, и есть объект z. Как видно на рисунке, пара представлена двумя адресами — указатель на голову и указатель на хвост. Традиционно первый указатель (на рисунке выделен голубым цветом) называется a-поле, а второй указатель (на рисунке — зеленоватый) называется d-поле.
Для удобства представления объекты, на которые указывают a- и d-поля, в дальнейшем будут записываться непосредственно в сами поля. Пустой список будет обозначаться перечеркнутым квадратом (указатель ни на что не указывает).
Остается отметить, что операция prefix требует расхода памяти, ибо при конструировании пары выделяется память под указатели. С другой стороны обе операции head и tail не требуют памяти, они просто возвращают адрес, который содержится соответственно в a- или d-поле.

Примеры

Пример 5. Операция prefix.
Для начала необходимо рассмотреть более подробно работу операции prefix.
Пояснение работы будет проведено на трёх более или менее общих примерах:
1°. prefix (a1, a2) = a1: a2 (при этом результат не является элементом List_str (A)).
2°. prefix (a1, [b1, b2]) = [a1, b1, b2]
3°. prefix ([a1, a2], [b1, b2]) = [[a1, a2], b1, b2]
Пример 6. Функция определения длины списка Length.
Перед тем, как собственно начать реализовывать функцию Length, необходимо понять, что она должна возвращать. Понятийное определение результата функции Length может звучать как "количество элементов в списке, который передан функции в качестве параметра". Здесь возникает два случая: функции передан пустой список и функции передан непустой список. С первым случаем все ясно — результат должен быть нулевым. Во втором случае задачу можно разбить на две подзадачи, путем разделения переданного списка на голову и хвост при помощи операций head и tail.
Осмысленно, что операция head возвращает первый элемент списка, а операция tail возвращает список из оставшихся элементов. Пусть известна длина списка, полученного при помощи операции tail, тогда длина исходного списка будет равна известной длина, увеличенной на единицу. В этом случае можно легко записать определение самой функции Length:
Length ([]) = 0
Length (L) = 1 + Length (tail (L))

Пример 7. Функция слияния двух списков Append.
Реализовать функцию слияния (или сцепления) списков можно многими способами. Первое, что приходит в голову — деструктивное присваивание. Т.е. заменить указатель на [] в конце первого списка на указатель на голову второго списка и тем самым получить результат в первом списке. Однако здесь изменяется сам первый список. Такие приёмы запрещены в функциональном программировании (хотя, в очередной раз необходимо заметить, что в некоторых функциональных языках всё-таки есть такая возможность).
Второй способ состоит в копировании верхнего уровня первого списка и помещении в последний указатель копии ссылку на первый элемент второго списка. Этот способ хорош с точки зрения деструктивности (не выполняет деструктивных и побочных действий), однако требует дополнительных затрат памяти и времени.
Append ([], L2) = L2
Append (L1, L2) = prefix (head (L1), Append (tail (L1), L2))

Последний пример показывает, как при помощи постепенного конструирования можно построить новый список, который равен сцепке двух заданных.
Упражнения
1. Построить функции, вычисляющие N-ый элемент следующих рядов:
a. an = xn
b. an = Summ i, (i = 1,n)
c. an = Summ (Summ i), (j = 1,n i = 1,j)
d. an = Summ n-i, (i = 1,p)
e. an = en = Summ (ni / i!), (i = 0,infinity)
2. Объяснить результаты операции prefix, показанные в примере 5. Для объяснения можно воспользоваться графическим методом.
3. Объяснить результат работы функции Append (пример 7). Пояснить, почему функция не является деструктивной.
4. Построить функции, работающие со списками:
a. GetN — функция вычленения N-ого элемента из заданного списка.
b. ListSumm — функция сложения элементов двух списков. Возвращает список, составленный из сумм элементов списков-параметров. Учесть, что переданные списки могут быть разной длины.
c. OddEven — функция перестановки местами соседних чётных и нечётных элементов в заданном списке.
d. Reverse — функция, обращающая список (первый элемент списка становится последним, второй — предпоследним, и так далее до последнего элемента).
e. Map — функция применения другой переданной в качестве параметра функции ко всем элементам заданного списка.
Ответы для самопроверки
Большинство ответов для самопроверки представляют собой лишь одни из
возможных вариантов (в большинстве случаев наиболее интуитивные).
1. Функции, вычисляющие N-ый элемент рядов:
a. Power:
Power (X, 0) = 1
Power (X, N) = X * Power (X, N - 1)

b. Summ_T:
Summ_T (1) = 1
Summ_T (N) = N + Summ_T (N - 1)

c. Summ_P:
Summ_P (1) = 1
Summ_P (N) = Summ_T (N) + Summ_P (N - 1)

d. Summ_Power:
Summ_Power (N, 0) = 1
Summ_Power (N, P) = (1 / Power (N, P)) + Summ_Power (N, P - 1)

e. Exponent:
Exponent (N, 0) = 1
Exponent (N, P) = (Power (N, P) / Factorial (P)) + Exponent (N, P - 1)

Factorial (N) = N * Factorial (N - 1)

2. Объяснение работы операции prefix можно легко провести в три приёма (равно так же, как и приведено в примере). Для того чтобы не загромождать объяснения, здесь наряду с функциональной записью операции prefix также используется инфиксная запись посредством символа двоеточия.
a. Первый пример работы операции — определение самой операции.
Рассматривать его нет смысла, ибо операция prefix определяется именно таким образом.
b. prefix (a1, [b1, b2]) = prefix (a1, b1 : (b2 : [])) = a1 : (b1 : (b2 : [])) = [a1, b1, b2]
(Эти преобразование проведены по определению списка).
c. prefix ([a1, a2], [b1, b2]) = prefix ([a1, a2], b1 : (b2 : [])) = ([a1, a2]) : (b1 : (b2 : [])) = [[a1, a2], b1, b2].
3. В качестве примера работы функции Append рассмотрим сцепку двух списков, каждый из которых состоит из двух элементов: [a, b] и [c, d].
Опять же для того, чтобы не загромождать объяснение, для записи операции prefix используется инфиксная форма. Для более полного понимания приведенного объяснения необходимо помнить определение списка.
Append ([a, b], [c, d]) = a : Append ([b], [c, d]) = a : (b : Append ([], [c, d])) = a : (b : ([c, d])) = a : (b : (c : (d : []))) = [a, b, c, d].
4. Функции, работающие со списками:
a. GetN:
GetN (N, []) = _
GetN (1, H:T) = H
GetN (N, H:T) = GetN (N - 1, T)

b. ListSumm:
ListSumm ([], L) = L
ListSumm (L, []) = L
ListSumm (H1:T1, H2:T2) = prefix ((H1 + H2), ListSumm (T1, T2))

c. OddEven:
OddEven ([]) = []
OddEven ([X]) = [X]
OddEven (H1:[H2:T]) = prefix (prefix (H2, H1), OddEven (T))

d. Reverse:
Reverse ([]) = []
Reverse (H:T) = Append (Reverse (T), [H])

e. Map:
Map (F, []) = []
Map (F, H:T) = prefix (F (H), Map (F, T))