2 line finite (monadic) state machine

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"

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org