I wrote a recursive program to do this without using any monads. I simply send the entire dfa, the input string and its partial result in the recursive calls.