Hello,

A very good morning to all.

I am a Haskell beginner. And although I have written fairly complicated programs and have understood to some extent the concepts like pattern matching, folds, scans, list comprehensions, but I have not satisfactorily understood the concept of Monads yet. I have partially understood and used the Writer, List and Maybe monads but the State monad completely baffles me.

I wanted to write a  program for the following problem: A DFA simulator. This I guess is a right candidate for State monad as it mainly deals with state changes.

What the program is supposed to do is:

======================

It should read a description of a DFA given as a 5 tuple (q, sigma, delta, q0, finals)

   where 

and it should also read an input string (over alphabet sigma) 

and then it should run the input string on the DFA which it should build from the given description and should output (produce) a list of states through which the DFA has passed as it consumed the input string. 

You can assume that 'q' the set of state is of integers only. Also you can assume that sigma consist only of single character English alphabets (['A'..'Z']).

The  delta will be given as a list of 3-tuple. You don't need to do file IO.

Sample input is following 2-tuple: 

input = (dfa, input-string) 

   dfa = ([0,1], ['A','B'], [(0,'A',0), (0,'B',1),  (1,'A',1), (1,'B',0)  ], 0, [1])

   input-string = "AAABBABBAABBBABAAAB"

Expected output:

output = runDFA input

--  output = [0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1] 

======================

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.

How to do this using State Monad?

Sorry, I may be a block-head but even after reading many tutorials on monads, I am still confused about the state monad.

Either the tutorials give a very complicated example or they don't give a complete example that loads and runs properly in the GHCi .

Again sorry to say, but the Random number generation example given in RealWorldHaskell didn't help me either.

And yes, I have read Brent Yorgey's article on Monad tutorial fallacy too.

So, you Monad gurus over here can consider me a block-head, but let me assure you people that I am a sincere person trying to learn this beautiful but difficult concept.

I sincerely hope that a monadic solution (that uses  Control.Monad.State  ) to the DFA problem I gave, will help me understand the working of State Monad.

Please note that I wish your solution to use the Control.Monad.State. 

Thanks in advance.

kak