<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) -> ((Int, Int), Int)<br>lcf (x, y)<br> | x == y = ((x, y), x)<br> | x < y = ((y, x), 0)<br> | otherwise = ((y, x-y), 0)<br><br>lcfstate :: GeneratorState Int<br>lcfstate = State (\st -> lcf st)<br><br>============== Some output =========<br><br>{-<br>*Main> runState lcfstate (24,18)<br>(0,(18,6))<br>*Main> runState
lcfstate (18,6)<br>(0,(6,12))<br>*Main> runState lcfstate (6,12)<br>(0,(12,6))<br>*Main> runState lcfstate (12,6)<br>(0,(6,6))<br>*Main> runState lcfstate (6,6)<br>(6,(6,6))<br>*Main> runState (sequence $ replicate 5 lcfstate) (24,18)<br>([0,0,0,0,6],(6,6))<br>-}<br><br>{-<br>*Main> evalState (sequence $ replicate 2 lcfstate) (24,18)<br>[0,0]<br>*Main> evalState (sequence $ replicate 3 lcfstate) (24,18)<br>[0,0,0]<br>*Main> evalState (sequence $ replicate 4 lcfstate) (24,18)<br>[0,0,0,0]<br>*Main> 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 -> (s, a) )<br><br>instance Monad (StateTrans s)<br>
where<br> -- (>>=) :: StateTrans s a -> (a -> StateTrans s b) -> StateTrans s b<br> (ST p) >>= k = ST( \s0 -> let (s1, a) = p s0<br> (ST q) = k a<br> in q s1 )<br> <br> -- return :: a -> StateTrans s a<br> return a = ST( \s -> (s, a) )<br><br>applyST :: StateTrans s a -> s -> (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)-> ((x,y), x))<br>getY = ST(\(x,y)-> ((x,y), y))<br><br>putX, putY :: Int -> StateTrans ImpState ()<br>putX x' = ST(\(x,y)->((x',y),()))<br>putY y' = ST(\(x,y)->((x,y'),()))<br><br>gcdST :: StateTrans ImpState Int<br>gcdST = do x <- getX<br> y <- getY<br> (if x == y<br> then<br> return x<br> else if x < y<br> then <br> do putY
(y-x)<br> gcdST<br> else<br> do putX (x-y)<br> gcdST)<br><br>greatestCommonDivisor x y = snd( applyST gcdST (x,y) )<br><br>============== Some output =========<br><br>{-<br>*Main> 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>