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

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

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

• Основы языка Haskell
  
  • Служебные слова и синтаксис
    
  • Модули и монады
    
  • Ввод-вывод
    
  • Другие статьи и учебники по 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$ — лес, который необходимо обработать.

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

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

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

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

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

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

f0 T = f1 (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