On Wed, May 21, 2008 at 8:42 AM, Dmitri O.Kondratiev <dokondr@gmail.com> wrote:
So let's start with fundamental and most intriguing  (to me) things:


getAny :: (Random a) => State StdGen a
getAny = do g <- get -- magically get the current StdGen

First line above declares a data type:

State StdGen a

which is constructed with the function:

State {runState :: (StdGen -> (a, StdGen))}

Q1: Where in the example (http://www.haskell.org/all_about_monads/examples/example15.hs) data of this type *actually gets constructed* ?

In getAny and getOne. Their signature has type `State StdGen a`. The use of the do notation to chain the actions and the use of get and put from the State Monad make this function a `State StdGen a`.


Looking at example15.hs code we see the following sequence:

1) makeRandomValue g -- where g is a StdGen instance, ok

2) makeRandomValue g ~> expands into ~>

~>  (runState (do { ...; b <- getAny;...})) g


This last expression puzzles me. I can understand, for example, this:

State StdGen a :: aState
StdGen:: g1

(v, g2) = (runStae aState) g1 -- this returns a state function which is then passed a generator g1, and as result returns pair (value, new generaor)

But '(runState (do ...)) g' implies that expression (do ...)  must be somehow of type 'State StdGen a' ?
Yet, when we call 'makeRandomValue g' we just pass to this function g::StgGen

So, my next question:
Q2: How (do {...;b <- getAny;...}) becomes an *instance* of type 'State StdGen a' ?

In 2) I suppose you're talking of `makeRandomValueST` as `makeRandomValue` is the function that runs without the State Monad.

makeRandomValueST does not build a `State StdGen a` it uses `runState` to run the (do block) which has type `State StdGen a`.

Using `runState` will run an action which has `State s a` type on an initial state `s` and return a `(a, s)` tuple.

`makeRandomValueST` does just the same using its parameter `g :: StdGen` as initial state and returning a tuple of type `(MyType, StdGen)`. Now what makes the do-block used in `runState` an instance of type `State StdGen a` is type inference. `runState` expects a `State s a` as first argument and `s` as second argument. The function signature, the use of `>>=` and `return` (desugared do-block) to combine actions and the use of actions already having that type like `getAny` and `getOne` will make your do block a `State StdGen a`.

I'm not sure we can talk of building an instance of `State s a`. It's a "parameterized variant" of `State s a` which itself is an instance of the Monad class. We're just assigning types to the `s` and `a` type variables in `State s a`.

In short `runState` takes the value (s -> (a, s)) out of the State monad. In the case of the State Monad that value is a function and it is run on the initial state. Its usually what runXXXXX functions do. They have type `(Monad m) => m a -> a`.

Actions in the State Monad have type `State (s -> (a, s))`. The value stored in the State constructor is a function. Combining two actions using the `>>=` and `>>` functions (hidden or not in a do-block) just create a bigger `s -> (a, s)` function. The function is "hidden" in a `State` constructor just to ensure you don't run it when you don't want to. When you whant to run the "big function" you first have to take it out of the State constructor using the accessor `runState` and then run it on the initial state. The end result is of course a (a, s) tuple.

Clear as mud, isn't it? It tooks me lots of time to understand how the State Monad works. I read many tutorial and still understood nothing about it. Its only by looking at the source code, playing with it and trying to rewrite the State Monad that I finally got an understanding of it. So I'm not sure you'll get it before you go through the same kind of path.

The key to understand this Monad, at least based on my experience, is to keep in mind that `>>=` just assembles small state passing functions into bigger ones, but does not run the built function until you explicitly use the `runState` function on it.

Olivier.