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:


How can I get rid of line | _ -&gt; (function `q0 -&gt; `q0 | `q2 -&gt;
`q2 | `q1 -&gt; `q1)
How can I improve that code?


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

(*
---&gt;  q0  ---0--&gt;  q2  ---1---&gt;   q1
    /  \         /  \          /    \ 
    -1-&gt;         -0-&gt;          -0,1-&gt; 
*)

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


let state_machine_01 sequence =
    let machine_01 = {
        initial = `q0;
        final = (function `q0 -&gt; "Init" | `q2 -&gt; "Found zero" | `q1 -&gt; "END" );
        transition = (function
            | 0 -&gt; (function `q0 -&gt; `q2 | `q2 -&gt; `q2 | `q1 -&gt; `q1)
            | 1 -&gt; (function `q0 -&gt; `q0 | `q2 -&gt; `q1 | `q1 -&gt; `q1)
            | _ -&gt; (function `q0 -&gt; `q0 | `q2 -&gt; `q2 | `q1 -&gt; `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";
;;
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
  | [] -&gt; "nothing"
  | Z::rest -&gt; have_zero rest
  | O::rest -&gt; look_for_zero rest

and have_zero = function
  | [] -&gt; "nothing"
  | O::_ -&gt; "yes!"
  | Z::rest -&gt; 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 -&gt; string;
  transition: 'state -&gt; 'number -&gt; 'state; (* I changed the order! *)
};;

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

let final = function
  | Init | HaveZero -&gt; "no"
  | FoundZeroOne -&gt; "yes"

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

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

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