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: