On Vox: Классы как типы

[migmit]

А мне всего-то хотелось сделать композицию трансформеров...

> {-# LANGUAGE GeneralizedNewtypeDeriving, RankNTypes, TypeOperators #-}
> module MonadM where
> import Control.Monad

Допустим, мы хотим применить к некоторой монаде несколько трансформеров. Причём, мы заранее не знаем, к какой именно монаде - но знаем, какие трансформеры. Ну, например, пусть это будут

> newtype StateT s m x = StateT {runStateT :: s -> m (s, x)}
> instance Monad m => Monad (StateT s m) where
>     return x = StateT $ \s -> return (s, x)
>     st >>= f = StateT $ \s -> runStateT st s >>= \(s', x) -> runStateT (f x) s'

и

> newtype ReaderT r m x = ReaderT {runReaderT :: r -> m x}
> instance Monad m => Monad (ReaderT r m) where
>     return x = ReaderT $ \r -> return x
>     rt >>= f = ReaderT $ \r -> runReaderT rt r >>= \x -> runReaderT (f x) r

Конечно, нет никакой проблемы написать трансформер-композицию.

newtype SRT s r m x = SRT (ReaderT r (StateT s m) x)

Далее, можно точно также объявить

instance Monad m => Monad (SRT s r m)

и жить припеваючи.

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

Попробуем это сделать. Для начала, всё-таки, объявим класс для трансформеров, чтобы не всухомятку обсуждать:

class Trans t where
    lift :: m x -> t m x

И сделаем простенькую композицию:

newtype (Trans t1, Trans t2) => (t2 :. t1) m x = Compose {runCompose :: t2 (t1 m) x} deriving Monad

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

Далее, нужно, чтобы это был снова трансформер:

instance (Trans t1, Trans t2) => Trans (t2 :. t1) where
    lift = Compose . lift . lift

Пока что, всё работает прекрасно. Давайте же сделаем два наших трансформера инстансами соответствующего класса, зарелизим библиотеку на Hackage и пойдём пить кофе с бубликами.

instance Trans (StateT s) where
    lift mx = StateT smx
        where smx s =
                  do x <- mx
                     return (s, x)

Упс. Получили ругань:

MonadM.lhs:54:23:
    Could not deduce (Monad m) from the context ()
      arising from a do statement
                   at MonadM.lhs:54:23-29
    Possible fix:
      add (Monad m) to the context of the type signature for `lift'
    In a stmt of a 'do' expression: x <- mx
    In the expression:
        do x <- mx
           return (s, x)
    In the definition of `smx':
        smx s = do x <- mx
                   return (s, x)
Failed, modules loaded: none.

Фикус в том, что для того, чтобы написать нашу функцию lift, нам нужно использовать, что аргумент засунут именно в монаду, а не во что-то ещё. Действительно нужно, это не фантазия какая-то.

Попробуем пофиксить, изменив сигнатуру lift.

class Trans t where
    lift :: Monad m => m x -> t m x

Опять облом.

MonadM.lhs:49:23:
    Could not deduce (Monad (t1 m)) from the context (Monad m)
      arising from a use of `lift'
                   at MonadM.lhs:49:23-26
    Possible fix:
      add (Monad (t1 m)) to the context of the type signature for `lift'
      or add an instance declaration for (Monad (t1 m))
    In the first argument of `(.)', namely `lift'
    In the second argument of `(.)', namely `lift . lift'
    In the expression: Compose . lift . lift
Failed, modules loaded: none.

Теперь проблема в том, что из instance Monad m и instance Trans t не следует instance Monad (t m). Практически это всегда так - по крайней мере, это так для двух трансформеров, которые мы определили в самом начале. Но у нас нет способа убедить компилятор, что это и будет всегда так.

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

В Языке Моей Мечты(tm) я бы написал так:

class Trans t where
    lift :: Monad m => m x -> t m x
    instance Monad m => Monad (t m)

После чего я перенёс бы instance Monad m => Monad (StateT s m) внутрь instance Trans (StateT s) и всё заработало бы. Увы, Язык Моей Мечты(tm) пока лишён важной утилиты, а именно, компилятора. Нет, интерпретатора тоже нет. Так что, этот способ тоже не сработает.

Попробуем иначе. Что нам нужно, так это добавить в класс Trans какую-то функцию, которая сообщит компилятору, что происходит именно преобразование монад, а не чего-то ещё. Иначе говоря, нам нужно работать с классом Monad как с типом данных.

Попробуем это сделать.

Что вообще означает, что некоторый тип T является монадой? Это означает, что для данного типа определены несколько операций. Как учит нас теория категорий, где есть алгебраические операции (или похожие на них), стоит искать... монаду. Да-да, монаду. Правда, так как наши типы имеют не тот kind, эта монада также будет монадой на другой категории. Следовательно, имеет смысл для начала определить эту категорию:

> type (m :-> n) = forall x. m x -> n x

Вот они - морфизмы нашей новой категории.

Далее, опять же, теория категорий учит, что новую монаду нужно определять так: объекту p ставится в соответствие нечто вроде "множества всех выражений, составленных при помощи заданных операций из элементов p". То есть, в нашем случае подошло бы что-то в таком духе:

data MonadM p x where
    Term :: p x -> MonadM p x
    Return :: x -> MonadM p x
    Bind :: MonadM p x -> (x -> MonadM p y) -> MonadM p y

Я, однако, предпочитаю более простой и универсальный подход. Сейчас я определю тот же тип, но по-другому. Вуаля:

> newtype MonadM p x = MonadM {bindM :: Monad m => (p :-> m) -> m x}

Это и правда то же самое. Теперь, MonadM имеет kind

*MonadM> :k MonadM
MonadM :: (* -> *) -> * -> *

и, следовательно, похож на монаду на категории типов kind-a (* -> *). Не хватает только функций return и (>>=) для полного счастья. Сейчас мы их определим.

Начнём с return. Обычно, эта функция имеет тип x -> m x (так она определена в классе Monad). У нас, следовательно, тип будет

> term :: p :-> MonadM p

Такую функцию написать несложно, и делается это, по существу, единственным образом:

> term px = MonadM $ \hom -> hom px

Далее, оператор (>>=). Он у нас, по сути, уже есть. Это функция bindM. Её тип поначалу не кажется похожим на то, что нам нужно, но только потому, что у нас не хватает ещё одного важного элемента:

> instance Monad (MonadM p) where
>     return x = MonadM $ \hom -> return x
>     mpx >>= f = MonadM $ \hom -> bindM mpx hom >>= \x -> bindM (f x) hom

В этом определении мы просто говорим, что правая часть, по существу, совпадает с левой, только вокруг тех штук, которые имеют тип MonadM p x добавляется некий line noise в виде bindM и hom.

Теперь мы видим, что функция bindM имеет тип, который, во всяком случае, не хуже, чем то, что нам нужно:

*MonadM> :set -XTypeOperators -XRankNTypes
*MonadM> :t bindM :: MonadM p x -> (p :-> MonadM p) -> MonadM p x
bindM :: MonadM p x -> (p :-> MonadM p) -> MonadM p x
  :: MonadM p x -> (p :-> MonadM p) -> MonadM p x

Хорошо. Далее, то, чему не учат в Haskell-школах: конкретный объект с нужными нам операциями является ни чем иным как алгеброй над подобной монадой. В нашем случае это значит, что каждая монада является алгеброй над MonadM. Более конкретно, для каждой монады есть отображение

alg :: Monad m => MonadM m :-> m

Именно, оно пишется так:

alg (MonadM h) = h id

В данном случае, id имеет тип m :-> m.

Как же это поможет нам решить нашу проблему? А вот как: по сути дела, указать для некоторого типа отображение alg и определить для этого же типа instance Monad - одно и то же. !. Я определю специальный тип:

> newtype Inst m = Inst {getInst :: MonadM m :-> m}

и навешу конструктор на alg следующим образом:

> alg :: Monad m => Inst m
> alg = Inst $ \mmx -> bindM mmx id

Далее, идеология происходящего следующая. Если нам нужно что-то сделать с типом m, для чего требуется instance Monad, а у нас вместо него только значение inst :: Inst m, то мы проделываем всё необходимое, используя вместо m тип MonadM m (который всегда является монадой - определение только что было), а потом переносим это на тип m, используя при этом отображения term :: m :-> MonadM m и getInst inst :: MonadM m :-> m.

Для того, чтобы этот перенос осуществить, нам потребуется такой класс:

class Iso t where iso :: (m :-> n) -> (n :-> m) -> (t m :-> t n)

На самом деле, мне неизвестны трансформеры монад, которые не были бы ковариантны по этим монадам, так что можно сократить сигнатуру:

> class Iso t where iso :: (m :-> n) -> (t m :-> t n)

instance Iso обычно пишется несложно и бойлерплейт получится весьма небольшой.

В частности, например, легко написать такое:

> infixl 1 `bindM`
> instance Iso MonadM where iso hom mmx = mmx `bindM` term . hom

Заметьте, я здесь, фактически, воспроизвёл определение функции liftM:

liftM f mx = mx >>= return . f

Класс трансформеров теперь определяется так:

> class Iso t => Trans t where
>     lift :: Monad m => m x -> t m x
>     liftInst :: Inst m -> Inst (t m)

Обратите внимание на изменившийся контекст.

В частности, теперь можно сделать трансформером композицию трансформеров.

> newtype (Iso t1, Iso t2) => (t2 :. t1) m x = Compose {runCompose :: t2 (t1 m) x} deriving Monad
> infixr 9 :.

Здесь я изменил контекст с Trans на Iso, чтобы следующий инстанс выглядел более вменяемо:

> instance (Iso t1, Iso t2) => Iso (t2 :. t1) where iso hom ttmx = Compose $ iso (iso hom) $ runCompose ttmx

Ну и, как я и обещал, композиция трансформеров - трансформер:

> instance (Trans t1, Trans t2) => Trans (t2 :. t1) where

Нам нужно пройти от m x к (t2 :. t1) m x

Обычно мы пошли бы по маршруту m x --> t1 m x --> t2 (t1 m) x --> (t2 :. t1) m x.

Увы, если первый и последний шаги особых проблем не представляют, то второй шаг, увы, невозможен, так как t1 m не является монадой (по крайней мере, мы не можем убедить компилятор, что является). Однако, у нас есть значение alg :: Inst m, и, следовательно, также и значение liftInst alg :: Inst (t1 m). В соответствии с общей идеологией, мы сделаем второй шаг несколько более длинным, а именно, пройдём по маршруту t1 m x --> MonadM (t1 m) x --> t2 (MonadM (t1 m)) x --> t2 (t1 m) x.

Делаем:

    lift = Compose . step2 . lift
        where step2 = iso (getInst $ liftInst alg) . lift . term

или, коль скоро принцип ясен,

>     lift = Compose . iso (getInst $ liftInst alg) . lift . term. lift
>     liftInst = isoInst . liftInst . liftInst
>         where isoInst :: (Iso t1, Iso t2) => Inst (t2 (t1 m)) -> Inst ((t2 :. t1) m)
>               isoInst inst = Inst $ \mmx -> Compose $ getInst inst $ iso runCompose mmx

Пока всё не слишком (надеюсь) сложно. Но сумеем ли мы сделать наши StateT и ReaderT инстансами класса Trans? Ну, первая часть проблем не вызывает:

> instance Iso (StateT s) where iso hom smx = StateT $ hom . runStateT smx
> instance Trans (StateT s) where
>     lift mx = StateT smx
>         where smx s =
>                   do x <- mx
>                      return (s, x)

Здесь почти ничего не изменилось. Далее, нам нужно от Inst m перейти к Inst (StateT s m).

Если бы m было монадой, то всё было бы не просто, а очень просто: достаточно было бы использовать значение alg, поскольку instance Monad m => Monad (StateT s m) у нас уже есть. Увы, m не обязательно является монадой, однако мы начинаем со значения типа Inst m! В соответствии с общей идеологией, мы пройдём по маршруту MonadM (StateT s m) --> MonadM (StateT s (MonadM m)) --> StateT s (MonadM m) --> StateT s m следующим образом:

    liftInst inst = Inst $ iso (getInst inst) . getInst alg . iso (iso term)

У меня лично сразу проситься вынести alg в дополнительный параметр и написать так:

>     liftInst = makeLiftInst alg
> makeLiftInst :: Iso t => Inst (t (MonadM m)) -> Inst m -> Inst (t m)
> makeLiftInst alg' inst = Inst $ iso (getInst inst) . getInst alg' . iso (iso term)

Тип для функции makeLiftInst, признаюсь, написал не я, а компилятор. Ну, пусть будет.

Аналогично пишется инстанс для ReaderT:

> instance Iso (ReaderT r) where iso hom rmx = ReaderT $ hom . runReaderT rmx
> instance Trans (ReaderT r) where
>     lift mx = ReaderT $ const mx
>     liftInst = makeLiftInst alg

Обратите внимание, что объявление функции liftInst совершенно одинаковое, что для StateT, что для ReaderT. Мы можем написать ещё несколько трансформеров, но везде будет то же самое. Нельзя ли его написать, например, как дефолтную реализацию в самом классе? Попробовав, получаем

MonadM.lhs:392:30:
    Could not deduce (Monad (t (MonadM m))) from the context ()
      arising from a use of `alg'
                   at MonadM.lhs:392:30-32
    Possible fix:
      add (Monad (t (MonadM m))) to the context of
        the type signature for `liftInst'
      or add an instance declaration for (Monad (t (MonadM m)))
    In the first argument of `makeLiftInst', namely `alg'
    In the expression: makeLiftInst alg
    In the definition of `liftInst': liftInst = makeLiftInst alg
Failed, modules loaded: none.

Увы, так не получится. Причина здесь в том, что мы для каждого конкретного T определяем instance Monad m => Monad (T m) отдельно, и строчка liftInst = makeLiftInst alg как бы является обещанием, что такой инстанс определён где-то в другом месте; компилятор же это обещание тщательно проверит.

На закуску - применение трансформера к монаде. Конечно, можно применять и так, но в некоторых случаях более общий подход может пригодиться:

> newtype Monad m => (t :$ m) x = Apply {runApply :: t m x}
> infixr 0 :$
> instance (Trans t, Monad m) => Monad (t :$ m) where
>     return x = Apply $ getInst (liftInst alg) $ return x
>     tmx >>= f = Apply $ getInst (liftInst alg) $ term (runApply tmx) >>= \x -> term (runApply $ f x)

Фикус в том, что мы дописываем к значениям tmx :: (t :$ x) x мусор вида term (runApply tmx), а обратно приходим при помощи Apply . getInst (liftInst alg). В остальном же, мы просто в правой части повторяем левую.

Теперь можно писать, например, (StateT Int :. ReaderT String :$ Maybe) Char и это будет примерно (с точностью до newtype-ов) то же самое, что и (StateT Int :$ ReaderT String :$ Maybe) Char или State Int (ReaderT String (Maybe Char)).

Если кто-то вдруг захочет написать собственный трансформер MyCoolTransformer - нет проблем, пусть сделает три вещи:

1)

instance Monad m => Monad (MyCoolTransformer m)

Если этого не сделать, то непонятно, почему вообще речь идёт о трансформерах монад.

2)

lift :: m x -> MyCoolTransformer m x

Это - то, для чего трансформеры монад действительно нужны.

3) Заклинание liftInst = makeLiftInst alg, которое пишется без участия мозга. Как видим, весь бойлерплейт сведён к одной строчке - что можно записывать как победу.

Маленькое замечание: здесь мы почти не пользовались тем, что речь идёт именно о монадах. Точно то же самое можно написать про трансформеры, например, стрелок. Понадобиться только а) изменить понятие морфизма, так как стрелки имеют другой kind, б) заменить два инстанса на полностью аналогичные, один для нашей "монады" (которая, если мы заменим монады на стрелки,.. останется монадой), и один для оператора применения трансформера к монадестрелке.

Originally posted on migmit.vox.com