Pithy finite state machine in haskell

gistfile1.hs

import Control.Monad
import Data.Maybe
import Prelude hiding (any, elem)
import Data.Foldable

type State = String
type Map a b = [(a, b)]

-- In Map State (Map Char (m State)), the monad m determines the kind of FSM that is being run.
-- If m = [] (or Set), these functions work as a NFA. If m = Maybe, we essentially have a DFA.

transition :: (MonadPlus m) => Map State (Map Char (m State)) -> State -> Char -> m State
transition transMap q c = fromMaybe mzero $ lookup q transMap >>= lookup c

toFSM :: (Foldable m, MonadPlus m) => Map State (Map Char (m State)) -> State -> [State] -> (String -> Bool) 
toFSM transMap q0 accepts = any (`elem` accepts) . foldM (transition transMap) q0

-- An NFA that accepts boolean strings ending in '1'
egMachine :: String -> Bool
egMachine = toFSM [("p", [ ('0', ["p"])
                         , ('1', ["p", "q"])])]
                  "p"
                  ["q"]