мый тип заменялся на параметр. Например для списка мы строили свёртку так:
class [a] b where
(:) :: a -> b -> b
[]
:: b
После этого мы легко получали тип для функции свёртки:
foldr :: (a -> b -> b) -> b -> ([a] -> b)
Программирование в стиле оригами | 241
Она принимает методы воображаемого класса, в котором тип записан с параметром, а возвращает функ-
цию из рекурсивного типа в тип параметра.
Сейчас мы выполняем эту процедуру замены рекурсивного типа на параметр в обратном порядке. Сначала
мы строим типы с параметром, а затем получаем из них рекурсивные типы с помощью конструкции Fix.
Теперь методы класса с параметром это наши конструкторы исходных классов, а рекурсивный тип записан
через Fix. Если мы сопоставим два способа, то мы сможем получить такой тип для функции свёртки:
fold :: (f b -> b) -> (Fix f -> b)
Смотрите функция свёртки по-прежнему принимает методы воображаемого класса с параметром, но те-
перь класс перестал быть воображаемым, он стал типом с параметром. Результатом функции свёртки будет
функция из рекурсивного типа Fix f в тип параметр.
Аналогично строится и функция unfold:
unfold :: (b -> f b) -> (b -> Fix f)
В первой функции мы указываем один шаг разворачивания рекурсивного типа, а функция развёртки
рекурсивно распространяет этот один шаг на потенциально бесконечную последовательность применений
этого одного шага.
Теперь давайте определим эти функции. Но для этого нам понадобится от типа f одно свойство. Он
должен быть функтором, опираясь на это свойство, мы будем рекурсивно обходить этот тип.
fold :: Functor f => (f a -> a) -> (Fix f -> a)
fold f = f . fmap (fold f) . unFix
Проверим эту функцию по типам. Для этого нарисуем схему композиции:
f
fmap (fold f)
f
Fix f
f (Fix f)
f a
a
Сначала мы разворачиваем обёртку Fix и получаем значение типа f (Fix f), затем с помощью fmap мы
внутри типа f рекурсивно вызываем функцию свёртки и в итоге получаем значение f a, на последнем шаге
мы выполняем свёртку на текущем уровне вызовом функции f.
Аналогично определяется и функция unfold. Только теперь мы сначала развернём первый уровень, затем
рекурсивно вызовем развёртку внутри типа f и только в самом конце завернём всё в тип Fix:
unfold :: Functor f => (a -> f a) -> (a -> Fix f)
unfold f = Fix . fmap (unfold f) . f
Схема композиции:
Fix
fmap (unold f)
f
Fix f
f (Fix f)
f a
a
Возможно вы уже догадались о том, что функция fold дуальна по отношению к функции unfold, это
особенно наглядно отражается на схеме композиции. При переходе от fold к unfold мы просто перевернули
все стрелки заменили разворачивание типа Fix на заворачивание в Fix.
Определим несколько функций для натуральных чисел и списков в стиле оригами. Для начала сделаем
L и N экземпляром класса Functor:
instance Functor N where
fmap f x = case x of
Zero
-> Zero
Succ a
-> Succ (f a)
instance Functor (L a) where
fmap f x = case x of
Nil
-> Nil
Cons a b
-> Cons a (f b)
Это всё что нам нужно для того чтобы начать пользоваться функциями свёртки и развёртки! Определим
экземпляр Num для натуральных чисел:
instance Num Nat where
(+) a = fold $ \x -> case x of
Zero
-> a
Succ x
-> succ x
(*) a = fold $ \x -> case x of
242 | Глава 16: Категориальные типы
Zero
-> zero
Succ x
-> a + x
fromInteger = unfold $ \n -> case n of
0
-> Zero
n
-> Succ (n-1)
abs = undefined
signum = undefined
Сложение и умножение определены через свёртку, а функция построения натурального числа из чис-
ла типа Integer определена через развёртку. Сравните с теми функциями, которые мы писали в главе про
структурную рекурсию. Теперь мы не передаём отдельно две функции, на которые мы будем заменять кон-