[Haskell-cafe] Type and State Confusion

[Albert Y. C. Lai]

Hans van Thiel wrote:
> sequence :: Monad m => [m a] -> m [a]
>
> You write:
> The >>= used by sequence is the same >>= in the MyState monad,
> since you instantiate m to MyState String. Therefore, sequence
> performs all the state transformations correctly, since >>= is
> correct.
>
> So the m becomes MyState String, and therefore the list elements
> have type (MyState String Int), or the other way around. I
> understand, from your explanation, how this works from there on,
> but I'm still confused about what the Monad is. Is it MyState
> which takes two types, or (MyState String) which takes one type?
> Or neither? Does it involve some 'sort of currying' of type
> parameters?
>   

The monad is (MyState String) or generally (MyState a) which takes one 
type. So this is some sort of currying of type parameters.

With this in mind, the rest is straightforward:

> data MyState a b = MyStateC ([a] -> ([a], b))
>
> This defines an algebraic data type (...why is it called algebraic?)
> with two type variables and a unary constructor.
>          
>  instance Monad (MyState a) where
>     return x = MyStateC (\tb -> (tb, x))
>     (MyStateC st) >>= f =  
>         MyStateC (\tb -> let                       
>                            (newtb, y) = st tb
>                            (MyStateC trans) = f y 
>                          in trans newtb )
>
> Now, if the instantiated a has type String, Int or whatever, I
> would understand, but the type of the Monad seems to be built up
> from two types.


The general type of return is

  return :: (Monad m) => b -> m b

Tailor-made to our case, m = MyState a,

  return :: b -> MyState a b

Similarly, the general type of >>= is

  (>>=) :: (Monad m) => m b -> (b -> m c) -> m c

Tailor-made to our case, m = MyState a,

  (>>=) :: MyState a b -> (b -> MyState a c) -> MyState a c

If we now consider

  foo >>= toMyState

then a=String, b=String, c=Int. Note again that the part (MyState a), or 
now (MyState String), is the monad.