Understanding the state argument in the State Monad

Question

I'm trying so hard to wrap my head around the State Monad, and I do not understand the following:

Given the implementation of return and (>>=), when you say State $ \s ->...., where does s come from? I mean, when you start performing >>= ... >>=, doesn't it mean that somewhere in your beginning of the chain you somehow have to provide for that initial parameter?

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

 instance Monad (State s) where
        return a=State $ \s->(a,s)
        (>>=) m g=State $ \s -> let (a,s')= runState m s in
                                   runState (g a) s'

In (>>=) you say State $ \s -> runState m s, and I do not get when is that initial (\s -> ...) argument (with a REAL argument) called?

Can someone explain, please?

Later Edit:

Can someone show me how would the initial state be set, let's say if it needs to get a value using getLine?

main::IO()
main=do
  argument<-getLine
  --how do i set initial state with argument?
  m >> f1 >> f2 >> f3

Answer 1

when you say State $ \s ->...., where does s come from ?

It will come from the invocation, when runState will supply the initial state value to the state-monadic value, to run the combined computation it describes:

st = do { x <- get ; return (x+1) }

x = runState st 0    -- x is (1,0)

---

I also sense another possible misunderstanding on your part: you write: "when is that initial (\s -> ...) argument called?" There's no "initial" lambda: the lambdas are all nested inside!

do { a <- as; b <- bs; c <- foo b; return c }

translates as

as >>= (\a -> bs >>= (\b -> foo b >>= (\c -> return c)))

so it's not "initial", that's one combined all-enclosing lambda that is called with the initial state!

And then it will call

let (a,s1) = runState as s0

etc. with that "initial" as in the do block.

Answer 2

the do block does not perform any stateful computation - it only assembles some smaller stateful computations into one bigger stateful computation. At the do level, the actual state does not exist.

It would be simpler and maybe even more accurate if the monad was called "a stateful computation". Or "a function that takes state of type S and returns another state of the same type alongside its actual result". Then you could imagine >>= as "combines two functions of the aforementioned type into one, such that the state returned by the first one is be passed as a parameter to the second one".

Answer 3

State is just a wrapper around functions of type s -> (a, s). runState doesn't actually "run" anything; it just gives back the function wrapped by the State constructor. You can, however, compare runState to the ($) operator for functions.

($)             f  x = f x
runState (State f) s = f s

That makes (=<<) = flip (>>=) similar to (<<<) = (.); just rather than taking two functions and returning a third function, it takes a function (that returns a State) and a State and produces a second State.

However, we'll make a direct comparison of (>>=) to (>>>) = flip (.) so that the types align better. (Similarly, you could compare (.) to (=<<).)

-- f :: t -> a
-- g ::      a -> b
f >>> g =         \t -> let a       = ($)      f     t
                        in            ($)      g     a
-- m :: State s a
-- g ::         a -> State s b
m >>= g = State $ \s -> let (a, s') = runState m     s
                        in            runState (g a) s'