+It's possible to do all of this monadically, and so using a language's existing resources, instead of adding new syntactic forms and new interpretation rules to the semantics. The patterns we use to do this in fact closely mirror the machinery described above.
+
+We call this a State monad. It's a lot like the Reader monad, except that with the Reader monad, we could only read from the environment. We did have the possibility of interpreting sub-expressions inside a "shifted" environment, but as you'll see, that corresponds to the "shadowing" behavior described before, not to the mutation behavior that we're trying to implement now.
+
+With a State monad, we call our book-keeping apparatus a "state" or "store" instead of an evironment, and this time we are able to both read from it and write to it. To keep things simple, we'll work here with the simplest possible kind of store, which only holds a single value. One could also have stores that were composed of a list of values, of a length that could expand or shrink, or even more complex structures.
+
+Here's the implementation of the State monad, together with an implementation of the Reader monad for comparison:
+
+ type env = (char * int) list;;
+ (* alternatively, an env could be implemented as type char -> int *)
+
+ type 'a reader = env -> 'a;;
+ let unit_reader (value : 'a) : 'a reader =
+ fun e -> value;;
+ let bind_reader (u : 'a reader) (f : 'a -> 'b reader) : 'b reader =
+ fun e -> let a = u e
+ in let u' = f a
+ in u' e;;
+
+ type store = int;;
+ (* very simple store, holds only a single int *)
+ (* this corresponds to having only a single mutable variable *)
+
+ type 'a state = store -> ('a, store);;
+ let unit_state (value : 'a) : 'a state =
+ fun s -> (value, s);;
+ let bind_state (u : 'a state) (f : 'a -> 'b state) : 'b state =
+ fun s -> let (a, s') = u s
+ in let u' = f a
+ in u' s';;
+
+Notice the similarities (and differences) between the implementation of these two monads.
+
+With the Reader monad, we also had some special-purpose operations, beyond its general monadic operations. These were `lookup` and `shift`. With the State monad, we'll also have some special-purpose operations. We'll consider two basic ones here. One will be to retrieve what is the current store. This is like the Reader monad's `lookup`, except in this simple implementation there's only a single location for a value to be looked up from. Here's how we'll do it:
+
+ let get_state : 'a -> store state =
+ fun _ ->
+ fun s -> (s, s);;
+
+This passes through the current store unaltered, and also returns a copy of the store as its value. Note the beginning `fun _ ->` part. That's so we can use this operation like this:
+
+ some_existing_state_monad >>= get_state >>= (fun cur_state -> ...)
+
+The `get_state` operation ignores the value wrapped by `some_existing_state_monad`. It just passes through whatever store is generated by `some_existing_state_monad`. It also wraps that store as its own value, which can be retrieved by further operations in the `... >>= ...` chain, such as the `(fun cur_state -> ...)`.
+
+The other operation for the state monad will be to update the existing store to a new one. This operation looks like this:
+
+ let set_state (value : int) : 'a -> dummy state =
+ fun s -> (dummy, value);;
+
+If we want to stick this in a `... >>= ...` chain, we'll need to prefix it with `fun _ ->` too, like this:
+
+ some_existing_state_monad >>= fun _ -> set_state 100 >>= ...
+
+In this kind of usage, we don't care what value is wrapped by `some_existing_state_monad`. We don't even care what store it generates, since we're going to replace that store with our own new store. A more complex kind of `set_state` or `update_state` operation might use as a new store not just some constant value, but rather something which is the result of applying some function to the existing store. For example, we might want to increment the current store. Here's how we could do that:
+
+ some_existing_state_monad >>= get_state >>= (fun cur_state -> set_state (cur_state + 1) >>= ...
+
+We can of course define more complex functions that perform the `get_state >>= (fun cur_state -> set_state (cur_state + 1)` as a single operation.
+
+In general, a State monadic value (what appears at the start of a `... >>= ... >>= ...` chain) is an operation that accepts some starting store as input---where the store might be simple as it is here, or much more complex---and returns a value plus a possibly modified store. This can be thought of as an encoding of a operation on the store as a box wrapped around a value.
+
+State monadic operations (what appears anywhere in the middle or end of a `... >>= ... >>= ...` chain) are operations that generate new State monadic values, based on what value was wrapped by the preceding elements in the `... >>= ... >>= ...` chain. The computations on the store that these encode (which their values may or may not be sensitive to) will be chained in the order given by their position in the `... >>= ... >>= ...` chain. That is, the computation encoded by the first element in the chain will accept a starting store s0 as input, and will return (a value and) a new store s1 as output, the next computation will get s1 as input and will return s2 as output, the next computation will get s2 as input, ... and so on.
+
+To get the whole process started, the complex computation so defined will need to be given a starting store. So we'd need to do something like this:
+
+ let computation = some_state_monadic_value >>= operation >>= operation
+ in computation initial_store;;
+
+