DFA and NFA simulators

gistfile1.hs

import Data.Map as M hiding (map)
import Data.Set as S hiding (map)
import Data.Maybe (catMaybes)

type State = Int
type Input = Char

data DFA = DFA { getEdges           :: Map (State, Input) State
               , getAcceptingStates :: Set State
               }

type DFAState = (DFA, State)

fsmsim :: [Input] -> DFAState -> Bool
fsmsim [] ((DFA _ accepting), currentState) = currentState `S.member` accepting
fsmsim (input:rest) (dfa@(DFA edges accepting), currentState) =
    case M.lookup (currentState, input) edges of
        Just ns -> fsmsim rest (dfa, ns)
        Nothing -> False

data NFA = NFA { getNFAEdges           :: Map (State, Input) [State]
               , getNFAAcceptingStates :: Set State
               }

type NFAState = (NFA, Set State)

nfasim :: [Input] -> NFAState -> Bool
nfasim [] ((NFA _ acceptingStates), currentStates) =
    any (`S.member` acceptingStates) (S.elems currentStates)
nfasim (input:rest) (nfa@(NFA edges acceptings), currentStates) =
    let newStates = S.fromList $ concat $ catMaybes $
                        map (\s -> M.lookup (s, input) edges) $
                        S.elems currentStates
    in if S.size newStates == 0
         then False
         else nfasim rest (nfa, newStates)