1. ВВЕДЕНИЕ

Многие программы, которые используют повторяющиеся операции, могут быть естественно описаны с использованием некоторой формы рекурсии, а свойства доказаны с использованием некоторой формы индукции.

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

Не удивительно, что многие рекурсивные программы содержат общий образец рекурсии, а индуктивные доказательства содержат общий образец индукции. Повторение тех же самых операций ведёт к ошибкам, и является достаточно трудоёмким и ненужным процессом. Повторений можно избежать с помощью введения специального оператора рекурсии и способа доказательства, которые инкапсулируют общие образцы, позволяя сконцентрироваться на частях, являющихся различными для разных приложений.

В функциональном программировании оператор свёртки (также известный как fold) - стандартный оператор, инкапсулирующий общий образец рекурсии для функций обработки списков. Оператор свёртки обладает свойством универсальности, которое инкапсулирует общий образец индуктивного доказательства, касающегося списков.

Руководство построено на двух ключевых аспектах оператора свёртки. Прежде всего, речь пойдет об универсальности оператора fold (вместе со свойством объединения), как с точки зрения способа доказательства, т.е. принципа, который не требует доказательств по индукции, так и с точки зрения способа определения, т.е. принципа, основанного на преобразовании рекурсивных функций в определения, с использованием оператора свёртки. Во-вторых, мы покажем, что даже притом, что образец рекурсии, инкапсулированный оператором свёртки, достаточно прост, в языке с кортежами оператор имеет большую степень выразительности, чем ожидалось, таким образом разрешая универсальное свойство и свойство объединения для оператора свёртки, оказывается, что он может быть применён к большему классу программ.

Статья заканчивается обзором работ, описывающих операторы рекурсии, некоторые положения которых, не будут присутствовать в данном руководстве.

Статья нацелена на читателя, знакомого с основами функционального программирования (Bird & Wadler, 1988; Bird, 1998). Все программы, приведённые в статье, написаны на языке Haskell (Peterson и др., 1997), который является стандартным функциональным языком программирования. В программах не использовались специальные возможности языка Haskell, что позволяет легко приспособить примеры к другим функциональным языкам.

2. ОПЕРАТОР СВЁРТКИ

св а: =з

Оператор свёртки описывается в теории рекурсии (Kleene, 1952). Использование свёртки, как центрального понятия в языке программирования относится ко времени оператора редукции языка APL (Iverson, 1962), и позже оператора вставки FP (Backus, 1978). В языке Haskell, оператор свёртки для списков может быть определён следующим образом:

fold f v [] fold f v (x:xs)

(a -> b -> b) -> b -> ([a] -> b)

f x (fold f v xs)

Таким образом, рассматривая функцию f типа a ->Ъ ->Ъ и значение v типа Ъ, функция fold f v обрабатывает список типа [а], для задания значения типа Ъ, заменяя пустой элемент nil значением v, а конструктор подстановки cons (:) в списке, функциейf Таким же образом, оператор свёртки инкапсулирует простой образец рекурсии, в котором эти два конструктора просто заменены другими значениями и функциями. Целый ряд знакомых функций, построенных на списках, могут быть легко реализованы с использованием оператора свёртки. Например:

Вспомните, что применение инфиксного оператора Ф в круглых скобках ( Ф ) преобразовывает оператор в префиксную форму. Этот приём, называется секционированием, и часто является полезным при написании простых функций с использованием свёртки. Если требуется, один из аргументов оператора может быть также заключён в круглые скобки. Например, функция (++) может быть реализована следующим образом:

(++) :: (++ ys) =

[a] -> [a] -> [a] fold (:) ys

Во всех приведённых примерах, конструктор (:) заменён встроенной функцией. Однако, в большинстве случаев применения оператора свёртки, конструктор (:) будет заменён функциями, определёнными пользователем, часто реализованные, как

£ сс

неименованные функции, с использованием -абстракции, как стандартных функций обработки списков:

следующих примерах

length::

length=

reverse::

reverse=

filter::

filter p=

[a] -> Int

fold (\x n -> 1 + n) 0

[a] -> [a]

fold (\x xs -> xs ++ [x]) []

(a -> b) -> ([a] -> [b])

fold (\x xs -> f x : xs)

(a -> Bool)

fold (\x xs

>([a] -> [a])

>if p x then x : xs else xs) []

Программы, написанные с использованием свёртки, могут быть менее удобочитаемы, чем программы, написанные с использованием явной рекурсии. Однако, программы написанные с использованием оператора fold более систематизированы, и более удобны для преобразования и доказательства различных свойств. Например, далее в статье описано, как вышеупомянутое определение функции map с использованием оператора свёртки, может быть построено из обычного определения, с использованием явной рекурсии, и что ещё более важно, как использование свёртки упрощает процесс доказательства свойств функции map.