Are applicative transformers really superfluous?

Question

There is a lot of talk about Applicative not needing its own transformer class, like this:

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

But I can define applicative transformers that don't seem to be compositions of applicatives! For example sideeffectful streams:

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

Lifting just performs the side effect at every step:

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

And if f is an applicative, then MStream f is as well:

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

I know that for any practical purposes, f should be a monad:

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

But while there is a Monad instance for MStream m, it's inefficient. (Or even incorrect?) The Applicative instance is actually useful!

Now note that usual streams arise as special cases for the identity functor:

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

But the composition of Stream and f is not MStream f! Rather, Compose Stream f a is isomorphic to Stream (f a).

I'd like to know whether MStream is a composition of any two applicatives.

Edit:

I'd like to offer a category theoretic viewpoint. A transformer is a "nice" endofunctor t on the category C of applicative functors (i.e. lax monoidal functors with strength), together with a natural transformation liftA from the identity on C to t. The more general question is now what useful transformers exist that are not of the form "compose with g" (where g is an applicative). My claim is that MStream is one of them.

Take any monad transformer that does not work by simple composition (StateT, ListT, ContT, etc.). This will give you an example of a nontrivial applicative transformer as well, since each monad is automatically an applicative functor. — winitzki, Jan 09 '23 at 13:08
My comment was too quick. In a lot of cases, what I said doesn't work. Here is an example: https://stackoverflow.com/questions/18673525/is-it-possible-to-implement-applicative-m-applicative-statet-s-m — winitzki, Jan 09 '23 at 19:09

score 10 · Accepted Answer · edited May 23 '17 at 11:58

Great question! I believe there are two different parts of this question:

Composing existing applicatives or monads into more complex ones.
Constructing all applicatives/monads from some given starting set.

Ad 1.: Monad transformers are essential for combining monads. Monads don't compose directly. It seems that there needs to be an extra bit of information provided by monad transformers that tells how each monad can be composed with other monads (but it could be this information is already somehow present, see Is there a monad that doesn't have a corresponding monad transformer?).

On the other hand, applicatives compose directly, see Data.Functor.Compose. This is why don't need applicative transformers for composition. They're also closed under product (but not coproduct).

For example, having infinite streams data Stream a = Cons a (Stream a) and another applicative g, both Stream (g a) and g (Stream a) are applicatives.

But even though Stream is also a monad (join takes the diagonal of a 2-dimensional stream), its composition with another monad m won't be, neither Stream (m a) nor m (Stream a) will always be a monad.

Furthermore as we can see, they're both different from your MStream g (which is very close to ListT done right), therefore:

Ad 2.: Can all applicatives be constructed from some given set of primitives? Apparently not. One problem is constructing sum data types: If f and g are applicatives, Either (f a) (g a) won't be, as we don't know how to compose Right h <*> Left x.

Another construction primitive is taking a fixed point, as in your MStream example. Here we might attempt to generalize the construction by defining something like

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)

(which requires not-so-nice UndecidableInstances) and then

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

type MStream f = Fix1 (MStream' f)

Are applicative transformers really superfluous?

1 Answers1

Linked