Understanding a monad instance

Question

I have this Haskell code portion:

newtype State st a = State (st -> (st, a))

instance Monad (State state) where
    return x = let f t = (t,x) in State f

    State f >>= g = State (\oldstate ->
                let {(newstate, val) = f oldstate;
                  State f'= g val}
                in f' newstate)

I'm new to monad but i think i got how return and bind works in the general case.

But in the example above i have lots of problems:

1. in Monad (State state) is State the Monad's name? How is it related with the newtype State ... ?
2. in return x = let f t = (t,x) in State f where does t comes from?

Answer 1

So by this point you've certainly heard of currying or partial application: if you have f :: a -> b -> c and x :: a, then f x :: b -> c. I.e., If f is a two-argument function and x has the type of f's first argument, then f x is a function that takes the second argument and "completes" the application.

Well, in Haskell the same thing applies to type constructors like State. Types and type constructors have a kind, which is analogous to how values have types. A non-parametric type like Integer has kind *; a one-parameter type like Maybe has kind * -> *; State has kind * -> * -> *.

And then, State state is a partial application of the State type constructor, and has kind * -> *. Monad is a class that applies to the kind * -> *. So, applied to our examples:

1. instance Monad (Integer) where ... is forbidden because Integer has kind *.
2. instance Monad (Maybe) where ... is allowed because Maybe has kind * -> *.
3. instance Monad (State) where ... is forbidden because State has kind * -> * -> *.
4. instance Monad (State st) where ... is allowed because State st has kind * -> *.

How do we know that Monad applies to types of kind * -> *? We can infer it from the class declaration:

class Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b
    -- ...

Look at how m is used in this class declaration: as part of m a and m b, i.e., as taking one argument. Because of this, Haskell infers that m is a type variable of kind * -> *.

Compare to this:

class Num a where
    (+) :: a -> a -> a
    (-) :: a -> a -> a
    -- ...

Here the type variable a is not applied to other type variables—thus it must be of kind *.

So strictly speaking, State is not a monad; it's a two-place type constructor that, when partially applied to just one type, gives you a monad. So State state is a monad, as is State Integer, State [a], etc. People do often speak loosely and talk of State and similar things as monads, though, but you should understand it's a parametrized monad—it's a monad that has an internal type parameter and thus many variants that differ in the type of that parameter.