Is it possible to implement `(Applicative m) => Applicative (StateT s m)`?

Question

I'm currently working on Data.Fresh and Control.Monad.Trans.Fresh, which resp. define an interface for generating fresh variables, and a monad transformer which implements this interface.

I initially thought it would be possible to implement the Applicative instance for my FreshT v m with the only requirement that Applicative m exists. However, I got stuck and it seemed like I need to require Monad m. Not trusting my Haskell-fu, I then turned to the transformers package, and was surprised by what I found in Control.Monad.Trans.State.Lazy and .Strict:

instance (Functor m, Monad m) => Applicative (StateT s m) where
    pure = return
    (<*>) = ap

So here is my question: is it possible to create an instance with equivalent semantics with the following instance head?

instance (Applicative m) => Applicative (StateT s m) where

Answer 1

Consider that you have two functions:

 f :: s -> m (s, a -> b)
 g :: s -> m (s, a)

And you want to create a function h = StateT f <*> StateF g

 h :: s -> m (s, b)

From the above you have an s you can pass to f so you have:

 f' :: m (s, a -> b)
 g :: s -> m (s, a)

However to get s out of f' you need the Monad (whatever you'd do with applicative it would still be in form of m s so you would not be able to apply the value to g).

You can play with the definitions and use free monad but for the collapse of state you need join.

Answer 2

Weaker variant of an Applicative transformer

Although it isn't possible to define an applicative transformer for StateT, It's possible to define a weaker variant that works. Instead of having s -> m (a, s), where the state decides the next effect (therefore m must be a monad), we can use m (s -> (a, s)), or equivalently m (State s a).

import Control.Applicative
import Control.Monad
import Control.Monad.State
import Control.Monad.Trans

newtype StateTA s m a = StateTA (m (State s a))

This is strictly weaker than StateT. Every StateTA can be made into StateT (but not vice versa):

toStateTA :: Applicative m => StateTA s m a -> StateT s m a
toStateTA (StateTA k) = StateT $ \s -> flip runState s <$> k

Defining Functor and Applicative is just the matter of lifting operations of State into the underlying m:

instance (Functor m) => Functor (StateTA s m) where
    fmap f (StateTA k) = StateTA $ liftM f <$> k
instance (Applicative m) => Applicative (StateTA s m) where
    pure = StateTA . pure . return
    (StateTA f) <*> (StateTA k) = StateTA $ ap <$> f <*> k    

And we can define an applicative variant of lift:

lift :: (Applicative m) => m a -> StateTA s m a
lift = StateTA . fmap return

---

Update: Actually the above isn't necessary, as the composition of two applicative functors is always an applicative functor (unlike monads). Our StateTA is isomorphic to Compose m (State s), which is automatically Applicative:

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

Therefore we could write just

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
import Control.Applicative
import Control.Monad.State
import Data.Functor.Compose

newtype StateTA s m a = StateTA (Compose m (State s) a)
    deriving (Functor, Applicative)

Answer 3

Although, as noted in the previous answer, this instance cannot be defined in general, it is worth noting that, when f is Applicative and s is a Monoid, StateT s f is also Applicative, since it can be regarded as a composition of applicative functors:

StateT s f = Reader s `Compose` f `Compose` Writer s