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

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

Часто нужна монада, которая одновременно, например, 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 использует понятие “род” (kind) для классификации типов.

Обычные типы имеют род Type или * (синонимы).

Конструкторы одного аргумента – род Type -> Type или * -> *

Конструкторы двух аргументов – род Type -> Type -> Type или * -> * -> *

И т.д.

В GHCi вывести род типа – команда :kind Typename.

Identity имеет род Type -> Type – конструктор типа одного аргумента.

Identity является (скучной) монадой:

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

Аналог оператора (.) на уровне типов имеет род

type Compose :: (Type -> Type) -> (Type -> Type) -> Type -> Type

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

(.) :: (b -> c) -> (a -> b) -> a -> c

type Compose :: (Type -> Type) -> (Type -> Type) -> Type -> Type

Из рода, вывод – конструктор трёх аргументов, два из которых – конструкторы одного аргумента, третий – обычный:

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].

Для Compose сравнительно легко получаются экземпляры 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) }

Добавили аргумент m :: Type -> Type.

Примерно эквивалентно условной конструкции

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 такой возможности нет, т.к. ни одна монада не фиксирована.

`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

Functor и Applicative неинтересные, повторяют Compose.

Monad аналогично Maybe:

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

Через 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 – те же. Здесь и далее опускаем.

Через 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)
  ) ())

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

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

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

Какой тип у val?

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

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

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 a -> a
val = runIdentity z

val :: Maybe
  (Either String Int)

mval :: EitherT String (
  MaybeT (
    ReaderT () Identity
    )
  ) Int
val :: Maybe (Either String Int)

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

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

Мы не рассматривали трансформаторы для монад списков и Writer. Они – сложные и редко используемые.

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

Наивная реализация ListT (доступная в библиотеке transformers) почти никогда не удовлетворяет закону ассоциативности ⇒ приводит к крайне неожиданным результатам.

Корректная реализация (доступная в библиотеке list-t) – достаточно сложная и медленная.

На практике используются библиотеки, работающие с “потоками”: streaming, conduit, pipes, streamly.

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

С другого конца – класс, 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