Editing Monad (functional programming) (section)

===State monads===

{{See also|Monad (category theory)#The state monad}}

A state monad allows a programmer to attach state information of any type to a calculation. Given any value type, the corresponding type in the state monad is a function which accepts a state, then outputs a new state (of type <code>s</code>) along with a return value (of type <code>t</code>). This is similar to an environment monad, except that it also returns a new state, and thus allows modeling a ''mutable'' environment.

<syntaxhighlight lang="haskell">
type State s t = s -> (t, s)
</syntaxhighlight>

Note that this monad takes a type parameter, the type of the state information. The monad operations are defined as follows:

<syntaxhighlight lang="haskell">
-- "return" produces the given value without changing the state.
return x = \s -> (x, s)
-- "bind" modifies m so that it applies f to its result.
m >>= f = \r -> let (x, s) = m r in (f x) s
</syntaxhighlight>

Useful state operations include:
<syntaxhighlight lang="haskell">
get = \s -> (s, s) -- Examine the state at this point in the computation.
put s = \_ -> ((), s) -- Replace the state.
modify f = \s -> ((), f s) -- Update the state
</syntaxhighlight>

Another operation applies a state monad to a given initial state:
<syntaxhighlight lang="haskell">
runState :: State s a -> s -> (a, s)
runState t s = t s
</syntaxhighlight>

do-blocks in a state monad are sequences of operations that can examine and update the state data.

Informally, a state monad of state type {{mvar|S}} maps the type of return values {{mvar|T}} into functions of type <math>S \rarr T \times S</math>, where {{mvar|S}} is the underlying state. The {{math|return}} and {{math|bind}} function are:
:<math>\begin{array}{ll}
\text{return} \colon & T \rarr S \rarr T \times S = t \mapsto s \mapsto (t, s) \\
\text{bind} \colon & (S \rarr T \times S) \rarr (T \rarr S \rarr T' \times S) \rarr S \rarr T' \times S \ = m \mapsto k \mapsto s \mapsto (k \ t \ s') \quad \text{where} \; (t, s') = m \, s
\end{array}
</math>.

From the category theory point of view, a state monad is derived from the adjunction between the product functor and the exponential functor, which exists in any [[cartesian closed category]] by definition.