[Haskell-cafe] Newbie: State monad example questions

[Olivier Boudry]

On Wed, May 21, 2008 at 8:42 AM, Dmitri O.Kondratiev <dokondr at 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080521/c17efded/attachment.htm