[Haskell-cafe] Newbie: State monad example questions

[Dmitri O.Kondratiev]

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 <olivier.boudry at gmail.com>
wrote:

> 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.
>



-- 
Dmitri O. Kondratiev
dokondr at gmail.com
http://www.geocities.com/dkondr
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20080521/e0c19de2/attachment.htm