Stupid regular expression engine in Haskell

regexp.hs

data NFAState = Match Char NFAState |
                MatchAll NFAState |
                Amb NFAState NFAState | Halt
              deriving Show
data Automaton = Running [Char] NFAState | Finished deriving Show

finished :: Automaton -> Bool
finished (Running _ _) = False
finished Finished      = True

runNFA :: [Char] -> NFAState -> [Automaton]
runNFA []      (Match _ _)  = []
runNFA (c1:cs) (Match c2 s) = if c1 == c2 then [Running cs s] else []
runNFA []      (MatchAll _) = []
runNFA (_:cs)  (MatchAll s) = [Running cs s]
runNFA cs      (Amb s1 s2)  = [Running cs s1, Running cs s2]
runNFA _       Halt         = [Finished]

runAutomaton (Running string state) = runNFA string state
runAutomaton (Finished) = error "can't run a finished Automaton"

stepNFAs nfas =
  let nfas' = nfas >>= runAutomaton in
    any finished nfas' ||
    case nfas' of
      [] -> False
      _  -> stepNFAs nfas'

evalNFA :: NFAState -> String -> Bool
evalNFA nfa string = stepNFAs [Running string nfa] 

data RegularExpression = Anything |
                         Literal Char |
                         Sequence RegularExpression RegularExpression |
                         Either RegularExpression RegularExpression |
                         Repeat RegularExpression
                       deriving Show
reToNFA' (Sequence r1 r2) s = reToNFA' r1 $ reToNFA' r2 s
reToNFA' (Either r1 r2)   s = Amb (reToNFA' r1 s) (reToNFA' r2 s)
reToNFA' (Repeat r)       s = let a = Amb (reToNFA' r a) s in a
reToNFA' (Literal c) s = Match c s
reToNFA' Anything    s = MatchAll s

reToNFA s = reToNFA' s Halt
evalRe re string = evalNFA (reToNFA re) string