[Haskell-beginners] How to solve this using State Monad?

[kak dod]

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

   - q: a finite set of states
   - sigma: a finite set of input symbols called the alphabet
   - delta: a transition function (delta : Q × S -> Q)
   - q0: start state (q0 belongs-to Q)
   - finals: a set of accept states (F belongs-to Q)

def taken from wikipedia<http://en.wikipedia.org/wiki/Deterministic_finite_automaton#Formal_definition>

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)
  where
   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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120529/f3fa1630/attachment-0001.htm>