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

Short answer:

1. State is meant to exploit monads' features in order to simulate an imperative-like system state with local variables. The basic idea is to hide within the monad the activity of taking in the current state and returning the new state together with an intermediate result at each step (and here we have s -> (a,s).
2. Do not mistake arbitrary functions with those wrapped within the State. The former may have whatever type you want (provided that they eventually produce some State a if you want to use them in the state monad). The latter holds functions of type s -> (a,s): this is the state-passing layer managed by the monad.
3. As I said, the function wrapped within State is actually produced by means of (>>=) and return as they're defined for the Monad (State s) instance. Its role is to pass down the state through the calls of your code.

Point 3 also is the reason why the state parameter disappears from the functions actually used in the state monad.

Long answer:

The State Monad has been studied in different papers, and exists also in the Haskell framework (I don't remember the good references right now, I'll add them asap).

This is the idea that it follows: consider a type data MyState = ... whose values holds the current state of the system.

If you want to pass it down through a bunch of functions, you should write every function in such a way that it takes at least the current state as a parameter and returns you a pair with its result (depending on the state and the other input parameters) and the new (possibly modified) state. Well, this is exactly what the type of the state monad tells you: s -> (a, s). In our example, s is MyState and is meant to pass down the state of the system.

The function wrapped in the State does not take parameters except from the current state, which is needed to produce as a result the new state and an intermediate result. The functions with more parameters that you saw in the examples are not a problem, because when you use them in the do-notation within the monad, you'll apply them to all the "extra" needed parameters, meaning that each of them will result in a partially applied function whose unique remaining parameter is the state; the monad instance for State will do the rest.

If you look at the type of the functions (actually, within monads they are usually called actions) that may be used in the monad, you'll see that they result type is boxed within the monad: this is the point that tells you that once you give them all the parameters, they will actually do not return you the result, but (in this case) a function s -> (a,s) that will fit within the monad's composition laws.

The computation will be executed by passing to the whole block/composition the first/initial state of the system.

Finally, functions that do not take parameters will have a type like State a where a is their return type: if you have a look at the value constructor for State, you'll see again that this is actually a function s -> (a,s).

Answer 2

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.

Answer 3

I'm total newbie to Haskell and I couldn't understand well the State Monad code in that book, too. But let me add my answer here to help someone in the future.

Answers:

• What are they trying to accomplish with State Monad ?

  Composing functions which handle stateful computation.
  e.g. push 3 >>= \_ -> push 5 >>= \_ -> pop
  
  

• Why pop takes no parameters, while it is suggested function f takes 1 parameter ?

  pop takes no arguments because it is wrapped by State.
  unwapped function which type is s -> (a, s) takes one argument. the same goes for push.
  you can unwrapp with runState.

  runState pop :: Stack -> (Int, Stack)
  runState (push 3) :: Stack -> ((), Stack)
  

  if you mean the right-hand side of the >>= by the "function f", the f will be like \a -> pop or \a -> push 3, not just pop.

Long Explanation:

These 3 things helped me to understand State Monad and the Stack example a little more.

• Consider the types of the arguments for bind operator(>>=)

  The definition of the bind operator in Monad typeclass is this

  (>>=) :: (Monad m) => m a -> (a -> m b) -> m b
  

  In the Stack example, m is State Stack.
  If we mentaly replace m with State Stack, the definition can be like this.

  (>>=) :: State Stack a -> (a -> State Stack b) -> State Stack b 

  Therefore, the type of left side argument for the bind operator will be State Stack a.
  And that of right side will be a -> State Stack b.
  
  

• Translate do notation to bind operator

  Here is the example code using do notation in the book.

  stackManip :: State Stack Int  
  stackManip = do  
       push 3  
       pop  
       pop  
  

  it can be translated to the following code with bind operator.

  stackManip :: State Stack Int  
  stackManip = push 3 >>= \_ -> pop >>= \_ -> pop
  

  Now we can see what will be the right-hand side for the bind operator.
  Their types are a -> State Stack b.

  (\_ -> pop) :: a -> State Stack Int
  (\_ -> push 3) :: a -> State Stack ()
  

  
  

• Recognize the difference between (State s) and (State h) in the instance declaration

  Here is the instance declaration for State in the book.

  instance Monad (State s) where  
      return x = State $ \s -> (x,s)  
      (State h) >>= f = State $ \s -> let (a, newState) = h s  
                                          (State g) = f a  
                                      in  g newState 
  

  Considering the types with the Stack example, the type of (State s) will be

  (State s) :: State Stack
  s :: Stack
  

  And the type of (State h) will be

  (State h) :: State Stack a
  h :: Stack -> (a, Stack)
  

  (State h) is the left-hand side argument of the bind operator and its type is State Stack a as described above.
  

  Then why h becomes Stack -> (a, Stack) ?
  It is the result of pattern matching against the State value constructor which is defined in the newtype wrapper. The same goes for the (State g).

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

  In general, type of h is s ->(a, s), representation of the stateful computation. Any of followings could be the h in the Stack example.

  runState pop :: Stack -> (Int, Stack)
  runState (push 3) :: Stack -> ((), Stack)
  runState stackManip :: Stack -> (Int, Stack)
  

  that's it.

Answer 4

The State monad is essentially

type State s a = s -> (a,s)

a function from one state (s) to a pair of the desired result (a) and a new state. The implementation makes the threading of the state implicit and handles the state-passing and updating for you, so there's no risk of accidentally passing the wrong state to the next function.

Thus a function that takes k > 0 arguments, one of which is a state and returns a pair of something and a new state, in the State s monad becomes a function taking k-1 arguments and returning a monadic action (which basically is a function taking one argument, the state, here).

In the non-State setting, pop takes one argument, the stack, which is the state. So in the monadic setting, pop becomes a State Stack Int action taking no explicit argument.

Using the State monad instead of explicit state-passing makes for cleaner code with fewer opportunities for error, that's what the State monad accomplishes. Everything could be done without it, it would just be more cumbersome and error-prone.