Чтобы выработать некоторую интуицию касательно монад, полезно рассмотреть некоторые “стандартные” экземпляры этого класса, как они объявляются и как они используются.

Но сперва обсудим, что же именно описывает класс типов Monad.

Для функций, возвращающих обычные значения, определена операция композиции, в Haskell обозначаемая оператором . (“точка”):

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(f . g) x = f (g x)

Отметим, что порядок применения функций – справа налево (сначала применяется g, потом f), что не всегда является удобной нотацией. В различных функциональных языках существует так же оператор, позволяющий указать применение функций слева направо. Haskell не исключение, в модуле Data.Function объявлен оператор

(&) :: a -> (a -> b) -> b
x & f = f x

позволяющий записывать последовательное применение функций в виде

1 & (+1) & show & replicate 2 & concat
-- == (concat . replicate 2 . show . (+1)) 1
-- == concat (replicate 2 (show ((+1) 1)))
-- == "22"

Это удобно, но, увы, не работает для функций, которые возвращают значения в дополнительной структуре, например для частично-определённых на множестве действительных чисел функций

realSqrt :: Double -> Maybe Double
realSqrt x | x >= 0 = Just (sqrt x)
           | otherwise = Nothing

realArcsin :: Double -> Maybe Double
realArcsin x | abs x <= 1 = Just (asin x)
             | otherwise = Nothing

композиция вида realArcsin . realSqrt невозможна: realSqrt возвращает Maybe Double, в то время как realArcsin принимает просто Double, без Maybe. Однако кажется, что подобная композиция должна быть возможна: действительно, если realSqrt возвращает Nothing, то разумно сказать, что результат композиции так же не определён и присвоить ему Nothing. Тогда такая композиция (обозначим её <=<) будет иметь тип

(<=<) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)
-- для сравнения, тип обычной композиции:
(.) :: (b -> c) -> (a -> b) -> (a -> c)

Можно также ввести аналог оператора &, обозначим его >>=:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
-- для сравнения
(&) :: a -> (a -> b) -> b

Теперь – абстрагируем. Maybe не единственный тип, для которого эти операции могут быть осмыслены. Тогда обобщим сигнатуры до

(<=<) :: (b -> m c) -> (a -> m b) -> (a -> m c)
(>>=) :: m a -> (a -> m b) -> m b

Поскольку m вообще говоря не любой конструктор типа – для каких-то ситуаций определить подобную композицию невозможно (либо есть более одного варианта, либо осмысленного варианта нет вообще), и поскольку конкретные определения будут зависеть от конкретных типов, для реализации этой абстракции вводится класс типов Monad. Название взято из теории категорий, и математическую подоплёку оставим за скобками:

(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(>>=) :: Monad m => m a -> (a -> m b) -> m b

C практической точки зрения Monad кодирует композицию (или что то же самое, последовательное применение) функций, возвращающих значение (или значения), “завёрнутое” в какую-то обобщённую структуру.

Отдельно отметим, что <=< реализуется в терминах >>=:

(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
(f <=< g) = \x -> g x >>= f

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
(g >=> f) = \x -> g x >>= f

Оператор <=< и симметричный оператор >=> с обратным порядком аргументов называются композицией Клейсли, а функции вида a -> m b – стрелками Клейсли. Это понятия, опять, из теории категорий, и, опять, не будем на этом останавливаться.

Собственно законы монад, рассмотренные в предыдущей лекции, более просто выражаются через композицию Клейсли:

Левая идентичность: return >=> k ≡ k
Правая идентичность: m >=> return ≡ m
Ассоциативность: f >=> (k >=> h) ≡ (f >=> k) >=> h

По сути законы требуют, чтобы композиция Клейсли над стрелками Клейсли образовывала категорию.

Некоторые стандартные монады

`Maybe`

Тип Maybe, позволяющий закодировать частично-определённую функцию в полностью определённой, является монадой. Напомним определение Maybe:

data Maybe a = Nothing | Just a

Рассмотрим минимальное определение:

instance  Functor Maybe  where
    fmap _ Nothing       = Nothing
    fmap f (Just a)      = Just (f a)

instance Applicative Maybe where
    pure = Just

    Just f  <*> m       = fmap f m
    Nothing <*> _m      = Nothing

instance  Monad Maybe  where
    (Just x) >>= k      = k x
    Nothing  >>= _      = Nothing

Экземпляр Functor описывает, как применяются функции, определённые над значениями, к значениям, “завёрнутым” в Maybe: результатом значения Nothing всегда является Nothing, результатом значения Just x – Just результат применения функции к x.

Экземпляр Applicative описывает, в операторе <*>, как фукнции, “завёрнутые” в Maybe применяются к аргументам, “завёрнутым” в Maybe. Кроме того, как значения могут быть “завёрнуты” в Maybe в функции pure.

Если вместо функции передано значение Nothing, то результат применения такой “функции” к чему бы то ни было – Nothing. В противном случае, <*> по поведению совпадает с fmap.

Наконец, экземпляр Monad описывает (несколько окружным путём) композицию функций, возвращающих Maybe: если первая функция вернула Nothing, то нет смысла (и возможности) вычислять вторую, можно сразу вернуть Nothing.

С прикладной точки зрения, монаду Maybe удобно использовать для последовательностей вычислений (в широком смысле), которые на любом шаге могут закончиться неудачей. Типовый пример – поиск значения в какой-то базе данных:

import Data.List

newtype ItemId = ItemId Word deriving (Eq)
newtype CatId = CatId Word deriving (Eq)
type ItemName = String
type CategoryName = String

itemsTable :: [(ItemId, ItemName)]
itemsTable = [ (ItemId 1, "Ноутбук")
             , (ItemId 2, "Клавиатура")
             , (ItemId 3, "Трекбол")
             , (ItemId 4, "Монитор")
             , (ItemId 5, "Утюг")
             , (ItemId 6, "Холодильник")
             ]

categoriesTable :: [(CatId, CategoryName)]
categoriesTable = [ (CatId 1, "Компьютерная техника")
                  , (CatId 2, "Периферийные устройства")
                  , (CatId 3, "Манипуляторы")
                  , (CatId 4, "Бытовая техника")
                  ]

linkingTable :: [(ItemId, CatId)]
linkingTable = [
    (ItemId 1, CatId 1)
  , (ItemId 2, CatId 1)
  , (ItemId 2, CatId 2)
  , (ItemId 3, CatId 1)
  , (ItemId 3, CatId 2)
  , (ItemId 3, CatId 3)
  , (ItemId 4, CatId 1)
  , (ItemId 4, CatId 2)
  , (ItemId 5, CatId 4)
  , (ItemId 6, CatId 4)
  ]

getCategoryForItem :: ItemName -> Maybe CategoryName
getCategoryForItem searchName = do
  itemId <- fst <$> find (\(key, value) -> value == searchName) itemsTable
  -- результат Nothing если в itemsTable нет элемента с именем searchName
  categoryId <- lookup itemId linkingTable
  -- результат Nothing если в linkingTable нет записей для данного itemId
  lookup categoryId categoriesTable
  -- финальный результат

здесь в роли “базы данных” выступают списки, но на практике это может быть, например, файл на диске или сервер SQL. Рассмотрим как работает функция getCategoryForItem. Для этого перепишем do-нотацию через >>=:

getCategoryForItem searchName =
  fst <$> find (\(key, value) -> value == searchName) itemsTable
  >>= \itemId -> lookup itemId linkingTable
  >>= \categoryId -> lookup categoryId categoriesTable

По порядку, find (\(key, value) -> value == searchName) itemsTable находит первый элемент в списке itemsTable, где второй элемент кортежа равен searchName. Если значение найдено, то результат – Just (key, value), иначе Nothing. fst <$> использует оператор <$>, эквивалентный fmap. По определению fmap для Maybe, приведённому выше, fst применяется к значению под Just, либо результат – Nothing, если аргумент – Nothing. Вся первая строчка таким образом имеет значение Just key или Nothing.

Далее срабатывает первый оператор >>=, по определению, если первая строчка – Nothing, то результат всего выражения – Nothing и вычисление прерывается. Иначе, значение под Just передаётся в функцию \itemId -> ....

lookup itemId linkingTable имеет значение Nothing или Just catId. Срабатывает второй оператор >>=, в первом случае, результат всего выражения – Nothing, во втором – значение catId передаётся в функцию \categoryId -> ....

Наконец результатом всей конструкции является lookup categoryId categoriesTable.

Таким образом, если какой-то из промежуточных шагов вычисления возвращает Nothing, то вычисление прерывается и результат – Nothing. В противном случае, значение под Just передаётся дальше.

`Either a`

Конструктор типа Either является конструктором двух параметров, поэтому сам по себе он не может быть функтором или монадой (эти классы типов определены для конструкторов типов одного параметра). Но конструкторы типов тоже можно применять частично, поэтому Either a для любого типа a является конструктором типа одного параметра, и, следовательно, для него можно реализовать экземпляр Functor. Этот тип практически аналогичен Maybe, но Nothing может иметь дополнительное значение какого-то (фиксированного!) типа a.

Напомним,

data  Either a b  =  Left a | Right b

Рассмотрим определение:

instance Functor (Either a) where
    fmap _ (Left x) = Left x
    fmap f (Right y) = Right (f y)

instance Applicative (Either e) where
    pure          = Right
    Left  x <*> _ = Left x
    Right f <*> r = fmap f r

instance Monad (Either e) where
    Left  x >>= _ = Left x
    Right r >>= k = k r

Если сравнить с определением для Maybe, то вся разница только в том, что вместо Nothing используется Left x, а вместо Just – Right.

Понятно, работает так же, как Maybe. Это простейшая монада “ошибки с описанием”. Можно написать функции

catchError :: Either e a -> (e -> Either e' a) -> Either e' a
catchError (Left  l) handler = handler l
catchError (Right r) _ = Right r

throwError :: e -> Either e a
throwError = Left

и использовать их как проброс исключений. Например, очень многословный вариант на тему кода выше:

getCategoryForItem'' :: ItemName -> Either String CategoryName
getCategoryForItem'' searchName = do
  let mItemId = fst <$> find (\(key, value) -> value == searchName) itemsTable
  case mItemId of
    Nothing -> throwError "Item not found"
    Just itemId -> do
      let mCategoryId = lookup itemId linkingTable
      case mCategoryId of
        Nothing -> throwError "Category for item not found"
        Just catId -> do
          let mCategoryName = lookup catId categoriesTable
          case mCategoryName of
            Nothing -> throwError "Category not found"
            Just catName -> pure catName

Конечно этот же код можно гораздо проще записать в виде

getCategoryForItem'' :: ItemName -> Either String CategoryName
getCategoryForItem'' searchName = do
  itemId <- fst <$> find (\(key, value) -> value == searchName) itemsTable
    `onError` "Item not found"
  categoryId <- lookup itemId linkingTable
    `onError` "Category for item not found"
  lookup categoryId categoriesTable
    `onError` "Category not found"
  where
  infix 0 `onError`
  onError Nothing  msg = throwError msg
  onError (Just x) msg = Right x

`[]`

Для конструктора типа списка тоже можно определить экземпляр Monad. Такая монада будет соответствовать нондетерминизму или многовариантности. В частности, с помощью монады списка можно очень легко написать модель недетерминированного автомата. Посмотрим на минимальное определение:

instance Functor [] where
    fmap = map

instance Applicative [] where
    pure x    = [x]
    fs <*> xs = concatMap (\f -> map f xs) fs

instance Monad []  where
    xs >>= f = concatMap f xs

Здесь можно заметить, что pure просто создаёт список одного элемента. Операции же >>= и <*> используют concatMap – если разобрать их определения, то перебираются все возможные варианты для всех элементов и возвращаются все возможные значения.

Так, например, недетерминированный конечный автомат без ε-переходов можно выразить в виде:

type State = Word

runNFA :: (State -> Char -> [State]) -> State -> [Char] -> [State]
runNFA _               _            [] = []
runNFA transitionTable initialState (ch:restOfInput) = do
  nextState <- transitionTable initialState ch
  runNFA transitionTable nextState restOfInput

или используя функцию foldlM над входной строкой:

type State = Word

runNFA :: (State -> Char -> [State]) -> State -> [Char] -> [State]
runNFA transitionTable initialState input = foldlM transitionTable initialState input
-- эквивалентно
-- runNFA = foldlM

`(,) a`

Для пар значений оказывается тоже возможно определить экземпляр Monad, параметризованный по типу второго значения, если первый аргумент является моноидом, т.е. поддерживает бинарную ассоциативную операцию и существует нейтральный элемент. Минимальное определение:

instance Functor ((,) a) where
    fmap f (x,y) = (x, f y)

instance Monoid a => Applicative ((,) a) where
    pure x = (mempty, x)
    (u, f) <*> (v, x) = (u <> v, f x)

instance Monoid a => Monad ((,) a) where
    (u, a) >>= k = case k a of (v, b) -> (u <> v, b)

`Writer w`

Более общепринятое название для монады пары – Writer. Эта монада представляет операции, которые могут “записывать” что-то в процессе работы. Собственно, пара – не единственная такая монада.

Вообще говоря, существует два варианта Writer, “строгий” и “ленивый”. Вариант для пары выше – строгий, в то время как реализация Writer по умолчанию ленивая. К вопросам строгости вернёмся в следующей лекции.

Будем называть элемент, являющийся моноидом (в котором хранится то, что “записывают” вычисления) – “выводом”.

Все монады типа Writer поддерживают операции:

writer :: (a, w) -> m a

“Заворачивает” пару значений (результат, вывод) в монаду Writer.

tell :: w -> m ()

Добавляет аргумент к выводу

listen :: m a -> m (a, w)

“Читает” вывод аргумента и возвращает его вместе с результатом вычисления

pass :: m (a, w -> w) -> m a

Модифицирует вывод.

Для удобства вводится также функция

censor :: (w -> w) -> m a -> m a

применяющая функцию в первом аргументе к выводу второго аргумента.

Собственно, все монады, являющиеся Writer объединяются в класс MonadWriter, определённый в пакете mtl в модуле Control.Monad.Writer.Class.

Собственно, типовый представитель этого класса, Writer w a, объявлен в модуле Control.Monad.Writer.

Вычисления в Writer w a производятся при помощи функции

runWriter :: Monoid w => Writer w a -> (a, w)

`(->) a`

Можно определить экземпляр Monad для функций, параметризованных по возвращаемому значению. Оператор “стрелка” -> по сути является конструктором типов двух аргументов, поэтому мы можем подойти к нему с той же позиции, что к конструкторам Either и (,):

instance Functor ((->) r) where
    fmap = (.)

instance Applicative ((->) a) where
    pure = const
    liftA2 q f g = \x -> q (f x) (g x)

instance Monad ((->) r) where
    f >>= k = \r -> k (f r) r

fmap – это просто композиция функций. Действительно, если мы рассматриваем функцию типа a -> b и хотим применить функцию b -> c к её результату, то композиция – это как раз то, что нам нужно.

pure определён как константная функция (т.е. функция, всегда возвращающая одно и то же). Действительно, если мы делаем функцию из значения, то единственный вариант, сохраняющий поведение – это функция, всегда возвращающая это значение независимо от аргумента.

liftA2 передаёт каждой из функций-аргументов одинаковый аргумент.

Оператор >>= действует над возвращаемыми значениями функций, не изменяя аргумента.

`Reader`

Более общепринятое называние для монады функций – Reader. Эта монада, по сути, отражает множество операций, которые могут “читать”, но не изменять, некое “окружение” – которое передаётся просто как аргумент функции. Вообще говоря, монада функции – не единственная, которая ведёт себя как Reader.

Все монады, удовлетворяющие концепции Reader поддерживают функции:

ask :: m r

Возвращает “окружение”

local :: (r -> r) -> m a -> m a

Первым аргументом принимает функцию, изменяющую окружение, и выполняет вычисление, переданное вторым аргументом, в изменённом окружении.

reader :: (r -> a) -> m a

Превращает функцию, принимающую аргумент “окружения” в вычисление в монаде.

Собственно, все монады, являющиеся Reader объединяются в класс MonadReader, определённый в пакете mtl в модуле Control.Monad.Reader.Class.

Собственно, типовый представитель этого класса, Reader r a, объявлен в модуле Control.Monad.Reader.

Вычисления в Reader r a производятся при помощи функции

runReader :: Reader r a -> r -> a

`State`

После рассмотрения Reader и Writer, может возникнуть мысль, что изменяемое состояние тоже можно закодировать при помощи монады. Действительно, это возможно, и такая монада называется State.

Тип State традиционно определяется как

newtype State s a
  = State { runState :: s -> (a, s) }

Можно провести параллели с монадой Reader, абстрагирующей функцию, принимающую аргумент, и монадой Writer, абстрагирующей пару.

instance Functor (State s) where
    fmap f x = State $ \s ->
        let (a, s') = runState x s
        in (f a, s')

instance Applicative (State s) where
    pure a = State $ \s -> (a, s)
    State f <*> State x = State $ \ s ->
      let (f, s') = f s
          (x, s'') = x s'
      in (f x, s'')

instance (Monad m) => Monad (State s) where
  m >>= k  = State $ \s ->
      let (a, s') = runState m s
      in runState (k a) s'

Отметим, что из-за использования let у нас получается “ленивая” монада State. Если бы мы использовали case, получилась бы “строгая”. Подробное обсуждение этой темы оставим на следующую лекцию.

Собственно, это не единственная монада State, так же как Reader и Writer.

Все монады, удовлетворяющие концепции State поддерживают функции:

get :: m s

Аналогично ask, получает текущее состояние.

put :: s -> m ()

Похоже на tell, но не добавляет, а заменяет текущее состояние.

state :: (s -> (a, s)) -> m a

Превращает функцию, принимающую состояние и возвращающую новое состояние в вычисление в монаде.

Кроме того, есть вспомогательные функции

gets :: (s -> a) -> m a

принимает проекцию состояния на значение и возвращает применение этой проекции к текущему состоянию (состояние не изменяется)

modify :: (s -> s) -> m ()

Применяет к состоянию функцию, изменяющую его.

Собственно, все монады, являющиеся State объединяются в класс MonadState, определённый в пакете mtl в модуле Control.Monad.State.Class.

Вычисления в State s a производятся при помощи функции

runState :: State s a -> s -> (a, s)

Кроме того есть функции

evalState :: State s a -> s -> a
execState :: State s a -> s -> s

возвращающие только результат и только финальное состояние соответственно.

С помощью State можно моделировать любые процессы с изменяемым состоянием. Например, ДКА:

type DFAState = Word

runDFA :: (Char -> DFAState -> DFAState)
       -> [Char]
       -> State DFAState ()
runDFA transitionTable [] = pure ()
runDFA transitionTable (ch:restOfInput) = do
  modify (transitionTable ch)
  runDFA transitionTable restOfInput

или, используя функцию mapM_ (вариант mapM, отбрасывающий результат)

runDFA :: (Char -> DFAState -> DFAState)
       -> [Char]
       -> State DFAState ()
runDFA transitionTable input = mapM_ (modify . transitionTable) input
-- эквивалентно
-- runDFA = mapM_ . (modify .)

`ST`

Мы переходим к “магическим” монадам – монадам, которые не определяются в терминах стандартного Haskell, и задача которых – обеспечить взаимодействие с “внешним миром”. Монада ST абстрагирует работу с памятью и позволяет работать с изменяемыми участками памяти, в частности, с переменными (в императивном смысле) и массивами (в смысле непрерывных участков изменяемой памяти).

Обычно, монада ST не нужна. Однако, некоторые алгоритмы значительно проще (и эффективнее!) в императивной парадигме. Поэтому иногда оказывается очень удобно вставить кусочек “почти императивного” кода в функциональный.

На самом деле с теоретической точки зрения, монада ST ничем не отличается от монады State. Однако реализация у них – сильно разная.

Основные функции для работы с изменяемыми значениями в монаде ST:

newSTRef :: a -> ST s (STRef s a)

Создаёт новую переменную и инициализирует её значением первого аргумента.

readSTRef :: STRef s a -> ST s a

Читает значение переменной.

writeSTRef :: STRef s a -> a -> ST s ()

Записывает значение в переменную.

`IO`

Монада IO абстрагирует всю работу с “внешним миром”, которая в целом сводится к вводу-выводу. О ней можно думать как о более сложном варианте монады ST, где в качестве состояния используется тип RealWorld, абстрагирующий состояние “внешнего мира”.

Ключевое отличие IO от ST и State в том, что RealWorld – на самом деле своего рода фикция: на самом деле никакого “состояния” RealWorld в скомпилированной программе нет (в отличие от State где для хранения состояния используется участок памяти). Вместо этого, использование IO сигнализирует компилятору, что порядок операций в IO при выполнении должен быть таким же, как в исходном тексте программы, и что нельзя применять многие оптимизации, которые можно применять в функционально чистом коде – в частности, нельзя “выбрасывать” повторяющиеся вычисления, поскольку состояние “внешнего мира” могло измениться и, следовательно, результат вычислений тоже мог измениться.

Любое значение в программе на Haskell, имеющее тип IO a является своего рода инструкцией, как получить значение a, взаимодействуя с внешним миром. Эта инструкция является “чистой”, в смысле сама по себе не имеет побочных эффектов. Её можно передавать как значение, над ней можно совершать манипуляции, как над любым другим значением в монаде. Эта “инструкция” будет выполнена тогда и только тогда, когда она будет объединена с IO в функции main (главной точке входа в программу). И именно тогда возникнут все связанные побочные эффекты. Под “объединением” имеется ввиду следующая операция. В модуле Control.Monad объявлена функция join:

join   :: (Monad m) => m (m a) -> m a
join x = x >>= id

Как видно из типа этой функции, она убирает один уровень вложенности какой-то монады m (например, она работает как конкатенация для монады списка). Определение этой функции просто применяет оператор >>= к функции идентичности.

То есть, если какое-то действие IO a в какой-то момент передаётся в вычисление, которое в результате вернётся как результат функции main, это действие IO a будет выполнено.

В качестве примера, рассмотрим два фрагмента кода:

main :: IO ()
main = do
  let action = putStrLn "Hello, World!"
  return ()

Этот код ничего не делает – вызов putStrLn никогда не объединяется с IO в main. Действительно, если записать этот код без do-нотации, то получится

main :: IO ()
main = let action = putStrLn "Hello, World!" in return ()

main :: IO ()
main = do
  action <- putStrLn "Hello, World!"
  return ()

Этот код выведет строку Hello, World!, поскольку, если убрать do-нотацию, мы увидим:

main :: IO ()
main = putStrLn "Hello, World!" >>= \action -> return ()

Несмотря на то, что значение action (которое в силу типа putStrLn является единичным ()) не используется, действие, необходимое для получения этого значения (а именно, putStrLn "Hello, World!") должно быть выполнено перед тем, как функция main сможет вернуть результат (), поскольку оно объединяется с результатом main оператором >>=.

Первый код можно исправить следующим образом:

main :: IO ()
main = do
  let action = putStrLn "Hello, World!"
  action
  return ()

Без do-нотации:

main = let action = putStrLn "Hello, World!" in action >>= \_ -> return ()

или, эквивалентно

main = let action = putStrLn "Hello, World!" in action >> return ()

Композиция типов

Часто бывает нужна монада, которая например ведёт себя одновременно, например, как Reader и Writer. Для этого используются трансформаторы монад. Рассмотрим сначала более простую идею: композицию типов в общем.

Рассмотрим функции

id :: a -> a
id x = x

(.) :: (b -> c) -> (a -> b) -> a -> c
(f . g) = \x -> f (g x)

Проводя аналогию между функциями над значениями и конструкторами типов (над типами), мы можем записать следующие аналогичные определения типов. Начнём с id.

newtype Identity a = Identity { runIdentity :: a}

Типы в Haskell бывают различными: мы уже сталкивались с этим, когда говорили про некоторые классы типов, определённые для конструкторов типов. Haskell использует понятие “род” (kind) для классификации типов.

Обычные типы имеют род Type или * (это синонимы). Конструкторы типов одного аргумента имеют род Type -> Type или * -> *, конструкторы типов двух аргументов имеют род Type -> Type -> Type или * -> * -> * и так далее.

В GHCi можно вывести род типа, выполнив команду :kind Typename. Так, объявленный выше тип Identity будет иметь род * -> *, поскольку это конструктор типа одного аргумента.

Identity является монадой (т.е. можно написать экземпляры Functor, Applicative и Monad):

instance Functor Identity where
  fmap f (Identity x) = Identity (f x)

instance Applicative Identity where
  pure = Identity
  (Identity f) <*> (Identity x) = Identity (f x)

instance Monad Identity where
  (Identity x) >>= f = f x

Чтобы написать аналог оператора (.) на уровне типов, нам нужно сконструировать тип, имеющий род (* -> *) -> (* -> *) -> * -> * (ср. с типом оператора (.)).

Глядя на сигнатуру рода, мы можем сделать вывод, что это конструктор типа трёх аргументов, два из которых – конструкторы одного аргумента, а третий – обычный тип:

newtype Compose f g a =
    Compose { getCompose :: f (g a) }

(это определение есть в модуле Data.Functor.Compose)

На практике, это может выглядеть, например так:

> let x = [Just (1::Int), Nothing]
> let y = Compose x
> :t x
x :: [Maybe Int]
> :t y
y :: Compose [] Maybe Int

Собственно, сама композиция – это Compose [] Maybe, и она применяется к типу Int, в результате получается [Maybe Int].

Мы сравнительно легко можем написать экземпляры Functor и Applicative для композиции функторов:

instance (Functor f, Functor g)
  => Functor (Compose f g) where
  fmap f (Compose x) = Compose $ fmap (fmap f) x

instance (Applicative f, Applicative g)
  => Applicative (Compose f g) where
  pure x = Compose $ pure (pure x)
  (Compose f) <*> (Compose x)
    = Compose $ fmap (<*>) f <*> x

Этого достаточно для многих практически важных случаев. Однако в случае с Monad нас ожидает трудность:

instance (Monad f, Monad g)
  => Monad (Compose f g) where
  (Compose x) >>= f
    = ???

Не будем останавливаться на доказательстве того, что это невозможно¹, лишь отметим, что тот же подход, что и с функторами не работает.

Трансформаторы монад

Проблема с монадами в том, что можно записать композицию двух монад, но композиция двух монад сама по себе не является монадой.

В связи с этой трудностью вводится понятие трансформатора монады. Трансформатор монады – это конструктор типа, который принимает монаду в качестве аргумента и возвращает новую монаду.

Основная проблема композиции двух монад – в недостатке информации. Если фиксировать “внешнюю” монаду, то мы, собственно, и получим трансформатор монад. Таким образом, для каждой монады существует так же и трансформатор монад.

Рассмотрим введённую выше монаду Identity:

newtype Identity a = Identity { runIdentity :: a }

Как может выглядеть трансформатор монады IdentityT?

newtype IdentityT m a =
    IdentityT { runIdentityT :: m (Identity a) }

Мы добавили новый аргумент типа, имеющий род * -> * к конструктору Identity, и можем получить нижележащее значение IdentityT, выполнив runIdentityT. Эта конструкция в каком-то смысле эквивалентна условной конструкции

data Compose m Identity a
  = Compose { getCompose :: m (Identity a) }

(это строго говоря некорректный синтаксис)

Давайте попробуем описать монаду для IdentityT:

instance Functor m => Functor (IdentityT m) where
  fmap f (IdentityT x) = IdentityT $ fmap (fmap f) x

instance Applicative m
  => Applicative (IdentityT m) where
  pure x = IdentityT $ pure (pure x)

  (IdentityT f) <*> (IdentityT x)
    = IdentityT $ fmap (<*>) f <*> x

instance Monad m => Monad (IdentityT m) where
  (IdentityT x) >>= f
    = IdentityT $ fmap runIdentity x
              >>= runIdentityT . f

Это ключевой момент: поскольку мы знаем, как можно “выполнить” монаду (Identity), мы можем “достать” вторую, сделать с ней всё, что требуется, затем “завернуть” обратно во внешнюю.

В случае Compose такой возможности мы не имели, поскольку интерфейс монады в общем случае не поддерживает универсального способа её “выполнить” (в случае например IO это невозможно в терминах стандартного Haskell)

Рассмотрим теперь некоторые стандартные трансформаторы монад.

`MaybeT`

newtype MaybeT m a =
  MaybeT { runMaybeT :: m (Maybe a) }

instance Functor m => Functor (MaybeT m) where
  fmap f (MaybeT ma) =
    MaybeT $ (fmap . fmap) f ma

instance Applicative m => Applicative (MaybeT m) where
  pure = MaybeT . pure . pure
  (MaybeT f) <*> (MaybeT x)
    = MaybeT $ fmap (<*>) f <*> x

instance Monad m => Monad (MaybeT m) where
  (MaybeT x) >>= f
    = MaybeT $
      x >>= maybe (pure Nothing)
                  (runMaybeT . f)

Экземпляры Functor и Applicative не представляют из себя ничего интересного, это экземпляры для композиции типов.

Экземпляр Monad здесь работает аналогично экземпляру для Maybe, что может быть проще увидеть, если переписать код через do-нотацию:

instance Monad m => Monad (MaybeT m) where
  (MaybeT x) >>= f = MaybeT $ do
    ma <- x
    case ma of
      Nothing -> pure Nothing
      Just x -> runMaybeT (f x)

Для сравнения:

instance Monad Maybe where
    x >>= k = case x of
      Nothing -> Nothing
      Just y -> k y

`EitherT`

newtype EitherT e m a =
  EitherT { runEitherT :: m (Either e a) }

instance Monad m => Monad (EitherT e m) where
  (EitherT x) >>= f
    = EitherT $
      x >>= either (pure . Left)
                   (runEitherT . f)

Здесь опустим экземпляры для Functor и Applicative, они практически одинаковые для всех трансформаторов монад.

Если переписать экземпляр Monad через do-нотацию:

instance Monad m => Monad (EitherT e m) where
  (EitherT x) >>= f = EitherT $ do
      ea <- x
      case ea of
        Left e -> pure (Left e)
        Right x -> runEitherT (f x)

Для сравнения:

instance Monad (Either e) where
    x >>= f = case x of
      Left e -> Left e
      Right x -> f x

Вообще, EitherT в библиотеке называется ExceptT

`ReaderT`

newtype ReaderT r m a =
  ReaderT { runReaderT :: r -> m a }

instance Monad m => Monad (ReaderT r m) where
  (ReaderT x) >>= f
    = ReaderT $ \r -> do
        y <- x r
        runReaderT (f y) r

Для сравнения:

instance Monad (Reader r) where
  (Reader x) >>= f
    = Reader $ \r -> runReader (f (x r)) r

`StateT`

newtype StateT s m a =
  StateT { runStateT :: s -> m (a, s) }

instance Monad m => Monad (StateT s m) where
  x >>= f
    = StateT $ \s -> do
        ~(a, s') <- runStateT x s
        runStateT (f a) s'

Для сравнения:

instance (Monad m) => Monad (State s) where
  x >>= k  = State $ \s ->
      let (a, s') = runState x s
      in runState (k a) s'

Обычные монады из трансформаторов монад

На самом деле, для монад Reader, State и т.п. “простые” монады не определяются явно, вместо этого они определяются в терминах трансформаторов. Например, Reader можно легко получить из ReaderT, просто применив его к Identity:

type Reader r a = ReaderT r Identity a

runReader :: Reader r a -> r -> a
runReader m r = runIdentity (runReaderT m r)

Порядок записи и порядок вложенности

Порядок записи типов трансформаторов монад может быть несколько неинтуитивным в смысле того, что представляют значения и в каком порядке их вычислять.

Рассмотрим для примера следующий код:

mval :: EitherT String (
  MaybeT (
    ReaderT () Identity
    )
  ) Int
mval = return 0

Чтобы “вычислить” весь этот стек монад, мы должны выполнить все трансформаторы, начиная с внешнего:

val = runIdentity (
  runReaderT (
    runMaybeT (runEitherT mval)
  ) ())

Отметим, что в силу порядка применения функций, синтаксически вычисление “внешнего” трансформатора в типе оказывается “внутренним” выражением.

но какой тип будет у val? Вспомним, что

runEitherT :: EitherT e m a -> m (Either e a)

Тогда тип x = runEitherT mval будет

x :: MaybeT (ReaderT () Identity)
            (Either String Int)

Аналогично,

runMaybeT :: MaybeT m a -> m (Maybe a)

и тип y = runMaybeT x будет

y :: ReaderT () Identity
            (Maybe (Either String Int))

Наконец,

runReaderT :: r -> m a

и тип z = runReader y ()

z :: Identity (Maybe (Either String Int))

после чего runIdentity просто убирает “лишний” слой Identity.

Что здесь примечательно: трансформаторы вычисляются от “внешнего” к “внутреннему” в записи типа, но значение, которое получается, имеет монаду внешнего трансформатора на внутренней позиции и т.д. Это прямо связано с порядком вычисления и с необходимостью иметь монаду на внешнем уровне вложенности после “выполнения” каждого трансформатора (если бы это было не так, мы не могли бы последовательно применять функции runSomethingT).

Другие трансформаторы монад

Можно заметить, что мы не рассматривали трансформаторы для монад списков и Writer. Это связано в основном с тем, что их не так просто написать.

Практически, WriterT, как и Writer используется достаточно редко, в основном поскольку он подходит только для достаточно специфических применений. В частности, он не слишком хорошо подходит для логгирования.

Что касается трансформатора списка, наивная реализация, доступная в библиотеке transformers, не удовлетворяет закону ассоциативности, как следствие, приводит к неожиданным результатам. Корректная реализация же (доступная в библиотеке list-t) достаточно сложная и медленная. На практике вместо трансформаторов списка используются библиотеки, работающие с “потоками”, такие как streaming, conduit, pipes, или streamly. Для восприятия, возможно, проще всего streamly, conduit пока, видимо, наиболее мощный, но довольно сложный инструмент.

MonadTrans

Для трансформаторов монад обычно пишется экземпляр класса MonadTrans:

class MonadTrans t where
    lift :: (Monad m) => m a -> t m a

Функция lift “поднимает” операцию вложенной монады на уровень стека трансформаторов. Например,

import Control.Monad.Except

safeIntegerDivision :: Int -> Int -> Maybe Int
safeIntegerDivision a b
  | b == 0 = Nothing
  | otherwise = Just (a `div` b)

doStuff :: Int -> Int -> ExceptT String Maybe Int
doStuff a b = do
  val <- lift $ safeIntegerDivision a b
  when (val == 0) $ throwError "Value is zero!"
  return val

Здесь функция safeIntegerDivision возвращает Maybe Int, но с помощью lift мы используем этот результат в контексте ExceptT String Maybe Int. Одно применение lift “поднимает” один уровень стека. Идеологически, принцип похож на pure с тем отличием, что вместо “чистых” значений, “поднимаются” значения в монадах.

Реализация MonadTrans в большинстве случаев достаточно простая, например

instance MonadTrans MaybeT where
  lift :: (Monad m) => m a -> MaybeT m a
  lift ma = MaybeT $ fmap Just ma

Некоторая проблема с использованием lift заключается в том, что наивное использование приводит к коду типа такого

lift $ lift $ lift $ lift $ lift $ lift $ lift $ put i'

Одним из наиболее удачных решений этой проблемы может быть объявление собственного трансформатора, который представляет из себя стек трансформаторов, например:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Control.Monad.Except
import Control.Monad.Reader
import Control.Monad.Trans.Maybe

newtype ReaderExceptMaybeT r e m a
  = ReaderExceptMaybeT {
      runREMT :: ReaderT r (ExceptT e (MaybeT m)) a
    } deriving ( Functor
               , Applicative
               , Monad
               , MonadReader r
               , MonadError e
               )

instance MonadTrans (ReaderExceptMaybeT r e) where
  lift = ReaderExceptMaybeT . lift . lift . lift

И в случае необходимости, написание вспомогательных функций:

liftREMTMaybe :: Monad m
              => MaybeT m a
              -> ReaderExceptMaybeT r e m a
liftREMTMaybe  = ReaderExceptMaybeT . lift . lift

liftREMTExcept :: Monad m
               => ExceptT e (MaybeT m) a
               -> ReaderExceptMaybeT r e m a
liftREMTExcept  = ReaderExceptMaybeT . lift

MonadIO

Заходящий с другого конца, есть класс, позволяющий “поднимать” действия в IO сразу до верха стека трансформаторов:

class (Monad m) => MonadIO m where
  liftIO :: IO a -> m a

Экземпляр при наличии экземпляра MonadTrans можно объявить следующим образом:

instance MonadIO m
  => MonadIO (ReaderExceptMaybeT r e m) where
  liftIO = lift . liftIO

Для интересующихся, http://web.cecs.pdx.edu/~mpj/pubs/RR-1004.pdf, стр. 44↩︎

Некоторые стандартные монады. Композиция типов. Трансформаторы монад.

Некоторые стандартные монады

Maybe

Either a

[]

(,) a

Writer w

(->) a

Reader

State

ST

IO

Композиция типов

Трансформаторы монад

MaybeT

EitherT

ReaderT

StateT

Обычные монады из трансформаторов монад

Порядок записи и порядок вложенности

Другие трансформаторы монад

MonadTrans

MonadIO

`Maybe`

`Either a`

`[]`

`(,) a`

`Writer w`

`(->) a`

`Reader`

`State`

`ST`

`IO`

`MaybeT`

`EitherT`

`ReaderT`

`StateT`