<table cellspacing="0" cellpadding="0" border="0" ><tr><td valign="top" style="font: inherit;">I've been playing around with State Monads. Two I looked at earlier used *sequence* and *replicate* but when I came to this one I found myself puzzling over how to structure the problem when there was no predetermined count of how many times to thread the state.<br><br>============== Program 1 ============= <br><br>import Control.Monad<br>import Control.Monad.State<br><br>type GeneratorState = State (Int, Int)<br><br>-- lcf (largest common factor)<br>-- lcf :: (Int, Int) -&gt; ((Int, Int), Int)<br>lcf (x, y)<br>&nbsp; | x == y&nbsp;&nbsp;&nbsp; = ((x, y), x)<br>&nbsp; | x &lt; y&nbsp;&nbsp;&nbsp;&nbsp; = ((y, x), 0)<br>&nbsp; | otherwise = ((y, x-y), 0)<br><br>lcfstate :: GeneratorState Int<br>lcfstate = State (\st -&gt; lcf st)<br><br>============== Some output =========<br><br>{-<br>*Main&gt; runState lcfstate (24,18)<br>(0,(18,6))<br>*Main&gt; runState
 lcfstate (18,6)<br>(0,(6,12))<br>*Main&gt; runState lcfstate (6,12)<br>(0,(12,6))<br>*Main&gt; runState lcfstate (12,6)<br>(0,(6,6))<br>*Main&gt; runState lcfstate (6,6)<br>(6,(6,6))<br>*Main&gt; runState (sequence $ replicate 5 lcfstate) (24,18)<br>([0,0,0,0,6],(6,6))<br>-}<br><br>{-<br>*Main&gt; evalState (sequence $ replicate 2 lcfstate) (24,18)<br>[0,0]<br>*Main&gt; evalState (sequence $ replicate 3 lcfstate) (24,18)<br>[0,0,0]<br>*Main&gt; evalState (sequence $ replicate 4 lcfstate) (24,18)<br>[0,0,0,0]<br>*Main&gt; evalState (sequence $ replicate 5 lcfstate) (24,18)<br>[0,0,0,0,6]<br>-}<br><br>===================================<br><br>Then I saw the same problem solved here<br><br>http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm<br><br>============== Program 2 =============<br><br>import Control.Monad<br>import Control.Monad.ST<br><br>newtype StateTrans s a = ST( s -&gt; (s, a) )<br><br>instance Monad (StateTrans s)<br>&nbsp;
 where<br>&nbsp;&nbsp;&nbsp; -- (&gt;&gt;=) :: StateTrans s a -&gt; (a -&gt; StateTrans s b) -&gt; StateTrans s b<br>&nbsp;&nbsp;&nbsp; (ST p) &gt;&gt;= k&nbsp; =&nbsp; ST( \s0 -&gt; let (s1, a) = p s0<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (ST q) = k a<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; in q s1 )<br>&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp;<br>&nbsp;&nbsp;&nbsp; -- return :: a -&gt; StateTrans s a<br>&nbsp;&nbsp;&nbsp; return a = ST( \s -&gt; (s, a) )<br><br>applyST :: StateTrans s a -&gt; s -&gt; (s, a)<br>applyST (ST p) s = p s<br><br>type ImpState = (Int,
 Int)<br><br>getX, getY :: StateTrans ImpState Int<br>getX = ST(\(x,y)-&gt; ((x,y), x))<br>getY = ST(\(x,y)-&gt; ((x,y), y))<br><br>putX, putY :: Int -&gt; StateTrans ImpState ()<br>putX x' = ST(\(x,y)-&gt;((x',y),()))<br>putY y' = ST(\(x,y)-&gt;((x,y'),()))<br><br>gcdST :: StateTrans ImpState Int<br>gcdST = do x &lt;- getX<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; y &lt;- getY<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (if x == y<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; then<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return x<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else if x &lt; y<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; then <br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; do putY
 (y-x)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; gcdST<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; else<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; do putX (x-y)<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; gcdST)<br><br>greatestCommonDivisor x y = snd( applyST gcdST (x,y) )<br><br>============== Some output =========<br><br>{-<br>*Main&gt; greatestCommonDivisor 24 18<br>6-}<br><br>====================================<br><br>Very impressive. Is this solution typical for problems where the number of times the state must be threaded is dependent on the state itself? <br><br>Michael<br><br></td></tr></table><br>