Основы функционального программирования/Конструирование функций

Лекции по функциональному программированию

1. Вводная лекция 2. Структуры данных и базисные операции 3. Структуры данных и базисные операции — 2 4. Основы языка Haskell 5. Служебные слова и синтаксис Haskell'а 6. Модули и монады в Haskell'е 7. Операции ввода/вывода в Haskell'е 8. Конструирование функций 9. Доказательство свойств функций 10. Формализация ФП на основе λ-исчисления 11. Трансформация программ

Для конструирования функций используются разные формализмы, среди которых синтаксически-ориентированное конструирование. Чтобы применять его, можно воспользоваться методом, в свое время предложенным Хоаром. Ниже приводится описание метаязыка, используемого для определения структур данных (в абстрактном синтаксисе):

Декартово произведение

Если $C_1, ..., C_n$ суть типы, а $C$ — тип, состоящий из множества $n$-ок вида <c1, ..., cn>, ci  Ci, i = 1,n, то говорится, что C — декартово произведение типов C1, ..., Cn и обозначается как C = C1  ...  Cn. При этом предполагается, что определены селекторы s1, ..., sn для типа C, что записывается как s1, ..., sn = selectors C.

Таким же образом записывается конструктор g: g = constructor C. Конструктор — это функция, имеющая тип (С1  ... (Cn  C) ... ), т.е. для ci  Ci, i = 1,n : g c1 ... cn = <c1, ..., cn>.

Будет считаться, что справедливо равенство:

x  C : constructor C (s1, x) ... (sn, x) = x

Это равенство называется аксиомой тектоничности. Кроме того, иногда эту аксиому записывают следующим образом:

si (constructor C c1 ... cn) = ci

Размеченное объединение

Если C1, ..., Cn — это типы, а C — это тип, состоящий из объединения типов C1, ..., Cn, при условии выполнения «размеченности», то C называется размеченным объединением типов C1, ..., Cn. Обозначается этот факт как C = C1 + ... + Cn. Условие размеченности обозначает, что если из C взять какой-нибудь элемент ci, то однозначно определяется тип этого элемента Ci. Размеченность можно определить при помощи предикатов P1, ..., Pn таких, что:

(x  C) & (x  Ci)  (Pi x = 1) & (j  i : Pj x = 0)

Размеченное объединение гарантирует наличие таких предикатов. Этот факт указывается записью: P1, ..., Pn = predicates C. Ещё есть части типа, которые обозначаются так: N1, ..., Nn = parts C.

Как видно, в представленном метаязыке используется два конструктора типов:  и +. Далее рассматриваются несколько примеров определения новых типов.

Пример 17. Формальное определение типа List (A).

List (A) = NIL + (A  List (A))
null, nonnull = predicates List (A)
NIL, nonNIL = parts List (A)
head, tail = selectors List (A)
prefix = constructor List (A)

Глядя на это описание (скорее — определение) типа, можно описать внешний вид функций, обрабатывающих структуры типа List (A): Каждая функция должна содержать как минимум два клоза, первый обрабатывает NIL, второй — nonNIL соответственно. Этим двум частям типа List (A) в абстрактной записи соответствуют селекторы [] и (H : T). Два клоза можно объединить в один с использованием охраны. В теле второго клоза (или второго выражения охраны) обработка элемента T (или tail (L)) выполняется той же самой функцией.

Пример 18. Формальное определение типа List_str (A).

List_str (A) = A + List (List_str (A))
atom, nonAtom = predicates List_str (A)

Функции над List_str (A) должны иметь по крайней мере следующие клозы:

1. A  when (atom (A))
2. []  when (null (L))
3. (H : T)  head (L), tail (L)
   1. atom (head (L))
   2. nonAtom (head (L))

Пример 19. Формальное определение деревьев и лесов с помеченными вершинами.

Tree (A) = A  Forest (A)
Forest (A) = List (Tree (A))
root, listing = selectors Tree (A)
ctree = constructor Tree (A)

Пример 20. Формально определение деревьев с помеченными вершинами и дугами.

MTree (A, B) = A  MForest (A, B)
MForest (A, B) = List (Element (A, B))
Element (A, B) = B  MTree (A, B)
mroot, mlist = selectors MTree (A, B)
null, nonNull = predicates MForest (A, B)
arc, mtree = selectors Element (A, B)

Утверждается, что любая функция, работающая с типом MTree (A, B), может быть представлена только через упомянутые шесть операций независимо от того, как она реализована. Это утверждение можно проверить при помощи диаграммы (скорее, это гиперграф), на которой ясно видно, что к любой части типа MTree (A, B) можно «добраться», используя только эти шесть операций. Для конструирования функций, обрабатывающих структуры данных MTree, необходимо ввести несколько дополнительных понятий и обозначений для них. Это делается для простоты. Начальная вершина, вершина MForest и вершина MTree (выходящая из Element) обозначаются как S0, S1 и S2 соответственно. Для обработки этих вершин необходимы три функции — f0, f1 и f2, причем f0 — это начальная функция, а две последних — рекурсивные.

Рисунок 3. Гиперграф для представления структуры MTree

Конструирование функции f0 выглядит просто — у этой функции один параметр T, который соответствует начальной вершине S0. Две другие функции сконструировать сложнее.

Функция f1 получает следующие параметры:

• A — метка вершины;
• K — параметр, содержащий результат обработки просмотренной части дерева;
• L — лес, который необходимо обработать.

f1 A K L = g1 A K when null L
f1 A K L = f1 A (g2 (f2 A (arc (head L)) (mtree (tail L)) K) A (arc L) K) (tail L) otherwise

Эта функция организует режим просмотра дерева «сначала в глубину».

Функция f2 получает следующие параметры (и это уже должно быть ясно из её вызова во втором клозе функции f1):

• A — метка вершины;
• B — метка дуги;
• T — поддерево для обработки;
• K — результат обработки просмотренной части дерева.

f2 A B T K = f1 (mroot T) (g3 A B K) (mlist T)

Необходимо отметить, что это общий вид функций для обработки структур данных MTree. Реализация дополнительных функций g1, g2 и g3 зависит от конкретной задачи. Теперь можно сконструировать и общий вид функции f0:

f0 T = f1 (root T) k (mlist T)

где k — это начальное значение параметра K.

Для более глубокого закрепления методики конструирования функций можно рассмотреть конкретную реализацию функций работы с B-деревьями. Пусть для структуры данных BTree существует набор базисных операций, а сами деревья представляются в виде списков (особой роли представление не играет). Базисные операции следующие:

1. cbtree A Left Right = [A, Left, Right]
2. ctree = []
3. root T = head T
4. left T = head (tail T)
5. right T = head (tail (tail T))
6. empty T = (T == [])

Пример 21. Функция insert для вставки элемента в дерево.

insert (A:L) T = cbtree (A:L) ctree ctree when (empty T)
insert (A:L) T = cbtree (root T) (insert (A:L) (left T)) (right T) when (A < head (root T))
insert (A:L) T = cbtree (A:(L:tail (root T))) (left T) (right T) when (A == head (root T))
insert (A:L) T = cbtree (root T) (left T) (insert (A:L) (right T)) otherwise

Это реализация на абстрактном уровне.

Пример 22. Функция access для поиска элементов в B-дереве.

access A Emptic = []
access A ((A1:L)LeftRight) = access A Left when (A < A1)
access A ((A1:L)LeftRight) = access A Right when (A > A1)
access A ((A:L)LeftRight) = L
access A (RootLeftRight) = access A Right otherwise

В этом примере приведено две новых конструкции — абстрактный элемент Emptic, представляющий собой, по сути, пустое дерево, а также знак , при помощи которого абстрагируется декартово произведение, которое используется здесь вместо списочного представления. Но надо помнить, что это только абстрактный функциональный язык.

В представленных двух примерах существует одна проблема. При использовании написанных функций совершается огромное количество лишних копирований из одного места в памяти в другое. По сути дела это воссоздание нового дерева с новыми элементами (речь идет о функции insert). Этого можно избежать при использовании деструктивного присваивания.

Упражнения

1. Сконструировать функцию insert для вставки элемента в B-дерево, использующую деструктивное присваивание.

Ответы для самопроверки

1. Один из возможных вариантов функции insert с деструктивным присваиванием:

--«Псевдо-функции» для деструктивного присваивания. В строгом функциональном языке (Haskell)
--так делать нельзя. В Lisp’е есть возможность использовать деструктивное присваивание.
replace_root A T – функция добавления элемента в корень дерева
replace_left K (RootEmpticRight) => (Root(KEmpticEmptic)Right)
replace_right K (RootLeftEmptic) => (RootLeft(KEmpticEmptic))

-- Функция insert
insert K Emptic = cbtree K ctree ctree
insert (A:L) ((A1:L1)LeftRight) = insert (A:L) Left when ((A < A1) & nonEmpty Left)
insert (A:L) ((A1:L1)EmpticRight) = replace_left (A:L) ((A1:L1)EmpticRight) when (A < A1)
insert (A:L) ((A1:L1)LeftRight) = insert (A:L) Right when ((A > A1) & nonEmpty Right)
insert (A:L) ((A1:L1)LeftEmptic) = replace_right (A:L) ((A1:L1)LeftEmptic) when (A > A1)
insert A T = replace_root A T otherwise