NFA and DFA implementation Can you review my F# code and point out some insights about it?

What I want to know, in order of relevance:


Avoid so much common code between DFA and NFA. I want to make something more generic, there is much code in common there.
Make it more F# idiomatic


Performance is not a concern. Readability is.

module DFA =
    type DeterministicFiniteAutomaton = {
        InitialState: string
        FinalStates: Set&lt;string&gt;
        Transitions: Map&lt;string * char, string&gt;
    }

    let private nextState (symbol:char) (state:string) (transitions:Map&lt;string * char, string&gt;) =
        transitions |&gt; Map.tryFind (state, symbol)

    let rec private haltState (input:string) (index:int) (state:string) (transitions:Map&lt;string * char, string&gt;) =
        match index with
        | i when i = input.Length -&gt; state
        | _ -&gt;
            match nextState input.[index] state transitions with
            | None -&gt; null
            | Some state -&gt; haltState input (index+1) state transitions

    let accepts (input:string) (dfa:DeterministicFiniteAutomaton) =
        dfa.FinalStates |&gt; Set.contains (haltState input 0 dfa.InitialState dfa.Transitions)

module NFA =
    type NondeterministicFiniteAutomaton = {
        InitialState: string
        FinalStates: Set&lt;string&gt;
        Transitions: Map&lt;string * char, string List&gt;
    }

    let private nextState (symbol:char) (state:string) (transitions:Map&lt;string * char, string List&gt;) =
        transitions |&gt; Map.tryFind (state, symbol)

    let rec private haltStates (input:string) (index:int) (state:string) (transitions:Map&lt;string * char, string List&gt;) =
        match index with
        | i when i = input.Length -&gt; Seq.singleton state
        | _ -&gt;
            match nextState input.[index] state transitions with
            | None -&gt; Seq.empty
            | Some states -&gt;
                states |&gt; Seq.collect (fun state -&gt;
                    haltStates input (index+1) state transitions)

    let accepts (input:string) (nfa:NondeterministicFiniteAutomaton) =
        haltStates input 0 nfa.InitialState nfa.Transitions
        |&gt; Set.ofSeq
        |&gt; Set.intersect nfa.FinalStates
        |&gt; Set.count &gt; 0
A quick look shows the only difference with your FiniteAutomaton types is that the transition either takes a string or string List.  So genericize it!

type FiniteAutomaton&lt;'a&gt; = {
    InitialState: string
    FinalStates: Set&lt;string&gt;
    Transitions: Map&lt;string * char, 'a&gt;
}
type DeterministicFiniteAutomaton = FiniteAutomaton&lt;string&gt;
type NondeterministicFiniteAutomaton = FiniteAutomaton&lt;string List&gt;


The rest pretty much falls in place:

let private nextState symbol state fa =
    fa.Transitions |&gt; Map.tryFind (state, symbol)

let rec private haltState (input:string) index state fa =
    match index with
    | i when i = input.Length -&gt; state
    | _ -&gt;
        match nextState input.[index] state fa with
        | None -&gt; null
        | Some state -&gt; haltState input (index+1) state fa

let accepts input fa =
    fa.FinalStates |&gt; Set.contains (haltState input 0 fa.InitialState fa)


I try to remove as much type annotations as possible.  Just let F#'s type inference do its magic. Also, it was convenient to pass around the fa instead of fa.Transitions.  Finally, the code compiles, but I have no idea if it works.

Edit:

If you want to be totaly generic you can do this:

type FiniteAutomaton&lt;'STATE, 'TOKEN when 'STATE:comparison and 'TOKEN:comparison&gt; = {
    InitialState: 'STATE
    FinalStates: Set&lt;'STATE&gt;
    Transitions: Map&lt;'STATE * 'TOKEN, 'STATE List&gt;
}


Also 'STATE should be a 'TOKEN List.