A finite state machine is an extremely simple computational device that we will use to process strings. It decides whether or not to accept a given string, based on finite set of rules.
Haskell is a purely functional programming language. It is one of the most elegant ways (that I know) to write programs. I will be writing a simple finite state automaton (or state machine) using pure functions - no monads or trickery of any kind. It is not meant to be an exercise in advanced Haskell and theoretical computer science. I am going to assume that the reader has some basic familiarity with Haskell and automata. If you don’t, there are some great free online resources for learning them.
So, we know that we cannot destructively update variables in the same way that we can in almost every other programming language. Something as simple as the following piece of pseudocode can’t be done in Haskell (or at least not without the use of complicated structures whose origin lies in abstract algebra).
Generally, mutating variables as above is how we represent states in computations in most languages. But, since these are not easily available in Haskell, how do we write a stateful computation? How can we store the state of the automaton without updating a variable?
To Understand Recursion One Must First Understand Recursion
The main idea in this implementation is the following:
Destructively updating variables is one (of many) ways to encode state within a computation. As I implied earlier, I won’t be using the state monad for this automaton. We can also store the state of a computation as an argument to a recursive function. This is a powerful idea and forms the basis for this FSM.
We will be implementing the FSM described by the following directed graph:
\(S_0\) is the initial state, as indicated by the lone arrow pointing to it. As the graph might suggest, this FSM only operates on strings consisting of ‘a’ and ‘b’.
In this simple example, the FSM will be completely hard-coded. This is just a demonstration that stateful computing can be done using pure functions, albeit in a slightly disguised form.
We take advantage of the fact that the problem affords a natural recursion. Given a state and a current character, the machine does not care how we arrived at that combination. It will transition to the next state regardless of how it got to the current one.
The general scheme can be described as:
- The current state is known
- Read a character from the front of the string
- Decide which state to transition to and go back to 1.
First, let’s define an algebraic data type that will represent the state of the machine.
The machine consists of two functions. The first one is essentially a list of general transition rules, without regard to the machine’s initial state.
It has the following type signature:
This takes a
State and a
String, and returns
Now, we use Haskell’s expressive and powerful pattern matching.
Each line corresponds to one of the machine’s transition rules.
That is, each edge in the graph above is represented by exactly one
There is an injective mapping
from the edges to the individual lines of the Haskell code.
As an example, the first line reads:
This line means: if the machine is in state \(S_0\), and the first character of the string is ‘a’, then transition to state \(S_1\).
accepts again, but this time, with a truncated string, and a new state.
Altogether, the function looks like:
Now, using partial functions (‘currying’ as it’s known, is one of the coolest
we wrap it in a clean function called
We could change the initial state of the machine by replacing
S0 in the
above code with another state such as
Running the machine in the Haskell shell:
I hoped to demonstrate that one does not necessarily need to use mutable variables or monads to write programs that are inherently stateful. The state just manifests itself differently.