Implement State Monad transformer in Haskell from scratch
Your implementation is correct. The additional comments are also welcome. I would write &lt;*&gt; without runState, but that's personal preference.

Keep in mind that you've re-implementend Control.Monad.Trans.State.Strict.StateT. For the lazy variant Control.Monad.Trans.State.Lazy.StateT, you would have to use lazy pattern matches in several places, so I assume you wanted to implement the strict variant.

To answer your question: no, we cannot implement Applicative (StateT s m) in terms of Applicative m. A Q&amp;A on StackOverflow contains some hints, but let's reiterate them:

Suppose you have two values f, x and want y with the following types:

f :: StateT m s (a -&gt; b)
x :: StateT m s a
y :: StateT m s b


We first remove the newtype:

f :: s -&gt; m (s, (a -&gt; b))
x :: s -&gt; m (s, a)
y :: s -&gt; m (s, b)


If our initial state is p, we have

f p :: m (s, (a -&gt; b))
x   :: s -&gt; m (s, a)


We want to use the s from f p in x to feed into x and the function to use the a. Now, let's suppose that m is an Applicative. This gives us only pure, fmap and &lt;*&gt; to work with. Let's try to write an expression that only uses those three functionspure, fmap and &lt;*&gt;:

z s = fmap (\(s', f') -&gt; fmap (\(s'', x') -&gt; (s'', f' x')) x s') (f s)


Let's check whether that implementation is sane. It's easier to deciper if we swap fmap's arguments:

x ~~&gt; f = fmap f x
z s = f s                                   --  1
      ~~&gt; (\(s', f') -&gt;                     --  2
           x s'                             --  3
           ~~&gt; (\(s'', x') -&gt; (s'', f' x')  --  4
         )



We run f s to get our new state and our function. 
Both are in m, so we use fmap to get in there.
We run x s' to get our new state again and our value. 
Both are in m, so we use fmap yet again. However, we're using fmap inside fmap, which already tells us that we're not going to end up with a simple m ....


In (4), we end up with the correct new state s'' and the correct value f' x'. However, our type is s -&gt; m (m (s, b)). Applicative does not provide any methods to reduce the number of m's, so we're stuck. We need to use join :: Monad m =&gt; m (m x) -&gt; m x.

If we go back, we see that the problem arises due to x's type s -&gt; m (s, a). If it was m (s -&gt; (s, a)), we could simply use Applicative. Petr provides a detailed answer on SO.