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

Материал из Викиучебника

< Основы функционального программирования

Перейти к: навигация, поиск

Основы функционального программирования

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

Основы языка 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)$ :

Каждая функция должна содержать как минимум два клоза, первый обрабатывает $NIL$ , второй — $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-деревьями. Пусть для структуры данных $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

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

Материал из Викиучебника

Содержание

[править] Упражнения

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

Просмотры

Личные инструменты

Навигация

участие

Поиск

Инструменты

Печать/Экспорт