State monad in fp-ts
Tags: functional, typescript
Published: 2022-01-19 12:52:46

Consider the gumball machine

![Picture of a gumball machine](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nrmk6ps212klbxbyrylj.png)

It is in a unpaid or paid state and the output of it is either nothing or a gumball.

```typescript
type State = Unpaid | Paid;
type Gumball = "Gumball";
type Output = O.Option<Gumball>;
```
Now let's consider the transitions. When we pay 50c into this gumball machine, it will put it into the Paid state. If the machine is in a paid state and we turn the handle, we get a gumball and the machine reverts back to an Unpaid state. All other transitions, we get nothing and the state remains the same.

![State transition diagram](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pdv7mkwcaa1d2sl5a2vq.png)

To model these state transitions, let's use the [fp-ts State type](https://gcanti.github.io/fp-ts/modules/State.ts.html#state-interface)
```typescript
// State s a :: s -> (a,s)
export interface State<S, A> {
  (s: S): [A, S]
}
```
which translated means give me an initial state s and I'll give you some output A and the new state. Now calling this interface State is a bit confusing as it is really more of a State processor whereas the actual state type is inside the generic parameter S.

Hence our pay and turn function looks like the following:

```typescript
//state transition functions are of the type State -> (Output, State)
const pay = (amount: number): S.State<State, Output> => (state: State) => {
  switch (amount) {
    case 50:
      return [O.none, "Paid"];
    default:
      return [O.none, state];
  }
};

const turn: S.State<State, Output> = (state: State) => {
  switch (state) {
    case "Unpaid":
      return [O.none, state];
    case "Paid":
      return [O.some("Gumball"), "Unpaid"];
  }
};

//Single usage:
pay(50)("Unpaid"); // [O.none, "Paid"];
turn("Paid"); // [O.some("Gumball"), "Unpaid"]
```

Now here comes the tricky part, how do we combine these functions together to build up our state machine? The key is that State s is an instance of Monad and that we can use bind/chain to combine our different state transition functions into a single one. Switching to Haskell for a second,

```
// (>>=) :: (Monad m) => m a -> (a -> m b) -> m b
// instance Monad (State s)
// (>>=) :: (Monad (State s)) => State s a -> (a -> State s b) -> State s b
```
Let's unpack this. First we have the definition of bind (>>=) or chain as it is in known in fp-ts. Next we see that our instance of Monad is (State s) so we should substitute (State s) wherever we see m. Finally we are left with the definition of bind specialised to the State monad. which we will take a look at now in parts. Ie `State s a`, `(a -> State s b)` and `State s b`. 

```
//State s a :: s -> (a,s)
```
We remember that `State s a` is a state transition function that takes a state s and returns back an output a and a new state. So we expand it out.
```
//a - > State s b :: a -> s -> (b, s)
```
Expanding out `State s b` to `s -> (b,s)`, we see that the second part is a function that takes in some input of type `a`, some state of type `s` and returns back a new output of type `b` and a new state.

```
//State s b :: s -> (b, s)
```
The return value is a new state transition function of `State s b`.

```
// (>>=) :: (State s) => State s a -> (a -> State s b) -> State s b
```
Let's bring it altogether now. 

> Bind takes the first state transition function and gets the output and state from that to feed it to the second state transition function creating a new combined state transition function.

Switching back to fp-ts land and our gumball machine, how would we combine our `pay(50)` and `turn` functions? Keeping in mind that `S.chain` is a flipped version of bind, we use the following: Note that we use `() => turn` because our gumball machine transitions do not depend on the output of a previous state transition.

```typescript
const combined = S.chain(() => turn)(pay(50));
combined('Unpaid') // [O.some("Gumball"), "Unpaid"]
```

Now that we know that monadic composition is available to us, we can use functions like `S.sequeunceArray` to combine an array of state transition functions into a single state transition function that returns a collected array of outputs as well as the final state.

```typescript
const actions = [pay(5), turn, pay(50), turn, turn, pay(50), turn];
const [outputs, finalState] = S.sequenceArray(actions)('Unpaid');
const numGumballs = outputs.filter(O.isSome).length; //2
```

Sample code: https://codesandbox.io/s/ancient-firefly-3lgrg?file=/src/index.ts

Further reading:
- http://brandon.si/code/the-state-monad-a-tutorial-for-the-confused/
- https://en.wikibooks.org/wiki/Haskell/Understanding_monads/State