views:

277

answers:

4

I have a function:

test :: String -> State String String
test x = 
    get >>= \test ->
    let test' = x ++ test in
    put test' >>
    get >>= \test2 -> put (test2 ++ x) >>
    return "test"

I can pretty much understand what goes on throughout this function, and I'm starting to get the hang of monads. What I don't understand is how, when I run this:

runState (test "testy") "testtest"

the 'get' function in 'test' somehow gets the initial state "testtest". Can someone break this down and explain it to me?

I appreciate any responses!

A: 

It's been a while since I programmed in Haskell but the following link might help you:

http://www.cs.nott.ac.uk/~gmh/monads

Just search for State monad in that page to find the notes on it that hopefully might help you understand things

RobV
+5  A: 

It might help you to take a deeper look at what the State type constructor really is, and how runState uses it. In GHCi:

Prelude Control.Monad.State> :i State
newtype State s a = State {runState :: s -> (a, s)}
Prelude Control.Monad.State> :t runState
runState :: State s a -> s -> (a, s)

State takes two arguments: the type of the state, and the returned type. It is implemented as a function taking the initial state and yielding a return value and the new state.

runState takes such a function, the initial input, and (most probably) just applies one to the other to retrieve the (result,state) pair.

Your test function is a big composition of State-type functions, each taking a state input and yielding a (result,state) output, plugged in one another in a way that makes sense to your program. All runState does is provide them with a state starting point.

In this context, get is simply a function that takes state as an input, and returns a (result,state) output such that the result is the input state, and the state is unchanged (the output state is the input state). In other words, get s = (s, s)

JB
Clickedy click click! Bingo. Thanks a lot, you're explanation made it click. I never realized that get actually 'took' an argument. Hehe. Thanks.
Rayne
+10  A: 

I was originally going to post this as a comment, but decided to expound a bit more.

Strictly speaking, get doesn't "take" an argument. I think a lot of what is going on is masked by what you aren't seeing--the instance definitions of the State monad.

get is actually a method of the MonadState class. The State monad is an instance of MonadState, providing the following definition of get:

get = State $ \s -> (s,s)

In other words, get just returns a very basic State monad (remembering that a monad can be thought of as a "wrapper" for a computation), where any input s into the computation will return a pair of s as the result.

The next thing we need to look at is >>=, which State defines thusly:

m >>= k  = State $ \s -> let
    (a, s') = runState m s
    in runState (k a) s'

So, >>= is going to yield a new computation, which won't be computed until it gets an initial state (this is true of all State computations when they're in their "wrapped" form). The result of this new computation is achieved by applying whatever is on the right side of the >>= to the result of running the computation that was on the left side. (That's a pretty confusing sentence that may require an additional reading or two.)

I've found it quite useful to "desugar" everything that's going on. Doing so takes a lot more typing, but should make the answer to your question (where get is getting from) very clear. Note that the following should be considered psuedocode...

test x =
    State $ \s -> let
     (a,s') = runState (State (\s -> (s,s))) s  --substituting above defn. of 'get'
     in runState (rightSide a) s'
     where 
          rightSide test = 
      let test' = x ++ test in
      State $ \s2 -> let
      (a2, s2') = runState (State $ \_ -> ((), test')) s2  -- defn. of 'put'
      in runState (rightSide2 a2) s2'
          rightSide2 _ =
      -- etc...

That should make it obvious that the end result of our function is a new State computation that will need an initial value (s) to make the rest of the stuff happen. You supplied s as "testtest" with your runState call. If you substitute "testtest" for s in the above pseudocode, you'll see that the first thing that happens is we run get with "testtest" as the 'initial state'. This yields ("testtest", "testtest") and so on.

So that's where get gets your initial state "testtest". Hope this helps!

J Cooper
I couldn't think of a better word when I said it "took" an argument. Thanks for this very detailed explanation.
Rayne
+2  A: 

Going through chapter 8 ("Functional Parsers") of Graham Hutton's Programming in Haskell several times until I'd properly understood it, followed by a go at the tutorial All About Monads, made this click for me.

The issue with monads is that they are very useful for several things that those of us coming from the usual programming background find quite dissimilar. It takes some time to appreciate that control flow and handling state are not only similar enough that they can be handled by the same mechanism, but are when you step back far enough, the same thing.

An epiphany came when I was considering control structures in C (for and while, etc.), and I realized that by far the most common control structure was simply putting one statement before the other one. It took a year of studying Haskell before I realized that that even was a control structure.

Curt Sampson
Thanks for the answer. Luckily, most of my programming experience actually lies in Functional programming, so it's not as hard on me! :D
Rayne