Understanding Monad Transformer Type Signatures

Question

I'm currently tackling monad transformers and trying to really understand the type signatures, and I'm having some confusion. Let's use the following stack for discussion:

newtype Stack s m a = Stack { runStack :: ReaderT s (StateT s IO) a }

I'm trying to go through layer by layer and write the unwrapped type signatures but getting stuck:

newtype Stack s m a = Stack { 
    runStack :: ReaderT s         (StateT s IO)       a }
--              ReaderT s                  m          a
--                      s ->               m          a
--                      s ->         (StateT s IO)    a
--                            StateT  s     m         a
--                      s ->         (s -> IO (a, s)) a  

That just doesn't look like a valid return type signature on the last line, we have essentially a function that takes an s and returns a function shoved up against an a?

I get that the inner function evaluates to a Monad eventually, and that's why it's the m in ReaderT r m a, but it's bending my brain.

Could anyone offer any insight, have I correceclty analyzed the types and I just have to accept that s -> (s -> IO (a, s)) a is indeed valid?

Thank you

Answer 1

The stack you wrote is a little odd because it's parametrized by m on the left but specialized to IO on the right, so let's look at the fully m-parametrized variant:

newtype Stack s m a = Stack { runStack :: ReaderT s (StateT s m) a }

Now runStack here is just a field name, so we can drop it and write the equivalent newtype definition:

newtype Stack s m a = Stack (ReaderT s (StateT s m) a)

We also have the following library newtype definitions, skipping the field names. I've also used fresh variables so we don't do something stupid like confuse two as in different scope while expanding:

newtype ReaderT r1 m1 a1 = ReaderT (r1 -> m1 a1)
newtype StateT s2 m2 a2 = StateT (s2 -> m2 (a2, s2))

Of course, if we're only interested in the type up to isomorphism, then the newtype wrappers don't matter, so just rewrite these as type aliases:

type Stack s m a = ReaderT s (StateT s m) a
type ReaderT r1 m1 a1 = r1 -> m1 a1
type StateT s2 m2 a2 = s2 -> m2 (a2, s2)

Now, it's easy to expand the Stack type:

Stack s m a
= ReaderT s (StateT s m) a
-- expand ReaderT with r1=s, m1=StateT s m, a1=a
= s -> (StateT s m) a
= s -> StateT s m a
-- expand StateT with s2=s m2=m a2=a
= s -> (s -> m (a, s))
= s -> s -> m (a, s)

As @duplode noted, there's no extra a here.

Intuitively this Stack reads from an s (first argument) takes an initial state of type s (second argument), and returns a monadic action in m (e.g., IO) that can return a value of type a and an updated state of type s.