FSM is a minimalist library for functionally defining state-machines in F#, although the approach may be generalised to any language supporting higher order functions. In FSM, a state is defined as a computation of the next state. This makes it possible to write state-machines as n-level DFAs or NFAs.

The base of this approach is the State function:

State<'a, 'b> = State<'a, 'b> * 'a -> State<'a, 'b> * 'b 

A state takes in a state and an input, and returns the next state and an output. A higher order state has input values which are states. To create a statemachine, supply it with the initial state and call Move to move the machine to the next state:

sm = StateMachine(<intial state>) sm.Move(value) 

From the definition (s, a) -> (s', b), the simplest state-machine we can define is one with a single state that transitions onto itself. (I: S → S)

identity = State(fun s v -> s, v) 

Another simple two state machine can be an even-odd machine. (P: Even → Odd → Even)

oddeven = State(fun s v -> State(fun _ v -> s, Odd), Even) 

spelled out better as:

oddeven = State(fun even v -> State(fun odd v -> even, Odd), Even) 

Here, the next odd state is generated by the even state.

To define this in a more conventional way, we can express it like so:

let rec odd = State(fun s v -> even, Odd) and even = State(fun s v -> odd, Even) 

This is easily defined in lazy languages like Haskell, but since F# has strict evaluation, the compiler will warn about recursive references. To get around this, we can use also reference cells.

odd := State(fun _ _ -> !even, Odd) even := State(fun _ _ -> !odd, Even) 

The initial value of the reference cell can be set as States.zero.

A state machine which checks if numbers are divisible by 3 given binary input:

let rec A = State(fun s v -> if v = 0 then s, 0 else B, 0) and B = State(fun s v -> if v = 0 then C, 0 else A, 1) and C = State(fun s v -> if v = 0 then B, 0 else s, 0) 

A recursive function can allow any type of state to be maintained internally.

let evenodd = let rec evenOddFn state = let ns = match state with | Even -> Odd | Odd -> Even State(fun s v -> evenOddFn state, v) evenOddFn Even //initial state 

This can be be rewritten using States.define as:

let evenOddfn _ = function | Even -> Odd | Odd -> Even let evenodd = States.define evenOddfn Even 

State combinators are higher order functions which can be to declaratively combine states.

For example,

let valuecards _ = function Number(n) when n > 1 -> Number(n - 1) | _ -> Joker let initial = States.define valuecards (Number 10) |> States.startWith [ Ace; Queen; King; Jack ] 

returns a sequence of all the cards (Ace, Queen, ... Number(1), Joker).

To execute side-effects on evaluating a state, the doAction combinator is useful:

let rec odd = State(fun s v -> even, Odd) |> States.doAction (printfn "odd: %A -> %A") and even = State(fun s v -> odd, Even) |> States.doAction (printfn "even: %A -> %A") 

Similarly other combinators like moveIf and moveIfElse can be use to declaratively encode transitions. The former example for divisible by 3 rewritten:

let rec A = moveIf ((=) 1) 1 (lazily (lazy B)) and B = moveIfElse ((=) 0) 0 C (lazily (lazy A)) and C = moveIf ((=) 0) 0 (lazily (lazy B)) 

For example, to represent a lock which becomes active after entering the sequence [1, 2, 3] (any other number out of sequence causes it to go back to the starting state):

let rec checkPin = States.returnValue "Success" |> States.moveIfElse ((=) 3) "C3" init |> States.moveIfElse ((=) 2) "C2" init |> States.moveIfElse ((=) 1) "C1" init and init = States.lazily (lazy checkPin) 

By repeatedly applying this combinator, this can be generalized to be constructed around any list:

let moveSeq endState list = let rec move zero = function | [] -> endState | x::xs -> States.moveIfElse ((=) x) (sprintf "State: %A" x) zero (move zero xs) let rec initial = move (States.lazily (lazy initial)) list initial 

Most combinators are simplistic and are defined in a single line lambda function.