и Monad для типа State s (рис. 6.7).
Подсказка: В этом определении есть одна хитрость, в отличае от типов Maybe и [a] у типа State два
параметра, это параметр состояния и параметр значения. Но мы делаем экземпляр не для State, а для State
s, то есть мы свяжем тип с некоторым произвольным типом s.
instance Kleisli (State s) where
…
Упражнения | 101
a
f
b
env
Рис. 6.8: Функция с окружением
Функции с окружением
Сначала мы рассмотрим функции с окружением. Функции с окружением – это такие функции, у которых
есть некоторое хранилище данных или окружение, из которых они могут читать информацию. Но в отличие
от функций с состоянием они не могут это окружение изменять. Функция с окружением похожа на функцию
с состоянием без одного выхода для состояния (рис. 6.8).
Функция с окружением принимает аргумент a и окружение env и возвращает результат b:
a -> env -> b
Как и в случае функций с состоянием выделим для функции с окружением отдельный тип. В Haskell он на-
зывается Reader (от англ. чтец). Все функции с окружением имеют возможность читать из общего хранилища
данных. Например они могут иметь доступ на чтение к общей базе данных.
data Reader env b = Reader (env -> b)
runReader :: Reader env b -> (env -> b)
runReader (Reader f) = f
Теперь функция с окружением примет вид:
a -> Reader env b
Определите для функций с окружением экземпляр класса Kleisli. У нас возникнет цепочка функций,
каждая из которых будет нуждаться в значении окружения. Поскольку окружение общее для всех функций
мы всем функциям передадим одно и то же значение (рис. 6.9).
a
f
b
b
g
c
env
env
b
a
g
f
c
env
a
f*>g
c
env
Рис. 6.9: Функция с окружением
Функции-накопители
Функции-накопители при вычислении за ширмой накапливают некоторое значение. Функция-накопитель
похожа на функцию с состоянием но без стрелки, по которой состояние подаётся в функцию (рис. 6.10).
Функция-накопитель имеет тип: a -> (b, msg)
Выделим результат функции в отдельный тип с именем Writer.
102 | Глава 6: Функторы и монады: теория
a
f
b
Msg
Рис. 6.10: Функция-накопитель
data Writer msg b = Writer (b, msg)
runWriter :: Writer msg b -> (b, msg)
runWriter (Writer a) = a
Тип функции примет вид:
a -> Writer msg b
Значения типа msg мы будем называть сообщениями. Смысл функций a -> Writer msg b заключается
в том, что при вычислении они накапливают в значении msg какую-нибудь информацию. Это могут быть
отладочные сообщения. Или база данных, которая открыта для всех функций на запись.
Класс Monoid
Как мы будем накапливать результат? Пока мы умеем лишь возвращать из функции пару значений. Одно
из них нам нужно передать в следующую функцию, а что делать с другим?
На помощь нам придёт класс Monoid, он определён в модуле Data.Monoid:
class Monoid a where
mempty
:: a
mappend :: a -> a -> a
В этом классе определено пустое значение mempty и бинарная функция соединения двух значений в одно.
Этот класс очень похож на класс Category и Kleisli. Там тоже было значение, которое ничего не делает и
операция составления нового значения из двух простейших значений. Даже свойства класса похожи:
mempty
‘mappend‘ f
= f
f
‘mappend‘ mempty
= f
f ‘mappend‘ (g ‘mappend‘ h) =
(f ‘mappend‘ g) ‘mappend‘ h
a
g
f
b
b
c
msg
msg
b
a
g
f
c
MsgG
++
MsgF ++ MsgG
MsgF
a
f*>g
c
msg
Рис. 6.11: Композиция функций-накопителей
Упражнения | 103
Первые два свойства говорят о том, что значение mempty и вправду является пустым элементом отно-
сительно операции mappend. А третье свойство говорит о том, что порядок при объединении элементов не
важен.
Посмотрим на определение экземпляра для списков:
instance Monoid [a] where
mempty
= []
mappend = (++)
Итак пустой элемент это пустой список, а объединение это операция конкатенации списков. Проверим в
интерпретаторе:
*Kleisli> :m Data.Monoid
Prelude Data.Monoid> [1 .. 4] ‘mappend‘ [4, 3 .. 1]
[1,2,3,4,4,3,2,1]
Prelude Data.Monoid> ”Hello” ‘mappend‘ ” World” ‘mappend‘ mempty
”Hello World”
Напишите экземпляр класса Kleisli для функций накопителей по (рис. 6.11). При этом будем считать,
что тип msg является экземпляром класса Monoid.
Экземпляры для функторов и монад
Представьте, что у нас нет класса Kleisli, а есть лишь Functor, Applicative и Monad. Напишите экзем-
пляры для этих классов для всех рассмотренных в этой главе специальных функций (в том числе и для Reader
и Writer). Экземпляры Functor и Applicative могут быть определены через Monad. Но для тренировки опре-
делите экземпляры полностью. Сначала Functor, затем Applicative и в последнюю очередь Monad.
Деревья
Напишите экземпляры классов Kleisli и Monad для двух типов, которые описывают деревья. Бинарные
деревья:
data BTree a = BList a | BNode a (BTree a) (BTree a)
Деревья с несколькими узлами:
data Tree a = Node a [Tree a]
Считайте, что списки являются частными случаями деревьев. В этом смысле деревья будут описывать
многозначные функции, которые возвращают несколько значений, организованных в иерархическую струк-
туру.
Стандартные функции
Почитайте документацию к модулям Control.Monad и Control.Applicative. Присмотритесь к функциям,
попробуйте применить их в интерпретаторе.
Эквивалентность классов Kleisli и Monad
Покажите, что классы Kleisli и Monad эквивалентны. Для этого нужно для произвольного типа c с одним