£ сс

k y (x:xs)

i x (k y xs)

Из первого уравнения получаем, что j = (f y, []). Из второго уравнения, мы попытаемся вывести определение для i следующим образом:

k y (x:xs) (h y (x:xs), x:xs) (g y x xs (h y xs), x:xs (g y x xs z, x:xs)

i x(k y xs)

i x(h y xs, xs)

i x(h y xs, xs)

i x(z, xs)

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

fold i j where

i x (z, xs)

(g y x xs z, x:xs)

(f y, [])

Это определение удовлетворяет уравнению ky xs = (h y xs, xs), но не использует h. Следовательно, примитивно-рекурсивную функцию h можно переопределить с использованием равенства h y = fst. к y. Мы показали, как произвольная примитивно-рекурсивная функция, обрабатывающая списки, может быть переопределена в терминах свёртки.

Заметьте, что использование способа составления кортежей для определения примитивно-рекурсивных функций в терминах свёртки, является ключевым моментом к определению функции предшественника для нумералов Чёрча (Barendregt, 1984). Действительно, интуитивное представление естественного числа (или вообще, любого индуктивного типа данных) в -исчислении заключается в представлении каждого числа его оператором свёртки. Например, число 3 = succ (succ (succ zero)) представляется термом \fx -> f (f (fx)), который является оператором свёртки для числа 3, если рассматривать f и x, как succ и zero соответственно.

£ то

св а: =з

5. ИСПОЛЬЗОВАНИЕ ОПЕРАТОРА СВЁРТКИ ДЛЯ ОПРЕДЕЛЕНИЯ ФУНКЦИИ

Степень примитивной рекурсии может увеличиваться, а, следовательно, и степень оператора свёртки также может увеличиваться. Приведём ещё один пример использования свёртки, рассмотрим функцию compose, которая формирует список функций. Она может быть определена с использованием свёртки, путём замены каждого конструктора (:) в списке, функцией (.), а пустой список [], идентично работающей функцией id:

compose :: compose =

[a -> a] -> (a -> a) fold (.) id

Рассмотрим проблему суммирования списка чисел. Основным определением для этой функции является: sum = fold (+) 0, числа в списке рассматриваются справа налево. Можно также реализовать функцию suml, которая будет обрабатывать список в обратном порядке. Функция suml задаётся с использованием вспомогательной функции suml, которая определяется через явную рекурсию и использует накапливающий параметр n:

suml xs =

[Int] -> Int

suml xs 0

suml [] n suml (x:xs) n

suml xs (n + x)

Поскольку функция (+) ассоциативна, она возвращает тот же самый результат при обработке одного и того же списка. Однако применение функции suml оказывается более рациональным из-за того, что её можно легко модифицировать (Bird, 1998).

Теперь предположим, что мы хотим переопределить функцию suml с использованием оператора свёртки. Этого можно добиться только воспользовавшись вспомогательной функцией:

suml:: [Int] -> (Int -> Int)

которая может переопределяться напрямую. Применяя свойство универсальности оператора свёртки, получаем, что равенство suml = fold fv эквивалентно следующим двум уравнениям:

suml suml

f x (siml xs)

Из первого уравнения получаем, что v = id. Из второго уравнения мы попытаемся вывести определение для f следующим образом:

suml (x:xs) suml (x:xs) n

f x (suml xs) f x (suml xs) n

£ сс

suml xs (n + x) g (n + x)

f x (suml xs) n f x g n

\x g -> (\n -> g (n + x))

Теперь, применяя свойство универсальности функции fold, получаем:

suml= fold (\x g -> (\n -> g (n + x))) id

Полученное определение показывает, что suml обрабатывает список, заменяя пустой список [] функцией id, а каждый конструктор (:) функцией, которая берет число x и функцию g, и возвращает функцию, которая берёт значение n из аккумулятора и возвращает результат применения g к новому значению аккумулятора n + x.

Заметьте, что задание функции, как suml:: [Int] -> (Int -> Int) невозможно при определении её с использованием свёртки. В частности, если эти два аргумента реверсированы или они представляют собой пару, в этом случае тип suml показывает, что определение больше не может быть реализовано непосредственно с использованием свёртки. На самом деле, нужно быть достаточно осторожными при переопределении функции с помощью свёртки. На первый взгляд можно подумать, что оператор свёртки используется только для тех функций, которые обрабатывают списки справа налево. Однако, на примере функции suml мы показали, что порядок обработки элементов списка зависит от аргументов оператора, а не от самого оператора свёртки.

Мы показали, что функция suml может быть переопределена с использованием свёртки, как и требовалось:

suml xs= fold (\x g -> (\n -> g (n + x))) id xs 0

В заключении отметим, что использование свёртки для составления функций, является удобным способом для применения атрибутивных грамматик в функциональных языках (Fokkinga и др., 1991; Swierstra и др., 1998).

5.1. Оператор foldl

Рассмотрим стандартный оператор foldl на примере функции suml, описанной в предыдущем разделе. Оператор обрабатывает элементы списка слева направо с использованием функции f (для объединения значений), и значение v в качестве начального условия:

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

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

foldl f (f v x) xs

С помощью этого оператора функция suml может быть переопределена просто как suml = foldl (+) 0. Наряду с suml многие другие функции быть определены с