What?

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).

x = 10
print x
x = -35
print x
>>> 10
    -35

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:

FSM

\(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’.

How?

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:

  1. The current state is known
  2. Read a character from the front of the string
  3. Decide which state to transition to and go back to 1.

The Code

First, let’s define an algebraic data type that will represent the state of the machine.

data State = S0 | S1 | S2

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:

accepts :: State -> String -> Bool

This takes a State and a String, and returns True or False

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 line of accepts. There is an injective mapping from the edges to the individual lines of the Haskell code.

As an example, the first line reads:

accepts S0 ('a':xs) = accepts S1 xs

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\).

We call accepts again, but this time, with a truncated string, and a new state.

Altogether, the function looks like:

accepts :: State -> String -> Bool
accepts S0 ('a':xs) = accepts S1 xs
accepts S0 ('b':xs) = accepts S2 xs
accepts S1 ('a':xs) = accepts S2 xs
accepts S1 ('b':xs) = accepts S0 xs
accepts S2 ('a':xs) = accepts S0 xs
accepts S2 ('b':xs) = accepts S2 xs
accepts S2 _        = True
accepts _ _         = False

Now, using partial functions (‘currying’ as it’s known, is one of the coolest Haskell features), we wrap it in a clean function called decide:

decide :: String -> Bool
decide = accepts S0

We could change the initial state of the machine by replacing S0 in the above code with another state such as S1.

Running the machine in the Haskell shell:

*Main> decide "aaa"
False
*Main> decide "aaaabbaaa"
True
*Main> decide "babababa"
False

But Why?

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.