Haskell markov text generator
First of all, it seems like you never change the MarkovMap in your States. So, why don't you take it out of MarkovState and change the type of, say, transition, to MarkovMap -> State MarkovState Char?

Try to use more combinators and less pattern-matching. For example, the generate function is something like sequence . repeat.