<div>Hello,<br></div><div>A very good morning to all.</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>What the program is supposed to do is: </div><div>
======================
</div><div>It should read a description of a DFA given as a 5 tuple <font face="courier new,monospace">(q, sigma, delta, q0, </font>
<font face="courier new,monospace">finals</font><font face="courier new,monospace">)</font></div><div> where <font face="courier new,monospace"><br></font></div><ul><li>
<font face="courier new,monospace">q: a finite set of states </font>
</li><li><font face="courier new,monospace">sigma: a finite set of input symbols called the alphabet </font></li><li><font face="courier new,monospace">delta: a transition function (delta : Q × S -> Q)</font></li><li>
<font face="courier new,monospace">q0: start state (q0 belongs-to Q)</font></li><li><font face="courier new,monospace">finals: a set of accept states (F </font>
<font face="courier new,monospace">belongs-to</font> <font face="courier new,monospace">Q)</font><br></li></ul><div><div style="margin-left:40px!important">def taken from <a href="http://en.wikipedia.org/wiki/Deterministic_finite_automaton#Formal_definition" target="_blank">wikipedia</a></div>
</div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">and it should also read an input string (over alphabet <font face="courier new,monospace">sigma</font>) <br></div><div style="margin-left:0px!important">
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. </div><div style="margin-left:0px!important">
<br></div><div style="margin-left:0px!important">You can assume that '<font face="courier new,monospace">q</font>' the set of state is of integers only. Also you can assume that
<font face="courier new,monospace">sigma</font> consist only of single character English alphabets (<font face="courier new,monospace">['A'..'Z']</font>).</div><div style="margin-left:0px!important">The <font face="courier new,monospace">delta</font>
will be given as a list of 3-tuple. You don't need to do file IO.</div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">Sample input is following 2-tuple: </div><div style="margin-left:0px!important">
<font face="courier new,monospace">input = (dfa, input-string) </font></div><div style="margin-left:0px!important"><font face="courier new,monospace"> where</font></div><div style="margin-left:0px!important">
<font face="courier new,monospace"> dfa = </font><font face="courier new,monospace">([0,1], ['A','B'], [(0,'A',0), (0,'B',1), </font>
<font face="courier new,monospace">(1,'A',1), (1,'B',0)</font>
<font face="courier new,monospace"> ], 0, [1])</font></div><div style="margin-left:0px!important">
<font face="courier new,monospace"> input-string = "AAABBABBAABBBABAAAB"</font>
<font face="courier new,monospace"><br></font></div><div style="margin-left:0px!important"><font face="courier new,monospace"> </font></div><div style="margin-left:0px!important">Expected output:</div><div style="margin-left:0px!important">
<font face="courier new,monospace">output = runDFA input</font></div><div style="margin-left:0px!important"><font face="courier new,monospace">-- </font>
<font face="courier new,monospace">output = [0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1] </font>
<font face="courier new,monospace"><br></font></div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">======================</div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">
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.</div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">
How to do this using State Monad?</div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">Sorry, I may be a block-head but even after reading many tutorials on monads, I am still confused about the state monad.</div>
<div style="margin-left:0px!important">Either the tutorials give a very complicated example or they don't give a complete example that loads and runs properly in the GHCi .</div><div style="margin-left:0px!important">
Again sorry to say, but the Random number generation example given in RealWorldHaskell didn't help me either.</div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">And yes, I have read Brent Yorgey's article on Monad tutorial fallacy too.</div>
<div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">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.</div>
<div style="margin-left:0px!important">I sincerely hope that a monadic solution
(that uses <code class="code">Control.Monad.State</code>
) to the DFA problem I gave, will help me understand the working of State Monad.</div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">
Please note that I wish your solution to use the <code class="code">Control.Monad.State. </code></div><div style="margin-left:0px!important"><br></div><div style="margin-left:0px!important">Thanks in advance.<br></div><div style="margin-left:0px!important">
kak</div><div style="margin-left:0px!important"><br></div>