Finite state machine written in OCaml to test for the sequence 0,1

I got inspired by Stack Overflow to build a simple state machine which can test if a sequence contains 0,1. I have two questions:

1. How can I get rid of line | _ -> (function q0 -> q0 | q2 -> q2 | q1 -> q1)
2. How can I improve that code?

(If it is matters, I came from Python and many things in OCaml seem unusual to me).

(*
--->  q0  ---0-->  q2  ---1--->   q1
/  \         /  \          /    \
-1->         -0->          -0,1->
*)

type ('state, 'number) state_machine = {
initial: 'state;
final: 'state -> string;
transition: 'number -> 'state -> 'state;
};;

let state_machine_01 sequence =
let machine_01 = {
initial = q0;
final = (function q0 -> "Init" | q2 -> "Found zero" | q1 -> "END" );
transition = (function
| 0 -> (function q0 -> q2 | q2 -> q2 | q1 -> q1)
| 1 -> (function q0 -> q0 | q2 -> q1 | q1 -> q1)
| _ -> (function q0 -> q0 | q2 -> q2 | q1 -> q1)
);
} in

let state = ref machine_01.initial in
for i = 0 to (List.length sequence) - 1 do
state := (machine_01.transition (List.nth sequence i)) !state
done;
machine_01.final !state;
;;

let () =
Printf.printf "------------- start --------------- \n";

Printf.printf "%s\n" (state_machine_01 [1; 1; 0; 0; 0; 1; 0; 1]);
Printf.printf "%s\n" (state_machine_01 [1; 1; 0; 0; 0]);
Printf.printf "%s\n" (state_machine_01 [1; 1; 1]);

Printf.printf "-------------- end ---------------- \n";
;;

• There are many aspects you may want to improve : readability, performance, safety, functional style (versus imperative style), evolvability... What do you want to improve?
– Lucky J.
Mar 15, 2016 at 13:56
• @LuckyJ. first of all - data structures, may be there is better way to implement state machine, second, how to rewrite without matching any number but just 0 and 1 and don't get warning. Mar 15, 2016 at 14:00
• A very important difference between Python and OCaml is that the static type system of OCaml allows many static analyses by the compiler. So you should exploit that. For instance, you can declare the type of states for a given automata (type state = Q0 | Q1 | Q2), the type of events (type event = Zero | One), the type of results (type result = Init | Found | End). With such closed types, you will have the compiler check that your pattern matchings are exhaustive, and also the "catch all" pattern will become useless (and the compiler will tell you that).
– Lucky J.
Mar 15, 2016 at 14:09
• To complete my previous comment, polymorphic variants of OCaml (open types, with backquotes in constructors in your code) are great, but I think you don't need them here.
– Lucky J.
Mar 15, 2016 at 14:13

I notice that you represent states as functions. This does give some expressive power, as seen in the composition example given in your linked answer.

If that power isn't needed we can write things directly and simply:

type element = Z | O

let rec start list = look_for_zero list

and look_for_zero = function
| [] -> "nothing"
| Z::rest -> have_zero rest
| O::rest -> look_for_zero rest

and have_zero = function
| [] -> "nothing"
| O::_ -> "yes!"
| Z::rest -> look_for_zero rest


If you want to stick with the given framework, then you can simplify a bit and transform into a functional style:

type ('state, 'number) state_machine = {
initial: 'state;
final: 'state -> string;
transition: 'state -> 'number -> 'state; (* I changed the order! *)
};;

type state = Init | HaveZero | FoundZeroOne
type element = Zero | One

let final = function
| Init | HaveZero -> "no"
| FoundZeroOne -> "yes"

let transition state n =
match n, state with
| _, FoundZeroOne -> FoundZeroOne
| Zero, _ -> HaveZero
| One, Init -> Init
| One, HaveZero -> FoundZeroOne

let machine = {
initial = Init;
final;
transition;
}

let run_machine machine list =
machine.final
(List.fold_left machine.transition machine.initial list)