I've got this type alias:

type Board a = ReaderT String (StateT String IO) a

I know that StateT has the kind * -> (* -> *) -> * -> * so it should get three parameters. But in the above example, StateT only receives String and the IO-Monad. Now I'm wondering where the missing parameter is passed to StateT.

Same goes for IO which should get one parameter but doesn't get any.

CodePudding user response：

If you look at the definition of ReaderT, you will see that its second parameter is itself applied to its last parameter:

newtype ReaderT r m a = ReaderT { runReaderT :: r -> m a }
                                                     ^^^
                                                  right here

Which means that its second parameter m must have kind m :: * -> *. And this is exactly what you get if you apply only two, not three, parameters to StateT:

StateT :: * -> (* -> *) -> * -> *
StateT x y :: * -> *
(where x :: * and y :: * -> *)

When substituting the definition of ReaderT in your type Board, you'll get:

(1) type Board a = ReaderT String (StateT String IO) a

-- Substituting ReaderT definition (pseudocode)
(2) type Board a = { runReaderT :: String -> StateT String IO a }
                                             ^^^^^^^^^^^^^^^^^^
                                Look, StateT has all its three parameters!

CodePudding user response：

You correctly observe that

StateT has the kind * -> (* -> *) -> * -> *

and the same is true of ReaderT.

So it takes 3 "parameters" as you call them. The first is String, of kind *, and the third is a, again of kind *. While the second must be of kind * -> *.

And that is given in your example by StateT String IO. So although there is in one sense a "missing parameter" of StateT, this needs to be "missing" in order to get something of kind * -> * - if you tried something like type Board a = ReaderT String (StateT String IO Int) a, this would fail with a "kind error", precisely because ReaderT's second type argument needs to be of kind * -> *, not of kind * which StateT String IO Int would have.

The same applies to why IO is used on its own rather than something of the form IO a. StateT String (IO Int) wouldn't work because StateT needs to apply to something of kind * -> * as its second type argument - IO has this kind but IO Int (or anything of the form IO a) does not.

To take a step back, monad transformers like ReaderT and StateT transform another monad, and a monad must always be of kind * -> *. IO is a monad, and so is StateT String IO. But IO Int and StateT String IO Int are not monads - and not for failing the monad laws or anything like that, but for a much more fundamental meaning, they are the wrong kind. (They are "concrete types" - types which have values - rather than "type constructors" that take another type as an argument.)