Hi all, I just wrote some nice code: A finite state machine with monadic state, allowing both DFAs and NFAs to be expressed with the same functions. I've only used it in [], Set, and Maybe, but I think it would be interesting in several others (a probability monad comes to mind). Also, if anyone has any sensible interpretation of this in the continuation monad, let me know. import Control.Monad import Data.Maybe 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 :: (MonadPlus m) => Map State (Map Char (m State)) -> State -> (String -> m State) toFSM transMap q0 = foldM (transition transMap) q0 egMachine = toFSM [("p", [ ('0', ["p"]) , ('1', ["p", "q"])])] "p"