2
\$\begingroup\$

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
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ 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. \$\endgroup\$
    – Gabriel
    May 10, 2016 at 12:15
  • \$\begingroup\$ See: gist.github.com/ihavenonickname/… \$\endgroup\$
    – Gabriel
    May 10, 2016 at 12:20
  • \$\begingroup\$ 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). \$\endgroup\$
    – Gabriel
    May 10, 2016 at 12:37
  • \$\begingroup\$ Yes, a one element list would work for deterministic FA. Also you can get extra generic. See above. \$\endgroup\$
    – Ray
    May 10, 2016 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.