Creating monads analoguous to the IO Monad with chained state

Question

Hello folks,

I'm pretty new to Haskell again this year (after using it in the early 1990s and then again in the early 00's). I'm trying to write some code that uses a pattern that is almost directly analoguous to the example IO monad shown on the Haskell Wiki:

type IO a  =  RealWorld -> (a, RealWorld)

(Yes, I know this isn't the GHC implementation of IO, but merely a vehicle for understanding it.) The reason is, in my application (a game), I now have two patterns doing this with two different substitutions of the RealWorld here. In one, it's the state of the game, and in the other, it's just a StdGen random number seed. I of course now have two pairs of types like this:

-- | Easily return a specified value as well as the new random number generator
type ReturnRNG a = (a, StdGen)

-- | Take an RNG and return it and another value.
-- (This is basically like the IO type but with the StdGen instead of RealWorld.)
type WithRNG a = StdGen -> ReturnRNG a

-- | Easily return a specified value as well as the new GameState
type ReturnGS a = (a, GameState)

-- | Use a GameState and return a value with the updated GameState.
-- (This is like IO.)
type WithGS a = GameState -> ReturnGS a

(Yes, I could abstract them into one pair with two parameters but I haven't gotten around to it.) You can see, of course, that my WithGS a and WithRNG a types (type synonyms) are exactly analogous to IO a above.

So, here's a simple example of actual working code that I now have:

-- | Returns a random position for the given size.
randomPos :: (Int, Int)          -- ^ The size
          -> WithRNG (Int, Int)  -- ^ The result (0 up to 1 less than the size) and new RNG seed
randomPos (w, h) r0 = ((x, y), r2)
  where
    (x, r1) = randomR (0, w - 1) r0
    (y, r2) = randomR (0, h - 1) r1

This creates a random pair in a specified range, and returns the final RNG seed. A large percentage of my methods are like this (using WithRNG or WithGS), using a chained state, sometimes even getting up to r4 or r6 (or gs4, etc.). I'd rather write this example to look like this...

-- (Not working example)
randomPosSt (w, h) = do
    x <- randomR (0, w - 1)
    y <- randomR (0, h - 1)
    return (x, y)

...yet have the exact same method signature and semantics. This seems like it should be possible following the aforementioned tutorial which gives this example:

(>>=) :: IO a -> (a -> IO b) -> IO b
(action1 >>= action2) world0 =
   let (a, world1) = action1 world0
       (b, world2) = action2 a world1
   in (b, world2)

This, as you can see, is almost exactly what I'm doing above (once you substitute "let" for "where" notation).

However, I cannot create a Monad out of a type synonym. (I've tried TypeSynonymInstances but it doesn't seem to work with either "instance Monad WithRNG where" or using a parameter. Using a newtype would also seem to add useless ugly syntax.) I haven't been able to figure out the State Monad well enough to make an equivalent method using that either. Even if I had succeeded, however, the State Monad implementation would seem to use ugly "get" and "put"s (and "runState"s etc.) and make the code less readable, not more.

-- THIS DOES NOT WORK
-- | Make a State Monad with random number generator - like WithRNG above
type RandomState = State StdGen

-- | Returns a random position for the given size.
randomPosSt :: (Int, Int)                  -- ^ The size
            -> RandomState (Int, Int)  -- ^ The result (0 up to 1 less than the size) and new RNG seed

After all this, I've concluded that I'm either doing something wrong, misunderstanding something, or just can't do what I want to do. I was just about to say "well, you don't really need to figure out how to modify your code to make the state carried through to be handled automatically, as it works just fine" and give up and then I thought I'd ask here (my debut delurking). I would prefer a more elegant solution.

I also figure a more elegant solution would give me this function I use "for free:"

-- | Maps the specified method, which must take a RNG as the last parameter,
-- over all the elements of the list, propagating the RNG and returning it.
-- TODO: Implement this without using recursion? Using a fold?
mapRandom :: (a -> WithRNG b) -- ^ The function to map (that takes a RNG)
          -> [a] -- ^ The input list
          -> WithRNG [b] -- ^ The RNG to return
mapRandom func [] r0 = ([], r0)
mapRandom func (x:xs) r0 = (mapped : rest, r2)
  where
    (mapped, r1) = func x r0
    (rest, r2)   = mapRandom func xs r1

Thanks for any thoughts, suggestions, references and your time!

Answer 1

You can use the State monad without using get or put. Just wrap your state passing functions directly in the State newtype:

import System.Random

newtype State s a = State { runState :: s -> (a, s) }

instance Monad (State s) where
    return a = State (\s -> (a, s))

    m >>= f = State (\s0 ->
        let (a, s1) = runState m s0
        in  runState (f a) s1 )

randomPos :: (Int, Int) -> State StdGen (Int, Int)
randomPos (w, h) = do
    x <- State $ randomR (0, w - 1)
    y <- State $ randomR (0, h - 1)
    return (x, y)

The trick is to observe the type of the State constructor:

State :: (s -> (a, s)) -> State s a

.. and randomR (lo, hi) has just the right type to be wrapped directly within State:

randomR (1, 6)          :: StdGen -> (Int, StdGen)
StateT $ randomR (1, 6) :: State StdGen Int

The State constructor takes a state passing function and creates a suitable value for use within a State monad. Then when you are done using the monad you can convert the monad back to the equivalent state-passing function using runState:

runState :: State s a -> (s -> (a, s))

runState (randomPos (5, 6)) :: StdGen -> ((Int, Int), StdGen)

This is in fact how RandT works, by wrapping all the generator-passing random functions in a state monad, and RandT is equivalent to StateT StdGen under the hood.

Also, like you said, the monadic formulation would give you the mapped version for free:

mapRandom
    :: ( a  -> (StdGen -> ( b , StdGen)))
    -> ([a] -> (StdGen -> ([b], StdGen)))
mapRandom f xs = runState $ mapM (State . f) xs

This is because the type of mapM (when specialized to State) is:

mapM :: (a -> State s b) -> [a] -> State s [b]

So all the above mapRandom function does is wrap the input in a State newtype, use mapM, and then unwrap it.