Take the 2-minute tour ×

Just learning about State monad from this excellent tutorial. However, when I tried to explain it to a non-programmer they had a question that stumped me.

If the purpose of the State is to simulate mutable memory, why is the function that state monad stores is of the type:

s -> (a, s)

and not simply:

s -> s

In other words, what is the need for the "intermediate" value? For example, couldn't we, in the cases where we need it, simulate it by simply defining a state as a tuple of (state, value)?

I'm sure I confused something, any help is appreciated.

share|improve this question
I like Roman's answer, but I would say that the purpose of State is not to simulate mutable memory, but to simulate computations that require mutable memory. The point of running State is (notionally) to obtain the result of the computation, with the state itself being simply an artifact. Of course in real problems we often do care about the output state, which is why it's available too. –  John L Jul 21 '12 at 13:06

7 Answers 7

up vote 16 down vote accepted

To draw a parallel with an imperative language like C, s -> s corresponds to a function with the return type void, which is invoked purely for side effects (such as mutating the memory). It is isomorphic to State s ().

And indeed, it is possible to write C functions which communicate only through global variables. But, as in C, it is often convenient to return values from functions. That's what a is for.

Of course it's possible that for your particular problem s -> s is a better choice. Although it's not a Monad, it is a Monoid (when wrapped in Endo). So you can construct such functions using <> and mempty, which correspond to >>= and return of Monad.

share|improve this answer
Also s -> s doesn't scale very well. Using your C parallel: you can always add extra information into global state by simply defining new global variable; in Haskell this would require changing the underlying type s. I'll illustrate with an example: let's have a state Stack -> Stack and we'd like to collect how the top of stack looks at some specific moments. In C, you could just add new global variable, with Stack -> Stack you can't - you have to use something more specific such as (Stack,[a]) -> (Stack,[a]). With "normal" state it is as simple as using few <- and return [a,b,c] –  Vitus Jul 20 '12 at 17:29
Sorry, but I gave this answer a -1. I worry that, although true and indeed powerful, the Monoid view of functions is likely to be more confusing to a new Haskell developer learning about State than helpful. Initially it's simplest to treat function composition directly as function composition (or Control.Category.(.) if you want to be somewhat more general) than as monoid append. –  mergeconflict Jul 23 '12 at 17:23

To expand a bit on Nick's answer:

s is the state. If all your functions were s -> s (state to state), your functions would not be able to return any values. You could define your state as (the actual state, value returned), but that conflates the state with the value the state-ful functions are computing. And it's also the common case that you'll want functions to actually compute and return values...

share|improve this answer

s' -> s' is equivalent to (a, s) -> (a, s). Here it is obvious that your State will need an initial a to start things off in addition to s.

On the other hand s -> (a, s) only needs the seed s to begin things and does not require an a value at all.

Thus the type of s -> (a, s) tells you that State is less complex than if it were (a, s) -> (a, s). Types in Haskell convey LOTS of information.

share|improve this answer


s -> (a, s)

and not simply:

s -> s

The purpose of the State monad is not to simulate mutable memory, but rather to model computations that both produce a value and have a side effect. Simply, given some initial state of type s, your computation will produce some value of type a, as well as an updated state.

Maybe your computation does not produce a value... Then, easy: the value type a is simply (). Perhaps on the other hand your computation does not have a side effect. Again, easy: you might think of your state transition function (the s -> s argument to modify) as just being id. But often you're dealing with both at the same time.

You can actually use get and put as relatively simple examples:

get :: State s s      -- s -> (s, s)
put :: s -> State ()  -- s -> (s -> ((), s))
  • get is a computation which, given the current state (the first s), will return it both as a value -- that is, the result of the computation -- and as the "new" (unmodified) state.

  • put is a computation which, given a new state (the first s) and a current state (the second s), will simply ignore the current state. It will produce () as the computed value (because, of course, it hasn't computed any value!) and hang onto the new state provided.

share|improve this answer

Presumably you want to use your stateful computations inside of do notation?

You should ask yourself what the Monad instance would look like for a stateful computation defined by

newtype State s = { runState :: s -> s }
share|improve this answer
It is perhaps more enlightening to think about how you would write the Functor instance. fmap :: (a -> b) -> State a -> State b. While you can easily transform the "output" end of State, you do not have enough information to also transform the input end. –  Dan Burton Jul 20 '12 at 20:59
I originally ended the answer with "In fact, what would the Functor instance look like?" but decided not to include it :) –  Chris Taylor Jul 20 '12 at 22:52

a is the value returned, and the s is the final state.


share|improve this answer

The problem to be solved is that you have an input and a series of functions, and you want to apply the functions to the input in order.

If the functions are purely state-changing functions, s -> s on an input of type s, then you don't need State to use them. Haskell is very good at chaining together functions like these, e.g. with the standard composition operator ., or something like foldr (.) id, or foldr id.

However, if the functions both mutate a state and report some result of doing so, so that you could give them the type s -> (s,a), then gluing them all together is a bit of a nuisance. You have to unpack the result tuple and pass the new state value to the next function, use the reported value somewhere else, and then unpack that result, and so on. It's easy to pass the wrong state to an input function because you have to name each result and input explicitly to do the unpacking. You end up with something like this:

  (res1, s1) = fun1 s0
  (res2, s2) = fun2 s1
  (res3, s3) = fun3 res1 res2 s1
  in resN

There, I accidentally passed s1 instead of s2, maybe because I added the second line in later and didn't realise the third line needed changing. When composing the s -> s functions, this problem can't possibly arise because there are no names to get right:

  resN = fun1 . fun2 . fun3 . -- etc.

So we invented State to do the same trick. State is essentially just a way of gluing functions like s -> (s,a) together in such a way that the right state always gets passed to the right function.

So it's not so much that people went "we want to use State, let's use s -> (s,a)" but rather "we're writing functions like s -> (s,a), let's invent State to make that easy". With functions s -> s, it's already easy and we don't have to invent anything.

As an example of how s -> (s,a) arises naturally, consider parsing: a parser will be given some input, consume some of the input and return a value. In Haskell, this is naturally modelled as taking an input list, and returning a pair of the value and the remaining input - i.e. [Input] -> ([Input], a), or State [Input].

share|improve this answer

Your Answer


