Основы функционального программирования/Конструирование функций: различия между версиями
Содержимое удалено Содержимое добавлено
Нет описания правки |
Обработаны формулы, вставлены ссылки, прочие правки. |
||
Строка 2:
__TOC__
Для конструирования [[w:Функция (математика)|функций]] используются разные формализмы, среди которых синтаксически-ориентированное конструирование. Чтобы применять его, можно воспользоваться методом, в свое время предложенным
Ниже приводится описание [[w:Метаязык|метаязыка]], используемого для определения [[w:Структура данных|структур данных]] (в абстрактном [[w:Синтаксис (программирование)|синтаксисе]]):
'''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>.
Таким же образом записывается конструктор <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
Это равенство называется [[w:Аксиома|аксиомой]] тектоничности. Кроме того, иногда эту аксиому записывают следующим образом:
'''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> таких, что:
<math>(x
Размеченное объединение гарантирует наличие таких предикатов. Этот факт указывается записью:
Как видно, в представленном метаязыке используется два конструктора типов:
'''Пример 17. Формальное определение типа <math>\operatorname{List} (A)</math>.'''
<math>\mathrm{null}, \mathrm{nonnull} = \operatorname{predicates}\; \operatorname{List} (A)</math>
<math>\mathrm{NIL}, \mathrm{nonNIL} = \operatorname{parts}\; \operatorname{List} (A)</math>
<math>\mathrm{head}, \mathrm{tail} = \operatorname{selectors}\; \operatorname{List} (A)</math>
<math>\mathrm{prefix} = \operatorname{constructor}\; \operatorname{List} (A)</math>
Глядя на это описание (скорее — определение) типа, можно описать внешний вид функций, обрабатывающих структуры типа <math>\operatorname{List} (A)</math>:
Каждая функция должна содержать как минимум два [[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>) выполняется той же самой функцией.
'''Пример 18. Формальное определение типа <math>\operatorname{List\_str} (A)</math>.'''
<math>\operatorname{List\_str} (A) = A + \operatorname{List} \Big( \operatorname{List\_str} (A) \Big)</math>
<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{MForest} (A, B) = \operatorname{List} \Big( \operatorname{Element} (A, B) \Big)</math>
<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>
Конструирование функции
Функция
* <math>A</math> — метка вершины;
* <math>K</math> — параметр, содержащий результат обработки просмотренной части дерева;
* <math>L</math> — лес, который необходимо обработать.
<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>
Эта функция организует режим просмотра дерева «сначала в глубину».
Функция
* <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> существует набор базисных операций, а сами деревья представляются в виде списков (особой роли представление не играет). Базисные операции следующие:
1° <code>cbtree A Left Right = [A, Left, Right]</code>
2° <code>ctree = []</code>
4° <code>left T = head (tail T)</code>
5° <code>right T = head (tail (tail T))</code>
6° <code>empty T = (T == [])</code>
'''Пример 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)
access A ((A1:L)
access A ((A:L)
access A (
В этом примере приведено две новых конструкции — абстрактный элемент <code>Emptic</code>, представляющий собой, по сути, пустое дерево, а также знак
В представленных двух примерах существует одна проблема. При использовании написанных функций совершается огромное количество лишних копирований из одного места в памяти в другое. По сути дела это воссоздание нового дерева с новыми элементами (речь идет о функции <code>insert</code>). Этого можно избежать при использовании деструктивного присваивания.
== Упражнения ==
== Ответы для самопроверки ==
<code>-- «Псевдо-функции» для деструктивного присваивания.
-- В строгом функциональном языке (Haskell) так делать нельзя. --
replace_root A T – функция добавления элемента в корень дерева
replace_left K (
replace_right K (
-- Функция insert
insert K Emptic = cbtree K ctree ctree
insert (A:L) ((A1:L1)
insert (A:L) ((A1:L1)
insert (A:L) ((A1:L1)
insert (A:L) ((A1:L1)
insert A T = replace_root A T otherwise</code>
|