Confusion over the State Monad code on "Learn you a Haskell"

Question

I am trying to get a grasp on Haskell using the online book Learn you a Haskell for great Good.

I have, to my knowledge, been able to understand Monads so far until I hit the chapter introducing the State Monad.

However, the code presented and claimed to be the Monad implementation of the State type (I have not been able to locate it in Hoogle) seems too much for me to handle.

• To begin with, I do not understand the logic behind it i.e why it should work and how the author considered this technique.( maybe relevant articles or white-papers can be suggested?)

• At line 4, it is suggested that function f takes 1 parameter.
  However a few lines down we are presented with pop, which takes no parameters!

• To extend on point 1, what is the author trying to accomplish using a function to represent the State.

Any help in understanding what is going on is greatly appreciated.

Edit

To whom it may concern,

The answers below cover my question thoroughly.
One thing I would like to add though:

After reading an article suggested below, I found the answer to my second point above: All that time I assumed that the pop function would be used like :
stuff >>= pop since in the bind type the second parameter is the function, whereas the correct usage is this pop >>= stuff , which I realized after reading again how do-notation translates to plain bind-lambdas.

Answer 1

The State monad represents stateful computations i.e. computations that use values from, and perhaps modify, some external state. When you sequence stateful computations together, the later computations might give different results depending on how the previous computations modified the state.

Since functions in Haskell must be pure (i.e. have no side effects) we simulate the effect of external state by demanding that every function takes an additional parameter representing the current state of the world, and returns an additional value, representing the modified state. In effect, the external state is threaded through a sequence of computations, as in this abomination of a diagram that I just drew in MSPaint:

Notice how each box (representing a computation) has one input and two outputs.

If you look at the Monad instance for State you see that the definition of (>>=) tells you how to do this threading. It says that to bind a stateful computation c0 to a function f that takes results of a stateful computation and returns another stateful computation, we do the following:

1. Run c0 using the initial state s0 to get a result and a new state: (val, s1)
2. Feed val to the function f to get a new stateful computation, c1
3. Run the new computation c1 with the modified state s1

---

How does this work with functions that already take n arguments? Because every function in Haskell is curried by default, we simply tack an extra argument (for the state) onto the end, and instead of the normal return value, the function now returns a pair whose second element is the newly modified state. So instead of

f :: a -> b 

we now have

f :: a -> s -> (b, s) 

You might choose to think of as

f :: a -> ( s -> (b, s) ) 

which is the same thing in Haskell (since function composition is right associative) which reads "f is a function which takes an argument of type a and returns a stateful computation". And that's really all there is to the State monad.