Являются ли аппликативные трансформаторы излишними?

Существует много разговоров о том, что Applicative не нужен собственный трансформаторный класс, например:

class AppTrans t where
    liftA :: Applicative f => f a -> t f a

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

data MStream f a = MStream (f (a, MStream f a))

Подъем только выполняет побочный эффект на каждом шагу:

instance AppTrans MStream where
    liftA action = MStream $ (,) <$> action <*> pure (liftA action)

И если f является аппликативным, то MStream f также:

instance Functor f => Functor (MStream f) where
    fmap fun (MStream stream) = MStream $ (\(a, as) -> (fun a, fmap fun as)) <$> stream

instance Applicative f => Applicative (MStream f) where
    pure = liftA . pure
    MStream fstream <*> MStream astream = MStream
        $ (\(f, fs) (a, as) -> (f a, fs <*> as)) <$> fstream <*> astream

Я знаю, что для любых практических целей f должна быть монадой:

joinS :: Monad m => MStream m a -> m [a]
joinS (MStream stream) = do
    (a, as) <- stream
    aslist <- joinS as
    return $ a : aslist

Но пока есть экземпляр Monad для MStream m, он неэффективен. (Или даже неверно?) Экземпляр Applicative действительно полезен!

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

import Data.Functor.Identity
type Stream a = MStream Identity a

Но состав Stream и f не MStream f! Скорее, Compose Stream f a изоморфно Stream (f a).

Я хотел бы знать, является ли MStream композиция из любых двух аппликаций.

Edit:

Я бы хотел предложить теоретическую точку зрения. Трансформатор - это "хороший" endofunctor t в категории C аппликативных функторов (т.е. Слабых моноидальных функторов с силой) вместе с естественным преобразованием liftA из тождества на C до t. Более общий вопрос заключается в том, какие существуют пригодные трансформаторы, которые не имеют формы "compose with g" (где g является аппликативным). Я утверждаю, что MStream является одним из них.

Ответы

Ответ 1

Отличный вопрос! Я считаю, что есть две разные части этого вопроса:

  • Составляя существующие аппликации или монады в более сложные.
  • Построение всех прикладных/монадов из некоторого заданного стартового набора.

Объявление 1.: Трансформаторы Monad необходимы для объединения монад. Монады не создаются напрямую. Кажется, что требуется дополнительный бит информации, предоставляемый монад-трансформаторами, который рассказывает, как каждая монада может быть скомбинирована с другими монадами (но может быть, эта информация уже присутствует как-то, см. Есть ли монада, у которой нет соответствующего монадного трансформатора?).

С другой стороны, аппликаторы составляют непосредственно, см. Data.Functor.Compose. Вот почему не нужны аппликативные трансформаторы для композиции. Они также закрыты под product (но не coproduct).

Например, бесконечные потоки data Stream a = Cons a (Stream a) и еще один аппликативный g, оба Stream (g a) и g (Stream a) являются аппликативными.

Но даже если Stream также является монадой (join принимает диагональ двумерного потока), ее состав с другой монадой m не будет, ни Stream (m a), ни m (Stream a) не будет всегда быть монадой.

Кроме того, как мы видим, они оба отличаются от вашего MStream g (который очень близок к ListT done right), поэтому:

Объявление 2.: Могут ли все аппликаторы быть построены из некоторого заданного набора примитивов? По-видимому, нет. Одной из проблем является создание суммарных типов данных: если f и g являются аппликативными, Either (f a) (g a) не будет, так как мы не знаем, как составить Right h <*> Left x.

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

newtype Fix1 f a = Fix1 { unFix1 :: f (Fix1 f) a }

instance (Functor (f (Fix1 f))) => Functor (Fix1 f) where
    fmap f (Fix1 a) = Fix1 (fmap f a)

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

(что требует не очень-приятного UndecidableInstances), а затем

data MStream' f g a = MStream (f (a, g a))

type MStream f = Fix1 (MStream' f)