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.

============== Program 1 =============

import Control.Monad
import Control.Monad.State

type GeneratorState = State (Int, Int)

-- lcf (largest common factor)
-- lcf :: (Int, Int) -> ((Int, Int), Int)
lcf (x, y)
  | x == y    = ((x, y), x)
  | x < y     = ((y, x), 0)
  | otherwise = ((y, x-y), 0)

lcfstate :: GeneratorState Int
lcfstate = State (\st -> lcf st)

============== Some output =========

{-
*Main> runState lcfstate (24,18)
(0,(18,6))
*Main> runState lcfstate (18,6)
(0,(6,12))
*Main> runState lcfstate (6,12)
(0,(12,6))
*Main> runState lcfstate (12,6)
(0,(6,6))
*Main> runState lcfstate (6,6)
(6,(6,6))
*Main> runState (sequence $ replicate 5 lcfstate) (24,18)
([0,0,0,0,6],(6,6))
-}

{-
*Main> evalState (sequence $ replicate 2 lcfstate) (24,18)
[0,0]
*Main> evalState (sequence $ replicate 3 lcfstate) (24,18)
[0,0,0]
*Main> evalState (sequence $ replicate 4 lcfstate) (24,18)
[0,0,0,0]
*Main> evalState (sequence $ replicate 5 lcfstate) (24,18)
[0,0,0,0,6]
-}

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

Then I saw the same problem solved here

http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm

============== Program 2 =============

import Control.Monad
import Control.Monad.ST

newtype StateTrans s a = ST( s -> (s, a) )

instance Monad (StateTrans s)
  where
    -- (>>=) :: StateTrans s a -> (a -> StateTrans s b) -> StateTrans s b
    (ST p) >>= k  =  ST( \s0 -> let (s1, a) = p s0
                                    (ST q) = k a
                                in q s1 )
                        
    -- return :: a -> StateTrans s a
    return a = ST( \s -> (s, a) )

applyST :: StateTrans s a -> s -> (s, a)
applyST (ST p) s = p s

type ImpState = (Int, Int)

getX, getY :: StateTrans ImpState Int
getX = ST(\(x,y)-> ((x,y), x))
getY = ST(\(x,y)-> ((x,y), y))

putX, putY :: Int -> StateTrans ImpState ()
putX x' = ST(\(x,y)->((x',y),()))
putY y' = ST(\(x,y)->((x,y'),()))

gcdST :: StateTrans ImpState Int
gcdST = do x <- getX
           y <- getY
           (if x == y
            then
                 return x
            else if x < y
            then
                 do putY (y-x)
                    gcdST
            else
                 do putX (x-y)
                    gcdST)

greatestCommonDivisor x y = snd( applyST gcdST (x,y) )

============== Some output =========

{-
*Main> greatestCommonDivisor 24 18
6-}

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

Very impressive. Is this solution typical for problems where the number of times the state must be threaded is dependent on the state itself?

Michael