[Haskell] Monad and Monad transformer???

[Albert Y. C. Lai]

Duong Thai Ha wrote:
> I am trying to get the idea of using Monad and have to understand the 
> following code.
> 
> Can you please tell me is how different Monad and Monad transformer is?
> And what is mean by
> 
>  > newtype State s a = State { runState :: s -> (a, s) }

First I want to say the haskell-cafe mailing list is an even better 
place for this.

The Haskell Wikibook has a large section on monads and monad 
transformers, including the State monad. I will just explain the newtype 
business, which is simple.

The essence of the State monad is just functions of type s->(a,s). Due 
to a restriction on Haskell syntax (it is a good restriction, sometimes 
inconvenient but there are also benefits) we can't just write "s->(a,s)" 
into an instance declaration. The next best thing is to define our own 
data type with content "s->(a,s)", and then Haskell will allow our data 
type to be an instance. There are two ways:

     data MyType s a = MyConstructor (s->(a,s))
     newtype MyType s a = MyConstructor (s->(a,s))

There are subtle differences between the two. For now I'll just cite the 
most shallow one: the "data" version may add runtime overhead (depending 
on compiler), the "newtype" version is guaranteed to add no runtime 
overhead.

Next we rename the type from MyType to State:

     newtype State s a = MyConstructor (s->(a,s))

Next we recognize that the name of the constructor can be the same as 
the name of the type (they live in different namespaces, no clash), so 
we also rename MyConstructor:

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

Lastly, the record syntax applies to "newtype" definitions too. We can 
think of this type as a single-field record, the sole field being of 
type s->(a,s). We can give it a field name, and we choose "runState":

     newtype State s a = State { runState :: s->(a,s) }

The net effect is that "s->(a,s)" and "State s a" are of the same 
essence, just formally different types, and we need create "State s a" 
just to satisfy some requirement. But they are mutually convertible. If 
you have f :: s->(a,s), you can convert it to the new type by writing 
"State f". Conversely, if you have g :: State s a, you can convert it 
back to a function by writing "runState g" or using pattern matching. 
(These conversions are just syntactic and cost nothing in execution.)