where a’ = if a == n-1 then 0 else (a+1)
Гиломорфизм | 249
В функции erase мы заменяем на Nothing каждый элемент, порядок следования которого кратен аргу-
менту n. Проверим, что у нас получилось:
*Fix> primes
(2 :& (3 :& (5 :& (7 :& (11 :& (13 :& (17 :& (19 :& (23 :& (29 :& (31 :& (37 :& (41 :& (43 :& (47 :& (53 :& (59 :&
(61 :& (67 :& (71 :& (73 :& (79 :& (83 :& (89 :& (97 :&
(101 :& (103 :& (107 :& (109 :& (113 :& (127 :& (131 :&
...
16.4 Краткое содержание
В этой главе мы узнали, что любая рекурсивная функция может быть выражена через структурную ре-
курсию. Мы узнали как в теории категорий определяются типы. Типы являются начальными и конечными
объектами в специальных категориях, которые называются алгебрами функторов. Слоган теории категорий
гласит:
Управляющие структуры определяются структурой типов.
Определив тип, мы получаем вместе с ним две функции структурной рекурсии, это катаморфизм (для
начальных объектов) и анаморфизм (для конечных объектов). С помощью катаморфизма мы можем свора-
чивать значение данного типа в значения любого другого типа, а с помощью анаморфизма мы можем раз-
ворачивать значения данного типа из значений любого другого типа. Также мы узнали, что категория Hask
является категорией CPO, категорией полных частично упорядоченных множеств.
16.5 Упражнения
• Потренируйтесь в определении рекурсивных функций через гиломорфизм. Попробуйте переписать как
можно больше определений из главы о структурной рекурсии в терминах типа Fix и функций cata, ana
и hylo. Также потренируйтесь на стандартных функциях из модуля Prelude. Определите новые типы
через Fix например деревья из модуля Data.Tree. Попробуйте свои силы на функциях по-сложнее
например алгоритме эвристического поиска.
• Определите монадные версии рекурсивных функций:
cataM :: (Monad m, Traversable t) => (t a -> m a) -> Fix t -> m a
anaM
:: (Monad m, Traversable t) => (a -> m (t a)) -> (a -> m (Fix t))
hyloM :: (Monad m, Traversable t) => (t b -> m b) -> (a -> m (t a)) -> (a -> m b) С помощью этих функций мы, например, можем преобразовывать дерево выражения и при этом обнов-
лять какое-нибудь состояние или читать из общего окружения.
В этом определении стоит новый класс Traversable. Разберитесь с ним самостоятельно. Немного под-
скажу. Этот класс появился вместе с классом Applicative. Когда разработчики поняли о существова-
нии полезной абстракции, которая ослабляет класс Monad, они также обратили внимание на функцию
sequence:
sequence :: Monad m => [m a] -> m [a]
sequence = foldr (liftM2 (:)) (return [])
Эту функцию можно записать с помощью одних лишь методов класса Applicative. Поэтому ограниче-
ние в контексте функции избыточно. Класс Traversable предназначени для устранения этой неточно-
сти. Посмотрим на основной метод класса:
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
Тип очень похож на тип функции mapM. И не случайно, ведь mapM определяется через sequence. Только
теперь вместо списка стоит более общий тип. Это тип Foldable, который определяет список как нечто,
на чём можно проводить операции свёртки.
250 | Глава 16: Категориальные типы
Глава 17
Дополнительные возможности