F GX = F ( GX)
246 | Глава 16: Категориальные типы
По определению функции построенные с помощью этих операций называют полиномиальными. Опреде-
лим несколько типов данных с помощью полиномиальных функторов. Определим логические значения:
Bool = µ(1 + 1)
Объект 1 обозначает любую константу, это конечный объект исходной категории. Нам не важны имена
конструкторов, но важна структура типа. µ обозначает начальный объект в F -алгебре.
Определим натуральные числа:
N at = µ(1 + I)
Эта запись обозначает начальный объект для F -алгебры с функтором F = 1 + I. Посмотрим на опреде-
ление списка:
ListA = µ(1 + A × I)
Список это начальный объект F -алгебры 1 + A × I. Также можно определить бинарные деревья:
BT reeA = µ( A + I × I)
Определим потоки:
StreamA = ν( A × I)
Потоки являются конечным объектом F -коалгебры, где F = A × I.
16.3 Гиломорфизм
Оказывается, что с помощью катаморфизма и анаморфизма мы можем определить функцию fix, то есть
мы можем выразить любую рекурсивную функцию с помощью структурной рекурсии.
Функция fix строит бесконечную последовательность применений некоторой функции f.
f (f (f ... )))
Сначала с помощью анаморфизма мы построим бесконечный список, который содержит функцию f во
всех элементах:
repeat f = f : f : f : ...
А затем заменим конструктор : на применение. В итоге мы получим такую функцию:
fix :: (a -> a) -> a
fix = foldr ($) undefined . repeat
Убедимся, что эта функция работает:
Prelude> let fix = foldr ($) undefined . repeat
Prelude> take 3 $ y (1:)
[1,1,1]
Prelude> fix (\f n -> if n==0 then 0 else n + f (n-1)) 10
55
Теперь давайте определим функцию fix через функции cata и ana:
fix :: (a -> a) -> a
fix = cata (\(Cons f a) -> f a) . ana (\a -> Cons a a)
Эта связка анаморфизм с последующим катаморфизмом встречается так часто, что ей дали специальное
имя. Гиломорфизмом называют функцию:
hylo :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b)
hylo phi psi = cata phi . ana psi
Отметим, что эту функцию можно выразить и по-другому:
Гиломорфизм | 247
hylo :: Functor f => (f b -> b) -> (a -> f a) -> (a -> b)
hylo phi psi = phi . (fmap $ hylo phi psi) . psi
Этот вариант более эффективен по расходу памяти, мы не строим промежуточное значение Fix f, а сразу
обрабатываем значения в функции phi по ходу их построения в функции psi. Давайте введём инфиксную
операцию гиломорфизм для этого определения:
(>> ) :: Functor f => (a -> f a) -> (f b -> b) -> (a -> b)