Re: [Haskell-cafe] Newbie: State monad example questions

State is a data type. As any other data type it can be instantiated. State instance is a structure of one record that contains (\s ->(a,s)) lambda function. This function can be parametrized by types of its arguments 's' and 'a'. I don't see magic here :) Ok, then from declaration: getAny :: (Random a) => State StdGen a getAny = do g <- get we can say that looking at type 'State StdGen a' compiler concludes that later on in the 'do' block statements like: g <- get will resolve into bind function (>>=) *as bind is defined for State monad*. Fine, I assume compiler is capable of such reasoning. Then g <- get may be written as: get >>= \g -> ... To understand how State monad work, I wrote MyState data type that emulates State and (>=>) 'bind' function that emulates 'real' bind (>>=) implementation for State monad: (>=>) :: MyState StdGen Int -> (Int -> MyState StdGen Int) -> MyState StdGen Int (MyState ms) >=> fn = MyState(\seed -> let(v1, newSeed) = ms seed ms2 = fn v1 in (runState ms2) newSeed) Inserting 'get' into >>= (or >=> in my code) will in fact result in thinking about State instance that 'get' returns as denoted by 'ms' in this code of mine.

From 'get' definition follows that function hiding behind 'ms' State instance is:

\s -> (s,s) So when later we will feed generator 'g1' into this function will get: (g1,g1) And we also will get: v1 = g1 newSeed = g1 ms2 = fn g1 and finally 'g' in expression 'g <- get' will be equal to 'g1' that will be later fed in through the function call: 'makeRandomValueST g1' But how will 'g1' actually get delivered from 'makeRandomValueST g1' to invocation of 'getAny' I don't yet understand! On Wed, May 21, 2008 at 5:55 PM, Olivier Boudry wrote:

On Wed, May 21, 2008 at 8:42 AM, Dmitri O.Kondratiev 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.

-- Dmitri O. Kondratiev dokondr@gmail.com http://www.geocities.com/dkondr