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

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

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

1. Декартово произведение. Если суть типы, а — тип, состоящий из множества -ок вида , , , то говорится, что — декартово произведение типов и обозначается как . При этом предполагается, что определены селекторы для типа , что записывается как .

Таким же образом записывается конструктор . Конструктор — это функция, имеющая тип , то есть для .

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

.

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

2. Размеченное объединение. Если — это типы, а — это тип, состоящий из объединения типов , при условии выполнения «размеченности», то называется размеченным объединением типов . Обозначается этот факт как . Условие размеченности обозначает, что если из взять какой-нибудь элемент , то однозначно определяется тип этого элемента . Размеченность можно определить при помощи предикатов таких, что:

Размеченное объединение гарантирует наличие таких предикатов. Этот факт указывается записью: . Ещё есть части типа, которые обозначаются так: .

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

Пример 17. Формальное определение типа .

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

Каждая функция должна содержать как минимум два клоза, первый обрабатывает , второй — соответственно. Этим двум частям типа в абстрактной записи соответствуют селекторы и . Два клоза можно объединить в один с использованием охраны. В теле второго клоза (или второго выражения охраны) обработка элемента (или ) выполняется той же самой функцией.

Пример 18. Формальное определение типа .

Функции над должны иметь по крайней мере следующие клозы:

3.1°

3.2°

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

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

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

Для конструирования функций, обрабатывающих структуры данных , необходимо ввести несколько дополнительных понятий и обозначений для них. Это делается для простоты. Начальная вершина, вершина и вершина (выходящая из ) обозначаются как , и соответственно. Для обработки этих вершин необходимы три функции — , и , причём — это начальная функция, а две последних — рекурсивные.

Рисунок 3. Гиперграф для представления структуры

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

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

  • — метка вершины;
  • — параметр, содержащий результат обработки просмотренной части дерева;
  • — лес, который необходимо обработать.
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

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

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

  • — метка вершины;
  • — метка дуги;
  • — поддерево для обработки;
  • — результат обработки просмотренной части дерева.
f2 A B T K = f1 (mroot T) (g3 A B K) (mlist T)

Необходимо отметить, что это общий вид функций для обработки структур данных . Реализация дополнительных функций , и зависит от конкретной задачи. Теперь можно сконструировать и общий вид функции :

f0 T = f1 (root T) k (mlist T)

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

Для более глубокого закрепления методики конструирования функций можно рассмотреть конкретную реализацию функций работы с B-деревьями. Пусть для структуры данных существует набор базисных операций, а сами деревья представляются в виде списков (особой роли представление не играет). Базисные операции следующие:

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. Функция 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