Учебник по Haskell

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 Пуд сахара

В этом разделе мы рассмотрим специальный синтаксический сахар, который позволяет более кратко

записывать операции для некоторых структур.

Сахар для списков

Перечисления

Для класса 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]