Simple FSMs and event-sourcing in Haskell

Posted on March 25, 2017
Tags: Haskell, FSM, event-sourcing

In this post I want to briefly show you one way to encode finite-state machines (FSM) and use them with event sourcing. For the purposes of this post I’ll use Haskell with just basic data types and functions, so translating it in your language of choice should be relatively easy.

The problem

This is the particular FSM we want to encode:

It’s not very complicated isn’t it? It represents the states of a resource (for example a document) and the possible transitions between them. In other words, the FSM represents a process that the resource goes through. Potentially with multiple users involved.

You can think of the states transitions as domain events in an event sourced application. From this point of view, the document state is a projection of domain events that is computed by processing the events sequentially according to rules represented by the FSM. In other words, domain events represents what happened and the document state is derived from them according to a FSM. In this sense, the FSM gives an interpretation of what happened in the domain in the past according to a codified process. A nice property of this interpretation is that this process can change and the document state can be recalculated by replaying the events.

Solution

First of all, we encode the possible states:

data State
    = InProgress
    | Approved
    | Rejected
    | Deleted
    deriving (Eq,Show)

Nothing fancy here. It’s just a sum type (you can think of it as an enumeration).

We also encode the possibile state transitions (which are events in this example):

data Event
    = Create
    | Approve
    | Reject
    | Delete
    deriving (Eq,Show)

Please note that this is a simplistic definition where we assume that we’re working with a single document. Supporting arbitrary resources is not that difficult and I leave it as an exercise to the adventurous readers.

At this point, we need to encode state transitions in some way. Given a state and an event, we want to compute the next one:

transition :: State -> Event -> State

But remember that we have the Create event, which is a transition without a starting state. So, the initial state must be optional:

transition :: Maybe State -> Event -> State

At this point we must also consider that not all transitions are valid from a given state. For example, if we are in the Approved state, how we react to the Reject event? One possible option would be to NOT transition the state, but this way we would treat in the same way two very different cases:

To differentiate those two cases and obtain a validation of an ordered sequence of events in relation to our process, we make the transitioned state optional too. This way if the required transition is invalid, we’d get a Nothing.

transition :: Maybe State -> Event -> Maybe State

Futhermore, now that the input and output states are of the same type we can easily chain multiple transitions sequentially again.

The implementation is fairly straightforward:

transition :: Maybe State -> Event -> Maybe State
transition Nothing           Create  = Just InProgress
transition (Just InProgress) Approve = Just Approved
transition (Just InProgress) Reject  = Just Rejected
transition (Just _)          Delete  = Just Deleted
transition s                 _       = Nothing

An advantage of encoding state transitions as a function using Haskell is that we get completeness checking for free: the compiler will warn you if you forget to cover some state-event combinations. Another advantage of Haskell is that we can use pattern matching and concisely express some rules like:

Now we have everything we need to implement our projection:

project :: [Event] -> Maybe State
project = foldl transition Nothing

Here project takes an ordered list of events and computes the final state by sequentially applying transition to them. You can notice that the starting state is Nothing since we expect a Create event to transition to the InProgress state.

Thanks to Currying, I didn’t need to explicitly include the [Event] parameter in the function implementation.

A nice property of this implementation is that we get events stream validation for free. If project returns Nothing, it means that the input events are incompatible with out FSM.

Snapshots

We can also easily support snapshots with minimal changes! We just need to be able to apply a set of events to an arbitrary initial state, not… just Nothing (pun not intended).

We just need to generalize project by adding the initial state as an additional argument:

project :: Maybe State -> [Event] -> Maybe State
project start = foldl transition start

And for convenience we can write another function to project all the events:

projectAll :: [Event] -> Maybe State
projectAll = project Nothing

That’s it! We can easily test the code using GHCi:

*FSM> projectAll [Create, Approve]
Just Approved
*FSM> projectAll [Create, Reject, Delete]
Just Deleted
*FSM> projectAll [Delete]
Nothing
*FSM> projectAll [Create, Approve, Reject]
Nothing
*FSM> project (Just Approved) [Delete]                         
Just Deleted

Appendix: the complete solution

module FSM where

data State
    = InProgress
    | Approved
    | Rejected
    | Deleted
    deriving (Eq,Show)

data Event
    = Create
    | Approve
    | Reject
    | Delete
    deriving (Eq,Show)

transition :: Maybe State -> Event -> Maybe State
transition Nothing Create = Just InProgress
transition (Just InProgress) Approve = Just Approved
transition (Just InProgress) Reject = Just Rejected
transition (Just _) Delete = Just Deleted
transition s _ = Nothing

project :: Maybe State -> [Event] -> Maybe State
project start = foldl transition start

projectAll :: [Event] -> Maybe State
projectAll = project Nothing