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

Обработаны формулы, вставлены ссылки, прочие правки.
(Обработаны формулы, вставлены ссылки, прочие правки.)
__TOC__
 
Для конструирования [[w:Функция (математика)|функций]] используются разные формализмы, среди которых синтаксически-ориентированное конструирование. Чтобы применять его, можно воспользоваться методом, в свое время предложенным Хоаром. Ниже приводится описание метаязыка[[w:Хоар, используемогоЧарльз дляЭнтони определения структур данных (в абстрактном синтаксисе):Ричард|Хоаром]].
 
Ниже приводится описание [[w:Метаязык|метаязыка]], используемого для определения [[w:Структура данных|структур данных]] (в абстрактном [[w:Синтаксис (программирование)|синтаксисе]]):
===Декартово произведение===
Если <math>C_1, ..., C_n</math> суть типы, а <math>C</math> — тип, состоящий из множества <math>n</math>-ок вида <c1, ..., cn>, ci  Ci, i = 1,n, то говорится, что C — декартово произведение типов C1, ..., Cn и обозначается как C = C1  ...  Cn. При этом предполагается, что определены селекторы s1, ..., sn для типа C, что записывается как s1, ..., sn = selectors C.
 
'''1. [[w:Прямое произведение|Декартово произведение]].''' Если <math>C_1,\, \dots,\, C_n</math> суть [[w:Тип данных|типы]], а <math>C</math> — тип, состоящий из [[w:Множество|множества]] <math>n</math>-ок вида <math>\langle c_1,\, \dots,\, c_n \rangle</math>, <math>c_i \in C_i</math>, <math>i = 1,n</math>, то говорится, что <math>C</math> — декартово произведение типов <math>C_1,\, \dots,\, C_n</math> и обозначается как <math>C = C_1 \times \dots \times C_n</math>. При этом предполагается, что определены селекторы <math>s_1,\, \dots,\, s_n</math> для типа <math>C</math>, что записывается как <math>s_1,\, \dots,\, s_n = \operatorname{selectors}\; C</math>.
Таким же образом записывается конструктор g: g = constructor C. Конструктор — это функция, имеющая тип (С1  ... (Cn  C) ... ), т.е. для ci  Ci, i = 1,n : g c1 ... cn = <c1, ..., cn>.
 
Таким же образом записывается конструктор <math>g: g = \operatorname{constructor}\; C</math>. Конструктор — это функция, имеющая тип <math>(C_1 \to \dots (C_n \to C) \dots )</math>, то есть для <math>c_i \in C_i,\, i = 1,n : g\; c_1 \dots c_n = \langle c_1,\, \dots,\, c_n \rangle</math>.
 
Будет считаться, что справедливо равенство:
 
<math>\forall x \in C : \operatorname{constructor}\; C (s1s_1, x) ...\dots (sns_n, x) = x</math>.
 
Это равенство называется [[w:Аксиома|аксиомой]] тектоничности. Кроме того, иногда эту аксиому записывают следующим образом:
 
si<math>s_i (\operatorname{constructor}\; C\; c1c_1 ...\dots cnc_n) = cic_i</math>
 
'''2. Размеченное объединение.''' Если <math>C_1,\, \dots,\, C_n</math> — это типы, а <math>C</math> — это тип, состоящий из объединения типов <math>C_1,\, \dots,\, C_n</math>, при условии выполнения «размеченности», то <math>C</math> называется размеченным объединением типов <math>C_1,\, \dots,\, C_n</math>. Обозначается этот факт как <math>C = C_1 + \dots + C_n</math>. Условие размеченности обозначает, что если из <math>C</math> взять какой-нибудь элемент <math>c_i</math>, то однозначно определяется тип этого элемента <math>C_i</math>. Размеченность можно определить при помощи [[w:Предикат|предикатов]] <math>P_1,\, \dots,\, P_n</math> таких, что:
===Размеченное объединение===
Если C1, ..., Cn — это типы, а C — это тип, состоящий из объединения типов C1, ..., Cn, при условии выполнения «размеченности», то C называется размеченным объединением типов C1, ..., Cn. Обозначается этот факт как C = C1 + ... + Cn. Условие размеченности обозначает, что если из C взять какой-нибудь элемент ci, то однозначно определяется тип этого элемента Ci. Размеченность можно определить при помощи предикатов P1, ..., Pn таких, что:
 
<math>(x \in C) &\land (x \in CiC_i) \Rightarrow (PiP_i x = 1) &\land (j\forall j \neq i : PjP_j x = 0)</math>
 
Размеченное объединение гарантирует наличие таких предикатов. Этот факт указывается записью: P1<math>P_1,\, ...\dots,\, PnP_n = \operatorname{predicates}\; C</math>. Ещё есть части типа, которые обозначаются так: N1<math>N_1,\, ...\dots,\, NnN_n = \operatorname{parts}\; C</math>.
 
Как видно, в представленном метаязыке используется два конструктора типов: <math>\times</math> и <math>+</math>. Далее рассматриваются несколько примеров определения новых типов.
 
'''Пример 17. Формальное определение типа <math>\operatorname{List} (A)</math>.'''
 
<math>\operatorname{List} (A) = \mathrm{NIL} + \Big( A \times \operatorname{List} (A) \Big)</math>
null, nonnull = predicates List (A)
NIL, nonNIL = parts List (A)
head, tail = selectors List (A)
prefix = constructor List (A)
 
<math>\mathrm{null}, \mathrm{nonnull} = \operatorname{predicates}\; \operatorname{List} (A)</math>
Глядя на это описание (скорее — определение) типа, можно описать внешний вид функций, обрабатывающих структуры типа List (A):
Каждая функция должна содержать как минимум два клоза, первый обрабатывает NIL, второй — nonNIL соответственно. Этим двум частям типа List (A) в абстрактной записи соответствуют селекторы [] и (H : T). Два клоза можно объединить в один с использованием охраны. В теле второго клоза (или второго выражения охраны) обработка элемента T (или tail (L)) выполняется той же самой функцией.
 
<math>\mathrm{NIL}, \mathrm{nonNIL} = \operatorname{parts}\; \operatorname{List} (A)</math>
'''Пример 18. Формальное определение типа List_str (A).'''
 
<math>\mathrm{head}, \mathrm{tail} = \operatorname{selectors}\; \operatorname{List} (A)</math>
List_str (A) = A + List (List_str (A))
atom, nonAtom = predicates List_str (A)
 
<math>\mathrm{prefix} = \operatorname{constructor}\; \operatorname{List} (A)</math>
Функции над List_str (A) должны иметь по крайней мере следующие клозы:
 
Глядя на это описание (скорее — определение) типа, можно описать внешний вид функций, обрабатывающих структуры типа <math>\operatorname{List} (A)</math>:
#A  when (atom (A))
#[]  when (null (L))
#(H : T)  head (L), tail (L)
##atom (head (L))
##nonAtom (head (L))
 
Каждая функция должна содержать как минимум два [[w:Клоз|клоза]], первый обрабатывает <math>\mathrm{NIL}</math>, второй — <math>\mathrm{nonNIL}</math> соответственно. Этим двум частям типа <math>\operatorname{List} (A)</math> в абстрактной записи соответствуют селекторы <math>[\,]</math> и <math>(H : T)</math>. Два клоза можно объединить в один с использованием охраны. В теле второго клоза (или второго выражения охраны) обработка элемента <math>T</math> (или <math>\operatorname{tail}(L)</math>) выполняется той же самой функцией.
'''Пример 19. Формальное определение деревьев и лесов с помеченными вершинами.'''
 
'''Пример 18. Формальное определение типа <math>\operatorname{List\_str} (A)</math>.'''
Tree (A) = A  Forest (A)
 
Forest (A) = List (Tree (A))
<math>\operatorname{List\_str} (A) = A + \operatorname{List} \Big( \operatorname{List\_str} (A) \Big)</math>
root, listing = selectors Tree (A)
 
ctree = constructor Tree (A)
<math>\mathrm{atom}, \mathrm{nonAtom} = \operatorname{predicates}\; \operatorname{List\_str} (A)</math>
 
Функции над <math>\operatorname{List\_str} (A)</math> должны иметь по крайней мере следующие клозы:
 
1° <math>A \to \operatorname{when} \Big( \operatorname{atom} (A) \Big)</math>
 
2° <math>[\,] \to \operatorname{when} \Big( \operatorname{null} (L) \Big)</math>
 
3° <math>(H : T) \to \operatorname{head} (L), \operatorname{tail} (L)</math>
 
3.1° <math>\operatorname{atom} \Big( \operatorname{head} (L) \Big)</math>
 
3.2° <math>\operatorname{nonAtom} \Big( \operatorname{head} (L) \Big)</math>
 
'''Пример 19. Формальное определение [[w:Дерево (теория графов)|деревьев]] и лесов с помеченными вершинами.'''
 
<math>\operatorname{Tree} (A) = A \times \operatorname{Forest} (A)</math>
 
<math>\operatorname{Forest} (A) = \operatorname{List} \Big( \operatorname{Tree} (A) \Big)</math>
 
<math>\mathrm{root}, \mathrm{listing} = \mathrm{selectors}\; \operatorname{Tree} (A)</math>
 
<math>\mathrm{ctree} = \operatorname{constructor}\; \operatorname{Tree} (A)</math>
 
'''Пример 20. Формально определение деревьев с помеченными вершинами и дугами.'''
 
<math>\operatorname{MTree} (A, B) = A \times \operatorname{MForest} (A, B)</math>
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)
 
<math>\operatorname{MForest} (A, B) = \operatorname{List} \Big( \operatorname{Element} (A, B) \Big)</math>
Утверждается, что любая функция, работающая с типом MTree (A, B), может быть представлена только через упомянутые шесть операций независимо от того, как она реализована. Это утверждение можно проверить при помощи диаграммы (скорее, это гиперграф), на которой ясно видно, что к любой части типа MTree (A, B) можно «добраться», используя только эти шесть операций.
 
Для конструирования функций, обрабатывающих структуры данных MTree, необходимо ввести несколько дополнительных понятий и обозначений для них. Это делается для простоты. Начальная вершина, вершина MForest и вершина MTree (выходящая из Element) обозначаются как S0, S1 и S2 соответственно. Для обработки этих вершин необходимы три функции — f0, f1 и f2, причем f0 — это начальная функция, а две последних — рекурсивные.
<math>\operatorname{Element} (A, B) = B \times \operatorname{MTree} (A, B)</math>
 
<math>\mathrm{mroot}, \mathrm{mlist} = \mathrm{selectors}\; \operatorname{MTree} (A, B)</math>
 
<math>\mathrm{null}, \mathrm{nonNull} = \operatorname{predicates}\; \operatorname{MForest} (A, B)</math>
 
<math>\mathrm{arc}, \mathrm{mtree} = \mathrm{selectors}\; \operatorname{Element} (A, B)</math>
 
Утверждается, что любая функция, работающая с типом <math>\operatorname{MTree} (A, B)</math>, может быть представлена только через упомянутые шесть операций независимо от того, как она реализована. Это утверждение можно проверить при помощи диаграммы (скорее, это гиперграф), на которой ясно видно, что к любой части типа <math>\operatorname{MTree} (A, B)</math> можно «добраться», используя только эти шесть операций.
 
Для конструирования функций, обрабатывающих структуры данных <math>\operatorname{MTree}</math>, необходимо ввести несколько дополнительных понятий и обозначений для них. Это делается для простоты. Начальная вершина, вершина <math>\operatorname{MForest}</math> и вершина <math>\operatorname{MTree}</math> (выходящая из <math>\operatorname{Element}</math>) обозначаются как <math>S_0</math>, <math>S_1</math> и <math>S_2</math> соответственно. Для обработки этих вершин необходимы три функции — <math>f_0</math>, <math>f_1</math> и <math>f_2</math>, причём <math>f_0</math> — это начальная функция, а две последних — рекурсивные.
Рисунок 3. Гиперграф для представления структуры <math>\operatorname{MTree}</math>
 
Конструирование функции f0<math>f_0</math> выглядит просто — у этой функции один параметр <math>T</math>, который соответствует начальной вершине S0<math>S_0</math>. Две другие функции сконструировать сложнее.
 
Функция f1<math>f_1</math> получает следующие параметры:
 
* <math>A</math> — метка вершины;
* <math>K</math> — параметр, содержащий результат обработки просмотренной части дерева;
* <math>L</math> — лес, который необходимо обработать.
 
f1<code>f<sub>1</sub> A K L = g1g<sub>1</sub> A K when null L</code>
 
f1 A K L = f1 A (g2 (f2 A (arc (head L)) (mtree (tail L)) K) A (arc L) K) (tail L) otherwise
<code>f<sub>1</sub> A K L = f<sub>1</sub> A (g<sub>2</sub> (f<sub>2</sub> A (arc (head L)) (mtree (tail L)) K) A (arc L) K) (tail L) otherwise</code>
 
Эта функция организует режим просмотра дерева «сначала в глубину».
 
Функция f2<math>f_2</math> получает следующие параметры (и это уже должно быть ясно из её вызова во втором клозе функции f1<math>f_1</math>):
 
* <math>A</math> — метка вершины;
* <math>B</math> — метка дуги;
* <math>T</math> — поддерево для обработки;
* <math>K</math> — результат обработки просмотренной части дерева.
 
<code>f<sub>2</sub> A B T K = f<sub>1</sub> (mroot T) (g<sub>3</sub> A B K) (mlist T)</code>
 
Необходимо отметить, что это общий вид функций для обработки структур данных <math>\operatorname{MTree}</math>. Реализация дополнительных функций <math>g_1</math>, <math>g_2</math> и <math>g_3</math> зависит от конкретной задачи. Теперь можно сконструировать и общий вид функции <math>f_0</math>:
 
<code>f<sub>0</sub> T = f<sub>1</sub> (root T) k (mlist T)</code>
 
где <math>k</math> — это начальное значение параметра <math>K</math>.
 
Для более глубокого закрепления методики конструирования функций можно рассмотреть конкретную реализацию функций работы с [[w:B-дерево|B-деревьями]]. Пусть для структуры данных <math>\mathrm{BTree}</math> существует набор базисных операций, а сами деревья представляются в виде списков (особой роли представление не играет). Базисные операции следующие:
*A — метка вершины;
*B — метка дуги;
*T — поддерево для обработки;
*K — результат обработки просмотренной части дерева.
 
1° <code>cbtree A Left Right = [A, Left, Right]</code>
f2 A B T K = f1 (mroot T) (g3 A B K) (mlist T)
 
2° <code>ctree = []</code>
Необходимо отметить, что это общий вид функций для обработки структур данных MTree. Реализация дополнительных функций g1, g2 и g3 зависит от конкретной задачи. Теперь можно сконструировать и общий вид функции f0:
 
f0 T = f1 (<code>root T) k= (mlisthead T)</code>
 
4° <code>left T = head (tail T)</code>
где k — это начальное значение параметра K.
 
5° <code>right T = head (tail (tail T))</code>
Для более глубокого закрепления методики конструирования функций можно рассмотреть конкретную реализацию функций работы с B-деревьями. Пусть для структуры данных BTree существует набор базисных операций, а сами деревья представляются в виде списков (особой роли представление не играет). Базисные операции следующие:
 
6° <code>empty T = (T == [])</code>
#cbtree A Left Right = [A, Left, Right]
#ctree = []
#root T = head T
#left T = head (tail T)
#right T = head (tail (tail T))
#empty T = (T == [])
 
'''Пример 21. Функция <code>insert</code> для вставки элемента в дерево.'''
 
<code>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</code>
 
Это реализация на абстрактном уровне.
 
'''Пример 22. Функция <code>access</code> для поиска элементов в B-дереве.'''
 
<code>access A Emptic = []
access A ((A1:L)LeftRight × Left × Right) = access A Left when (A <&lt; A1)
access A ((A1:L)LeftRight × Left × Right) = access A Right when (A >&gt; A1)
access A ((A:L)LeftRight × Left × Right) = L
access A (RootLeftRightRoot × Left × Right) = access A Right otherwise</code>
 
В этом примере приведено две новых конструкции — абстрактный элемент <code>Emptic</code>, представляющий собой, по сути, пустое дерево, а также знак <code>×</code>, при помощи которого абстрагируется декартово произведение, которое используется здесь вместо списочного представления. Но надо помнить, что это только абстрактный функциональный язык.
 
В представленных двух примерах существует одна проблема. При использовании написанных функций совершается огромное количество лишних копирований из одного места в памяти в другое. По сути дела это воссоздание нового дерева с новыми элементами (речь идет о функции <code>insert</code>). Этого можно избежать при использовании деструктивного присваивания.
 
== Упражнения ==
 
#1. Сконструировать функцию <code>insert</code> для вставки элемента в B-дерево, использующую деструктивное присваивание.
 
== Ответы для самопроверки ==
 
#1. Один из возможных вариантов функции <code>insert</code> с деструктивным присваиванием:
 
<code>-- «Псевдо-функции» для деструктивного присваивания. В строгом функциональном языке (Haskell)
-- В строгом функциональном языке (Haskell) так делать нельзя.
--так делать нельзя. В Lisp’е есть возможность использовать деструктивное присваивание.
-- В Лиспе есть возможность использовать деструктивное присваивание.
replace_root A T – функция добавления элемента в корень дерева
replace_left K (RootEmpticRightRoot × Emptic × Right) => (RootRoot × (KEmpticEmpticK × Emptic × Emptic)Right × Right)
replace_right K (RootLeftEmpticRoot × Left × Emptic) => (RootLeftRoot × Left × (KEmpticEmpticK × Emptic × Emptic))
-- Функция insert
insert K Emptic = cbtree K ctree ctree
insert (A:L) ((A1:L1)LeftRight × Left × Right) = insert (A:L) Left when ((A < A1) & nonEmpty Left)
insert (A:L) ((A1:L1)EmpticRight × Emptic × Right) = replace_left (A:L) ((A1:L1)EmpticRight × Emptic × sRight) when (A < A1)
insert (A:L) ((A1:L1)LeftRight × Left × Right) = insert (A:L) Right when ((A > A1) & nonEmpty Right)
insert (A:L) ((A1:L1)LeftEmptic × Left × Emptic) = replace_right (A:L) ((A1:L1)LeftEmptic × Left × Emptic) when (A > A1)
insert A T = replace_root A T otherwise</code>