использованием этого оператора. Например, функция reverse переопределяется следующим образом:

reverse :: [a] -> [a]

reverse = foldl (\xs x -> x:xs) []

Это определение предпочтительнее, чем его стандартная форма (с использованием свёртки), т.к. в нём не требуется многократного применения оператора (++).

Простое обобщение вычислений, проведенных ранее для функции suml, показывает, что foldl выражается через оператор свёртки следующим образом:

foldl f v xs = fold (\x g -> (\a -> g (f a x))) id xs v

Однако, выразить оператор свёртки через foldl не возможно вследствие того, что foldl определяется строго в хвосте списка своих аргументов, а оператор свёртки - нет. Существует ряд двойственных теорем, связанных с операторами fold и foldl, а также рекомендации, помогающие определить, какой оператор лучше всего подходит для данной конкретной задачи (Bird, 1998).

£ то

5.2. Функция Акермана

В заключение рассмотрим пример реализации функции ack, иллюстрирующий степень свёртки. Функция ack обрабатывает два списка целых чисел и определяется с использованием явной рекурсии следующим образом:

ack[] ys=

ack(x:xs)[]=

ack(x:xs)(y:ys) =

[Int] -> ([Int] -> [Int]) 1:ys

ack xs [1]

ack xs (ack (x:xs) ys)

Функция Акермана позволяет оперировать списками, а не числами, представляя каждое число n списком с n произвольных элементов. Эта функция - классический пример функции, которая в языке программирования низкого уровня не является примитивно-рекурсивной. Однако, на языке высокого уровня, типа Haskell, функция Акермана действительно примитивно-рекурсивная (Reynolds, 1985).

Для того, чтобы выразить эту функцию, используя оператор свёртки, прежде всего необходимо воспользоваться свойством универсальности оператора fold. Получаем, что равенство ack = fold f v эквивалентно следующим двум уравнениям:

ack (x:xs)

f x (ack xs)

Из первого уравнения получаем, что v = (1:). Из второго уравнения мы не сможем получить определение для f, как мы делали это раньше. Необходимо переопределить с

использованием свёртки функцию ack (x:xs), стоящую в левой части второго уравнения. С использованием универсального свойства получаем следующий результат для уравнения:

ack (x:xs) []= w

ack (x:xs) (y:ys) = g y (ack (x:xs) ys)

Из первого уравнения получаем, что w = ack xs [1], из второго уравнения получаем:

ack (x:xs) (y:ys)=

ack xs (ack (x:xs) ys) = ack xs zs=

g y (ack (x:xs) ys) g y (ack (x:xs) ys) g y zs

\y -> ack xs

Таким образом, используя универсальность оператора свёртки, мы вычислили что: ack (x:xs)= fold (\y -> ack xs) (ack xs [1])

На основе полученного результата мы можем вычислить определение для f:

ack (x:xs)

fold (\y -> ack xs) (ack xs [1])

fold (\y -> g) (g [1])

f x (ack xs) f x (ack xs) f x g

\x g -> fold (\y -> g) (g [1])

В заключении дважды применяем универсальное свойство оператора свёртки и получаем что:

ack= fold (\x g -> fold (\y -> g) (g [1])) (1:)

6. ДРУГИЕ РАБОТЫ ПОСВЯЩЕННЫЕ ОПЕРАТОРАМ

РЕКУРСИИ

В последнем разделе мы кратко рассмотрим несколько работ, в которых рассматриваются операторы рекурсии, не упоминавшиеся в этом руководстве.

Оператор свёртки для регулярных типов данных. Оператор свёртки может применяться не только к спискам, но и к «регулярным» типам данных (Malcolm, 1990b; Meijer и др., 1991; Sheard & Fegaras, 1993).

Оператор свёртки для вложенных типов данных. Оператор свёртки может применяться к «вложенным» типам данных. Однако получающийся оператор не является достаточно обобщённым, чтобы было возможно его повсеместное использование. Поиск решений этой проблемы - предмет настоящего исследования (Bird & Meertens, 1998;

Jones & Blampied, 1998).

Оператор свёртки для функциональных типов данных. С обобщением оператора свёртки для типов данных появляется множество технических проблем. Пользуясь идеями из теории категории, оператор свёртки может быть определён для нескольких типов данных (Meijer & Hutton, 1995), но его использование практически не востребовано. Однако, более простое, но менее общее решение положило начало использованию оператора, связанному с циклическими структурами (Fegaras & Sheard, 1996).

Оператор свёртки для монад. В ряде важных статей Wadler показал, как функциональные программы могут быть промоделированы с использованием монад (Wadler, 1990; Wadler, 1992a; Wadler, 1992b). Работа включает в себя рассмотрение способов применения оператора свёртки к структурам, обрабатывающим рекурсивные значения с использованием монад (Fokkinga, 1994; Meijer & Jeuring, 1995).

Относительная свёртка. Оператор свёртки может быть применён также к отношениям. Это обобщение позволяет добавить описательный аспект оператору свёртки к уже имеющемуся программному. Например, относительная свёртка используется для расчета схем Ruby (Jones & Sheeran, 1990; Jones, 1990), эйндховенского исчисления спекуляции (Aarts и др., 1992) и, в недавно опубликованном учебнике по алгебре программирования (Bird & de Moor, 1997).

Другие операторы рекурсии. Оператор свёртки - не единственный полезный оператор рекурсии. Например, двойственный оператор используется в целях спецификации (Jones, 1990; Bird & de Moor, 1997), для программирования реактивных систем (Kieburtz, 1998).

Автоматическое изменение программы. При написании программы с использованием операторов рекурсии можно упростить процесс оптимизации во время

ФП 02005-01 01