DEV Community

Derp
Derp

Posted on • Edited on

State monad in fp-ts

Consider the gumball machine

Picture of a gumball machine

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

type State = Unpaid | Paid;
type Gumball = "Gumball";
type Output = O.Option<Gumball>;
Enter fullscreen mode Exit fullscreen mode

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

To model these state transitions, let's use the fp-ts State type

// State s a :: s -> (a,s)
export interface State<S, A> {
  (s: S): [A, S]
}
Enter fullscreen mode Exit fullscreen mode

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:

//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"]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.

const combined = S.chain(() => turn)(pay(50));
combined('Unpaid') // [O.some("Gumball"), "Unpaid"]
Enter fullscreen mode Exit fullscreen mode

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.

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
Enter fullscreen mode Exit fullscreen mode

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

Further reading:

Top comments (0)