NFA and DFA implementation

Question

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<string>
 Transitions: Map<string * char, string>
 }
 let private nextState (symbol:char) (state:string) (transitions:Map<string * char, string>) =
 transitions |> Map.tryFind (state, symbol)
 let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string>) =
 match index with
 | i when i = input.Length -> state
 | _ ->
 match nextState input.[index] state transitions with
 | None -> null
 | Some state -> haltState input (index+1) state transitions
 let accepts (input:string) (dfa:DeterministicFiniteAutomaton) =
 dfa.FinalStates |> Set.contains (haltState input 0 dfa.InitialState dfa.Transitions)
module NFA =
 type NondeterministicFiniteAutomaton = {
 InitialState: string
 FinalStates: Set<string>
 Transitions: Map<string * char, string List>
 }
 let private nextState (symbol:char) (state:string) (transitions:Map<string * char, string List>) =
 transitions |> Map.tryFind (state, symbol)
 let rec private haltStates (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
 match index with
 | i when i = input.Length -> Seq.singleton state
 | _ ->
 match nextState input.[index] state transitions with
 | None -> Seq.empty
 | Some states ->
 states |> Seq.collect (fun state ->
 haltStates input (index+1) state transitions)
 let accepts (input:string) (nfa:NondeterministicFiniteAutomaton) =
 haltStates input 0 nfa.InitialState nfa.Transitions
 |> Set.ofSeq
 |> Set.intersect nfa.FinalStates
 |> Set.count > 0

Answer 1

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<'a> = {
 InitialState: string
 FinalStates: Set<string>
 Transitions: Map<string * char, 'a>
}
type DeterministicFiniteAutomaton = FiniteAutomaton<string>
type NondeterministicFiniteAutomaton = FiniteAutomaton<string List>

The rest pretty much falls in place:

let private nextState symbol state fa =
 fa.Transitions |> Map.tryFind (state, symbol)
let rec private haltState (input:string) index state fa =
 match index with
 | i when i = input.Length -> state
 | _ ->
 match nextState input.[index] state fa with
 | None -> null
 | Some state -> haltState input (index+1) state fa
let accepts input fa =
 fa.FinalStates |> 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<'STATE, 'TOKEN when 'STATE:comparison and 'TOKEN:comparison> = {
 InitialState: 'STATE
 FinalStates: Set<'STATE>
 Transitions: Map<'STATE * 'TOKEN, 'STATE List>
}

Also 'STATE should be a 'TOKEN List.

• Gabriel: Your code looks nice, but there is a problem: let private nextState symbol state fa wants a string for parameter state, so it will infer that 'a is string in haltState and accepts too. Even if I put some type annotations in haltState and accepts, the nextState function will infer string for state.
• Gabriel: See: gist.github.com/ihavenonickname/…
• Gabriel: Say me what do you think about my idea: Keep only the code of my old NFA module, and when it is a DFA then all keys in Transitions map will all point to lists with 1 element each (thus it's deterministic).
• Ray: Yes, a one element list would work for deterministic FA. Also you can get extra generic. See above.