поскольку Stream является не самостоятельным типом а типом-синонимом. Поэтому нам приходится опре-
делить функцию mapS. Определим шаг рекурсии:
primes :: Stream Int
primes = ana erato nums
erato xs = n :& erase n ys
where n
= fromJust $ headS xs
ys = dropWhileS isNothing xs
Переменная n содержит первое не зачёркнутое число на данном шаге. Переменная ys указывает на спи-
сок чисел, из начала которого удалены все зачёркнутые числа. Функции isNothing и fromJust взяты из стан-
дартного модуля Data.Maybe. Нам осталось определить лишь две функции. Это аналог функции dropWhile
на списках. Эта функция удаляет из начала списка все элементы, которые удовлетворяют некоторому пре-
дикату. Вторая функция erase вычёркивает все числа в потоке кратные данному.
dropWhileS :: (a -> Bool) -> Stream a -> Stream a
dropWhileS p = psi >> phi
where phi ((b, xs) :& next) = if b then next else xs
psi xs = (p $ headS xs, xs) :& tailS xs
В этой функции мы сначала генерируем список пар, который содержит значения предиката и остатки
списка, а затем находим в этом списке первый такой элемент, значение которого равно False.
erase :: Int -> Stream (Maybe a) -> Stream (Maybe a)
erase n xs = ana phi (0, xs)
where phi (a, xs)
| a == 0
= Nothing
:& (a’, tailS xs)
| otherwise = headS xs :& (a’, tailS xs)
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
Дополнительные возможности
В этой главе мы рассмотрим некоторые дополнительные возможности языка и расширения, они часто
используются в серьёзных программах. Можно писать программы и без них, но с ними гораздо легче и увле-
кательней.
17.1 Пуд сахара
В этом разделе мы рассмотрим специальный синтаксический сахар, который позволяет более кратко
записывать операции для некоторых структур.
Сахар для списков
Перечисления