If you have programmed in any other language before, you likely wrote some functions that "kept state". For those new to the concept, a state is one or more variables that are required to perform some computation but are not among the arguments of the relevant function. Object-oriented languages, like C++, suggest extensive use of state variables within objects in the form of member variables. Programs written in procedural languages, like C, typically use variables declared outside the current scope to keep track of state.

In Haskell, however, such techniques cannot be applied in a straightforward way; they require mutable variables, and that clashes with Haskell's functional purity. We can usually keep track of state by passing parameters from function to function or by pattern matching of various sorts, but in some cases it is appropriate to find a more general or convenient solution. We will consider the common example of how the `State` monad can assist us in generating pseudo-random numbers.

## Pseudo-Random Numbers

Generating actual random numbers is a very complicated subject. Computer programming almost always sticks to pseudo-random numbers. They are called "pseudo" because they are not truly random. Starting from an initial state (commonly called the seed), pseudo-random number generators produce a sequence of numbers that have the appearance of being random.

Every time a pseudo-random number is requested, a global state is updated.[1] Sequences of pseudo-random numbers can be replicated exactly if the initial seed and the algorithm is known.

Producing a pseudo-random number in most programming languages is very simple: there is usually a function, such as C or C++'s `rand()`, that provides a pseudo-random value (or a truly random one, depending on the implementation). Haskell has a similar one in the `System.Random` module:

```> :m System.Random
> :t randomIO
randomIO :: Random a => IO a
> randomIO
-1557093684
```

This function references a mutable state that is held outside Haskell and interacted with via `IO`, so values obtained using `randomIO` will be different every time.

### Example: Rolling Dice

`randomRIO (1,6)`

Suppose we are coding a game in which at some point we need an element of chance. In real-life games that is often obtained by means of dice. So, let's create a dice-throwing function in Haskell.

We'll use the function `randomR` to specify an interval from which the pseudo-random values will be taken; in the case of a die, it is `randomR (1,6)`. To make sure we get new values each time we roll, we'll use the `IO` version of `randomR`:

```import Control.Monad
import System.Random

rollDiceIO :: IO (Int, Int)
rollDiceIO = liftM2 (,) (randomRIO (1,6)) (randomRIO (1,6))
```

That function rolls two dice. Here, `liftM2` is used to make the non-monadic two-argument function `(,)` work within a monad. The `(,)` is the non-infix version of the tuple constructor. Thus, the two die rolls will be returned (in `IO`) as a tuple.

Exercises
1. Implement a function `rollNDiceIO :: Int -> IO [Int]` that, given an integer (a number of die rolls), returns a list of that number of pseudo-random integers between 1 and 6.

### Getting Rid of the `IO` Monad

A disadvantage of `randomIO` is that it requires us to utilize the `IO` monad and store our state outside the program where we can't control what happens to it. We would prefer to only use IO when we really have a good reason to interact with the outside world.

To avoid the IO Monad, we can build a local generator. From the `System.Random` module, we can use the `random` and `mkStdGen` functions to generate tuples containing a pseudo-random number together with a new generator to use the next time the function is called.

```> :m System.Random
> let generator = mkStdGen 0           -- "0" is our seed
> generator
1 1
> random generator :: (Int, StdGen)
(2092838931,1601120196 1655838864)
```

Now, we've avoided the IO Monad, but there are new problems. First and foremost, if we want to use `generator` to get random numbers, the obvious definition...

```> let randInt = fst . random \$ generator :: Int
> randInt
2092838931
```

...is useless; it will always give back the same value, `2092838931`, every time (because the same generator is always used). To solve this, we can take the second member of the tuple (i.e. the new generator) and feed it to a new call to `random`:

```> let (randInt, generator') = random generator :: (Int, StdGen)
> randInt                            -- Same value
2092838931
> random generator' :: (Int, StdGen) -- Using new generator' returned from “random generator”
(-2143208520,439883729 1872071452)
```

Of course, this is clumsy and tedious. We need to keep creating new functions for new calls, and we're stuck with the fuss of having to carefully pass the generator around.

### Dice without IO

We can re-do our dice throw with our new approach:

```> randomR (1,6) (mkStdGen 0)
(6, 40014 40692)
```

This tuple combines the result of throwing a single die with a new generator number. A simple implementation for throwing two dice is then:

```clumsyRollDice :: (Int, Int)
clumsyRollDice = (n, m)
where
(n, g) = randomR (1,6) (mkStdGen 0)
(m, _) = randomR (1,6) g
```
Exercises
1. Implement a function `rollDice :: StdGen -> ((Int, Int), StdGen)` that, given a generator, return a tuple with our random numbers as first element and the last generator as the second.

The implementation of `clumsyRollDice` works as a one-off, but we have to manually write the passing of generator `g` from one `where` clause to the other. This approach will become increasingly cumbersome if we want to produce larger sets of pseudo-random numbers. It is also error-prone: what if we pass one of the middle generators to the wrong line in the `where` clause?

What we really need is a way to automate the extraction of the second member of the tuple (i.e. the new generator) and feed it to a new call to `random`. This is where the `State` monad comes into the picture.

## Introducing `State`

Note

In this chapter we will use the state monad provided by the module `Control.Monad.Trans.State` of the `transformers` package. By reading Haskell code in the wild, you will soon meet `Control.Monad.State`, a module of the closely related `mtl` package. The differences between these two modules need not concern us at the moment; everything we discuss here also applies to the `mtl` variant.

The Haskell type `State` describes functions that consume a state and produce a tuple that contains a result along with the new state after the result has been extracted.

The state function is wrapped by a data type definition which comes along with a `runState` accessor so that pattern matching becomes unnecessary. For our current purposes, consider the definition equivalent to:[2]

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

Here, `s` is the type of the state, and `a` the type of the produced result. Calling our type `State` is arguably a bit of a misnomer because the wrapped value is not the state itself but a state processor.

### newtype

Notice that we defined the data type with the `newtype` keyword, rather than the usual `data`. `newtype` can be used only for types with just one constructor and just one field. It ensures that the trivial wrapping and unwrapping of the single field is eliminated by the compiler. For that reason, simple wrapper types such as `State` are usually defined with `newtype`. Would defining a synonym with `type` be enough in such cases? Not really, because `type` does not allow us to define instances for the new data type, which is what we are about to do...

In contrast to the monads we have met thus far, `State` has two type parameters. To define a Monad, we need to combine `State` with a second parameter.

```instance Monad (State s) where
```

So, there are many different `State` monads including `State String`, `State Int`, `State SomeLargeDataStructure`, and so on…

The `return` function is implemented as:

```return :: a -> State s a
return x = State ( \ st -> (x, st) )
```

In words, giving a value to `return` produces a function wrapped in the `State` constructor. The function takes a state value, and returns it unchanged as the second member of a tuple, together with the specified result value.

Binding is a bit intricate:

```(>>=) :: State s a -> (a -> State s b) -> State s b
processor >>= processorGenerator = State \$ \ st ->
let (x, st') = runState processor st
in runState (processorGenerator x) st'
```

`(>>=)` is given a state processor and a function that can generate another processor using the result of the first one. The two processors are combined to obtain a function that takes the initial state, and returns the second result and state (i.e. after the second function has processed them).

Loose schematic representation of how bind creates a new state processor (pAB) from the given state processor (pA) and the given generator (f). s1, s2 and s3 are actual states. v2 and v3 are values. pA, pB and pAB are state processors. The diagram ignores wrapping and unwrapping of the functions in the State wrapper.

The diagram shows this schematically, for a slightly different, but equivalent form of the ">>=" (bind) function, given below (where wpA and wpAB are wrapped versions of pA and pAB).

```-- pAB = s1 --> pA --> (v2,s2) --> pB --> (v3,s3)
wpA >>= f = wpAB
where wpAB = State \$ \s1 -> let pA = runState wpA
(v2, s2) = pA s1
pB = runState \$ f v2
(v3,s3) = pB s2
in  (v3,s3)
```

### Setting and Accessing the State

The monad instantiation allows us to manipulate various state processors, but you may at this point wonder where exactly the original state comes from in the first place. `State s` is also an instance of the `MonadState` class, which provides two additional functions:

```put newState = State \$ \_ -> ((), newState)
```

Given a state, this function will generate a state processor. The processor's input will be disregarded, and the output will be a tuple carrying the state we provided. Since we do not care about the result (we are discarding the input, after all), the first element of the tuple will be "null".[3]

The specular operation reads the state. This is accomplished by `get`:

```get = State \$ \st -> (st, st)
```

The resulting state processor produces the input `st` in both positions of the output tuple (i.e. both as a result and as a state) so that it may be bound to other processors.

### Getting Values and State

From the definition of `State`, we know that `runState` is an accessor to apply to a `State a b` value to get the state-processing function. That function, given an initial state, will return the extracted value and the new state.

Other similar functions are `evalState` and `execState`. Given a `State a b` and an initial state, the function `evalState` will return the extracted value only, whereas `execState` will return only the new state.

```evalState :: State s a -> s -> a
evalState processor st = fst ( runState processor st )

execState :: State s a -> s -> s
execState processor st = snd ( runState processor st )
```

### Dice and state

Let's use the State monad for our dice throw examples.

To avoid the confusion with "State" and "state processor", we'll use a type synonym:

```import Control.Monad.Trans.State
import System.Random

type GeneratorState = State StdGen
```

So, `GeneratorState Int` is in essence a `StdGen -> (Int, StdGen)` function and is a processor of the generator state. The generator state itself is produced by the `mkStdGen` function. Note that `GeneratorState` does not specify what type of values we are going to extract, only the type of the state.

We can now produce a function that, given a `StdGen` generator, outputs a number between 1 and 6.

```rollDie :: GeneratorState Int
rollDie = do generator <- get
let (value, newGenerator) = randomR (1,6) generator
put newGenerator
return value
```

Let's go through each of the steps:

1. First, we take out the pseudo-random generator with `<-` in conjunction with `get`. `get` overwrites the monadic value (The 'a' in 'm a') with the state, binding the generator to the state. (If in doubt, recall the definition of `get` and `>>=` above).
2. Then, we use the `randomR` function to produce an integer between 1 and 6 using the generator we took; we also store the new generator graciously returned by `randomR`.
3. We then set the state to be the `newGenerator` using the `put` function, so that the next call will use a different pseudo-random generator;
4. Finally, we inject the result into the `GeneratorState` monad using `return`.

We can finally use our monadic die:

```> evalState rollDie (mkStdGen 0)
6
```

Why have we involved monads and built such an intricate framework only to do exactly what `fst \$ randomR (1,6)` already does? Well, consider the following function:

```rollDice :: GeneratorState (Int, Int)
rollDice = liftM2 (,) rollDie rollDie
```

We obtain a function producing two pseudo-random numbers in a tuple. Note that these are in general different:

```> evalState rollDice (mkStdGen 666)
(6,1)
```

Under the hood, the monads are passing state to each other. It was previously very clunky using `randomR (1,6)` because we had to pass state manually. Now, the monad is taking care of that for us. Assuming we know how to use the lifting functions, constructing intricate combinations of pseudo-random numbers (tuples, lists, whatever) has suddenly become much easier.

Exercises
1. Similarly to what was done for `rollNDiceIO`, implement a function `rollNDice :: Int -> GeneratorState [Int]` that, given an integer, returns a list with that number of pseudo-random integers between 1 and 6.

## Pseudo-random values of different types

Until now, we considered only `Int` as the type of the produced pseudo-random number. However, already when we defined the `GeneratorState` monad, we saw that it did not specify anything about the type of the returned value. In fact, there is one implicit assumption: that we can produce values of such a type with a call to `random`.

The `Random` class (capitalized) includes default implementations for functions generating `Int`, `Char`, `Integer`, `Bool`, `Double` and `Float`, so you can immediately generate any of those.

Because `GeneratorState` is "agnostic" in regard to the type of the pseudo-random value it produces, we can write a similarly "agnostic" function (analogous to `rollDie`) that provides a pseudo-random value of unspecified type (as long as it is an instance of `Random`):

```getRandom :: Random a => GeneratorState a
getRandom = do generator <- get
let (value, newGenerator) = random generator
put newGenerator
return value
```

Compared to `rollDie`, this function does not specify the `Int` type in its signature and uses `random` instead of `randomR`; otherwise, it is just the same. `getRandom` can be used for any instance of `Random`:

```> evalState getRandom (mkStdGen 0) :: Bool
True
> evalState getRandom (mkStdGen 0) :: Char
'\64685'
> evalState getRandom (mkStdGen 0) :: Double
0.9872770354820595
> evalState getRandom (mkStdGen 0) :: Integer
2092838931
```

Indeed, it becomes quite easy to conjure all these at once:

```allTypes :: GeneratorState (Int, Float, Char, Integer, Double, Bool, Int)
allTypes = liftM (,,,,,,) getRandom
`ap` getRandom
`ap` getRandom
`ap` getRandom
`ap` getRandom
`ap` getRandom
`ap` getRandom
```

Here we are forced to used the `ap` function, defined in `Control.Monad`, since there exists no `liftM7` (the standard libraries only go to `liftM5`). As you can see, `ap` fits multiple computations into an application of the (lifted) n-element-tuple constructor (in this case the 7-item `(,,,,,,)`). To understand `ap` further, look at its signature:

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

Remember then that type `a` in Haskell can be a function as well as a value, and compare to:

```>:type liftM (,,,,,,) getRandom
liftM (,,,,,) getRandom :: (Random a1) =>
State StdGen (b -> c -> d -> e -> f -> (a1, b, c, d, e, f))
```

The monad `m` is obviously `State StdGen` (which we "nicknamed" `GeneratorState`), while `ap`'s first argument is function `b -> c -> d -> e -> f -> (a1, b, c, d, e, f)`. Applying `ap` over and over (in this case 6 times), we finally get to the point where `b` is an actual value (in our case, a 7-element tuple), not another function. To sum it up, `ap` applies a function-in-a-monad to a monadic value (compare with `liftM`, which applies a function not in a monad to a monadic value).

So much for understanding the implementation. Function `allTypes` provides pseudo-random values for all default instances of `Random`; an additional `Int` is inserted at the end to prove that the generator is not the same, as the two `Int`s will be different.

```> evalState allTypes (mkStdGen 0)
(2092838931,9.953678e-4,'\825586',-868192881,0.4188001483955421,False,316817438)
```
Exercises
1. If you are not convinced that `State` is worth using, try to implement a function equivalent to `evalState allTypes` without making use of monads, i.e. with an approach similar to `clumsyRollDice` above.

## Notes

1. There are also other ways to seed a pseudo-random number generator without using a global state for the program. For example, a program could have an algorithm that starts with a seed from checking the current date and time (assuming the computer's clock is functioning, this will never be a repeated value).
2. The subtle issue with our approach is that the `transformers` package implements the `State` type in a somewhat different way. The differences do not affect how we use or understand `State`; as a consequence of them, however, `Control.Monad.Trans.State` does not export a `State` constructor. Rather, there is a `state` function,
```state :: (s -> (a, s)) -> State s a
```

which does the same job. As for why the implementation is not the obvious one we presented above, we will get back to that a few chapters down the road.

3. The technical term for the type of `()` is unit.
 State Solutions to exercises Monads edit this chapter Haskell edit book structure