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