курсию. Мы узнали как в теории категорий определяются типы. Типы являются начальными и конечными
объектами в специальных категориях, которые называются алгебрами функторов. Слоган теории категорий
гласит:
Управляющие структуры определяются структурой типов.
Определив тип, мы получаем вместе с ним две функции структурной рекурсии, это катаморфизм (для
начальных объектов) и анаморфизм (для конечных объектов). С помощью катаморфизма мы можем свора-
чивать значение данного типа в значения любого другого типа, а с помощью анаморфизма мы можем раз-
ворачивать значения данного типа из значений любого другого типа. Также мы узнали, что категория 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 Пуд сахара
В этом разделе мы рассмотрим специальный синтаксический сахар, который позволяет более кратко
записывать операции для некоторых структур.
Сахар для списков
Перечисления
Для класса Enum определён специальный синтаксис составления последовательностей перечисляемых
значений. Так например мы можем составить список целых чисел от нуля до десяти:
Prelude> [0 .. 10]
[0,1,2,3,4,5,6,7,8,9,10]
А так мы можем составить бесконечную последовательность положительных чисел:
Prelude> take 20 $ [0 .. ]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]
Мы можем составлять последовательности с определённым шагом. Так можно выделить все чётные по-
ложительные числа:
Prelude> take 20 $ [0, 2 .. ]
[0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38]
А так мы можем составить убывающую последовательность чисел:
Prelude> [10, 9 .. 0]
[10,9,8,7,6,5,4,3,2,1,0]
Что интересно в списке могут находиться не только числа, а любые значения из класса Enum. Например
определим тип:
data Day
= Monday | Tuesday | Wednesday | Thursday
| Friday | Saturday | Sunday
deriving (Show, Enum)
Теперь мы можем написать:
*Week> [Friday .. Sunday]
[Friday, Saturday, Sunday]
*Week> [ Monday .. ]
[Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday]
Также шаг последовательности может быть и дробным:
*Week> [0, 0.5 .. 4]
[0.0,0.5,1.0,1.5,2.0,2.5,3.0,3.5,4.0]
| 251
Генераторы списков
Генераторы списков (list comprehensions) объединяют в себе функции преобразования и фильтрации спис-
ков. Они записываются так:
[ f x | x <- list, p x]
В этой записи мы фильтруем список list предикатом p и преобразуем результат функцией f. Например
возведём в квадрат все чётные элементы списка:
Prelude> [x*x | x <- [1 .. 10], even x]
[4,16,36,64,100]
Предикатов может быть несколько, так например мы можем оставить лишь положительные чётные числа:
Prelude> [x | x <- [—10 .. 10], even x, x >= 0]
[0,2,4,6,8,10]
Также элементы могут браться из нескольких списков, посмотрим на все возможные комбинации букв из
пары слов:
Prelude> [ [x,y] | x <- ”Hello”, y <- ”World”]
[”HW”,”Ho”,”Hr”,”Hl”,”Hd”,”eW”,”eo”,”er”,”el”,
”ed”,”lW”,”lo”,”lr”,”ll”,”ld”,”lW”,”lo”,”lr”,
”ll”,”ld”,”oW”,”oo”,”or”,”ol”,”od”]
Сахар для монад, do-нотация
Монады используются столь часто, что для них придумали специальный синтаксис, который облегчает
подстановку специальных значений в функции нескольких переменных. Монады позволяют комбинировать
специальные функции вида
a -> m b
Если бы эти функции выглядели как обычные функции:
a -> b
их можно было свободно комбинировать с другими функциями. А так нам постоянно приходится поль-
зоваться методами класса Monad. Очень часто функции с побочными эффектами имеют вид:
a1 -> a2 -> a3 -> … -> an -> m b
А теперь представьте, что вам нужно подставить специальное значение третьим аргументом такой функ-
ции и затем передать ещё в одну такую же функцию. Для облегчения участи программистов было придумано
специальное окружение do, в котором специальные функции комбинируются так словно они являются обыч-
ными. Для этого используется обратная стрелка. Посмотрим как определяется функция sequence в окруже-
нии do:
sequence :: [m a] -> m [a]
sequence []
= return []
sequence (mx:mxs)
= do
x
<- mx
xs <- sequence mxs
return (x:xs)
Во втором уравнении сначала мы говорим вычислителю словом do о том, что выражения записаны в мире
монады m. Запись с перевёрнутой стрелкой x <- mx означает, что мы далее в do-блоке можем пользоваться
значением x так словно оно имеет тип просто a, но не m a. Смотрите в этом определении мы сначала извле-
каем первый элемент списка, затем извлекаем хвост списка, приведённый к типу m [a], и в самом конце мы
соединяем голову и хвост и в самом конце оборачиваем результат в специальное значение.
Например мы можем построить функцию, которая дважды читает строку со стандартного ввода и затем
возвращает объединение двух строк:
252 | Глава 17: Дополнительные возможности
getLine2 :: IO String
getLine2 = do
a <- getLine
b <- getLine
return (a ++ b)
В do-нотации можно вводить локальные переменные с помощью слова let:
t = do
b <- f a
c <- g b
let x = c + b
y = x + c
return y
Посмотрим как do-нотация переводится в выражение, составленное с помощью методов класса Monad:
