Type error while trying to implement the (>>=) function in order to create a custom monad transformer

Question

I'm trying to create a monad transformer for a future project, but unfortunately, my implementation of the Monad typeclasse's (>>=) function doesn't work.

First of all, here is the underlying monad's implementation :

newtype Runtime a = R { 
  unR :: State EInfo a
} deriving (Monad)

Here, the implementation of the Monad typeclasse is done automatically by GHC (using the GeneralizedNewtypeDeriving language pragma). The monad transformer is defined as so :

newtype RuntimeT m a = RuntimeT {
  runRuntimeT :: m (Runtime a)
} 

The problem comes from the way I instanciate the (>>=) function of the Monad typeclasse :

instance (Monad m) => Monad (RuntimeT m) where
    return a = RuntimeT $ (return . return) a
    x >>= f =  runRuntimeT x >>= id >>= f

The way I see it, the first >>= runs in the underlying m monad. Thus, runRuntimeT x >>= returns a value of type Runtime a (right ?). Then, the following code, id >>=, should return a value of type a. This value is the passed on to the function f of type f :: (Monad m) => a -> RuntimeT m b.

And here comes the type problem : the f function's type doesn't match the type required by the (>>=) function. Jow can I make this coherent ? I can see why this doesn't work, but I can't manage to turn it into something functionnal.

Edit : The error message :

Core.hs:34:4:
    Occurs check: cannot construct the infinite type: m = RuntimeT m
    When generalising the type(s) for `>>='
    In the instance declaration for `Monad (RuntimeT m)'
Failed, modules loaded: none.

Thank you for you help, and do not hesitate to correct any flaws in my message,
Charlie P.

Answer 1

To follow on from what Reid Barton said about StateT - here's how you would define RuntimeT using StateT. The Runtime monad can then be trivially defined using the identity monad.

newtype RuntimeT m a = R { 
  unR :: StateT EInfo m a
}

type Runtime = RuntimeT Identity

instance Monad m => Monad (RuntimeT m) where
    return = R . return

    (R m) >>= f = R (m >>= unR . f)

Answer 2

The usual StateT s m monad sends a to s -> m (a, s) but you are working with m (s -> (a, s)) instead. I don't think the latter forms a monad for general s. Are you sure you don't just want to use StateT?

---

Here's why I don't think a → m (s -> (a, s)) is a monad: To write >>= I need a function that takes arguments of types

m (s -> (a, s))
a -> m (s -> (b, s))

and returns a value of type

m (s -> (b, s))

The "effects" (i.e. fmap (const ())) of the result must be those of the first argument, since we have no way to get an a to pass to the second argument. Since m appears only on the outside of the result type, we then cannot use the second argument for anything at all—there will be no way to get rid of the m it introduces.