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

Вводная лекция
Структуры данных и базисные операции:
- Первая часть
- Вторая часть

Основы языка Haskell

Категория «Функциональное программирование» →

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

Ниже приводится описание метаязыка, используемого для определения структур данных (в абстрактном синтаксисе):

1. Декартово произведение. Если $C_{1},\,\dots ,\,C_{n}$ суть типы, а $C$ — тип, состоящий из множества $n$ -ок вида $\langle c_{1},\,\dots ,\,c_{n}\rangle$ , $c_{i}\in C_{i}$ , $i=1,n$ , то говорится, что $C$ — декартово произведение типов $C_{1},\,\dots ,\,C_{n}$ и обозначается как $C=C_{1}\times \dots \times C_{n}$ . При этом предполагается, что определены селекторы $s_{1},\,\dots ,\,s_{n}$ для типа $C$ , что записывается как $s_{1},\,\dots ,\,s_{n}=\operatorname {selectors} \;C$ .

Таким же образом записывается конструктор $g:g=\operatorname {constructor} \;C$ . Конструктор — это функция, имеющая тип $(C_{1}\to \dots (C_{n}\to C)\dots )$ , то есть для $c_{i}\in C_{i},\,i=1,n:g\;c_{1}\dots c_{n}=\langle c_{1},\,\dots ,\,c_{n}\rangle$ .

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

$\forall x\in C:\operatorname {constructor} \;C(s_{1},x)\dots (s_{n},x)=x$ .

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

$s_{i}(\operatorname {constructor} \;C\;c_{1}\dots c_{n})=c_{i}$

2. Размеченное объединение. Если $C_{1},\,\dots ,\,C_{n}$ — это типы, а $C$ — это тип, состоящий из объединения типов $C_{1},\,\dots ,\,C_{n}$ , при условии выполнения «размеченности», то $C$ называется размеченным объединением типов $C_{1},\,\dots ,\,C_{n}$ . Обозначается этот факт как $C=C_{1}+\dots +C_{n}$ . Условие размеченности обозначает, что если из $C$ взять какой-нибудь элемент $c_{i}$ , то однозначно определяется тип этого элемента $C_{i}$ . Размеченность можно определить при помощи предикатов $P_{1},\,\dots ,\,P_{n}$ таких, что:

$(x\in C)\land (x\in C_{i})\Rightarrow (P_{i}x=1)\land (\forall j\neq i:P_{j}x=0)$

Размеченное объединение гарантирует наличие таких предикатов. Этот факт указывается записью: $P_{1},\,\dots ,\,P_{n}=\operatorname {predicates} \;C$ . Ещё есть части типа, которые обозначаются так: $N_{1},\,\dots ,\,N_{n}=\operatorname {parts} \;C$ .

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

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

$\operatorname {List} (A)=\mathrm {NIL} +{\Big (}A\times \operatorname {List} (A){\Big )}$

$\mathrm {null} ,\mathrm {nonnull} =\operatorname {predicates} \;\operatorname {List} (A)$

$\mathrm {NIL} ,\mathrm {nonNIL} =\operatorname {parts} \;\operatorname {List} (A)$

$\mathrm {head} ,\mathrm {tail} =\operatorname {selectors} \;\operatorname {List} (A)$

$\mathrm {prefix} =\operatorname {constructor} \;\operatorname {List} (A)$

Глядя на это описание (скорее — определение) типа, можно описать внешний вид функций, обрабатывающих структуры типа $\operatorname {List} (A)$ :

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

Пример 18. Формальное определение типа $\operatorname {List\_str} (A)$ .

$\operatorname {List\_str} (A)=A+\operatorname {List} {\Big (}\operatorname {List\_str} (A){\Big )}$

$\mathrm {atom} ,\mathrm {nonAtom} =\operatorname {predicates} \;\operatorname {List\_str} (A)$

Функции над $\operatorname {List\_str} (A)$ должны иметь по крайней мере следующие клозы:

1° $A\to \operatorname {when} {\Big (}\operatorname {atom} (A){\Big )}$

2° $[\,]\to \operatorname {when} {\Big (}\operatorname {null} (L){\Big )}$

3° $(H:T)\to \operatorname {head} (L),\operatorname {tail} (L)$

3.1° $\operatorname {atom} {\Big (}\operatorname {head} (L){\Big )}$

3.2° $\operatorname {nonAtom} {\Big (}\operatorname {head} (L){\Big )}$

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

$\operatorname {Tree} (A)=A\times \operatorname {Forest} (A)$

$\operatorname {Forest} (A)=\operatorname {List} {\Big (}\operatorname {Tree} (A){\Big )}$

$\mathrm {root} ,\mathrm {listing} =\mathrm {selectors} \;\operatorname {Tree} (A)$

$\mathrm {ctree} =\operatorname {constructor} \;\operatorname {Tree} (A)$

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

$\operatorname {MTree} (A,B)=A\times \operatorname {MForest} (A,B)$

$\operatorname {MForest} (A,B)=\operatorname {List} {\Big (}\operatorname {Element} (A,B){\Big )}$

$\operatorname {Element} (A,B)=B\times \operatorname {MTree} (A,B)$

$\mathrm {mroot} ,\mathrm {mlist} =\mathrm {selectors} \;\operatorname {MTree} (A,B)$

$\mathrm {null} ,\mathrm {nonNull} =\operatorname {predicates} \;\operatorname {MForest} (A,B)$

$\mathrm {arc} ,\mathrm {mtree} =\mathrm {selectors} \;\operatorname {Element} (A,B)$

Утверждается, что любая функция, работающая с типом $\operatorname {MTree} (A,B)$ , может быть представлена только через упомянутые шесть операций независимо от того, как она реализована. Это утверждение можно проверить при помощи диаграммы (скорее, это гиперграф), на которой ясно видно, что к любой части типа $\operatorname {MTree} (A,B)$ можно «добраться», используя только эти шесть операций.

Для конструирования функций, обрабатывающих структуры данных $\operatorname {MTree}$ , необходимо ввести несколько дополнительных понятий и обозначений для них. Это делается для простоты. Начальная вершина, вершина $\operatorname {MForest}$ и вершина $\operatorname {MTree}$ (выходящая из $\operatorname {Element}$ ) обозначаются как $S_{0}$ , $S_{1}$ и $S_{2}$ соответственно. Для обработки этих вершин необходимы три функции — $f_{0}$ , $f_{1}$ и $f_{2}$ , причём $f_{0}$ — это начальная функция, а две последних — рекурсивные.

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

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

Функция $f_{1}$ получает следующие параметры:

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

f₁ A K L = g₁ A K  when null L

f₁ A K L = f₁ A (g₂ (f₂ A (arc (head L)) (mtree (tail L)) K) A (arc L) K) (tail L)  otherwise

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

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

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

f₂ A B T K = f₁ (mroot T) (g₃ A B K) (mlist T)

Необходимо отметить, что это общий вид функций для обработки структур данных $\operatorname {MTree}$ . Реализация дополнительных функций $g_{1}$ , $g_{2}$ и $g_{3}$ зависит от конкретной задачи. Теперь можно сконструировать и общий вид функции $f_{0}$ :

f₀ T = f₁ (root T) k (mlist T)

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

Для более глубокого закрепления методики конструирования функций можно рассмотреть конкретную реализацию функций работы с B-деревьями. Пусть для структуры данных $\mathrm {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) так делать нельзя.
-- В Лиспе есть возможность использовать деструктивное присваивание.
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 × sRight) 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