# New monads/MonadRandom

A simple monad transformer to allow computations in the transformed monad to generate random values.

## The code

```
{-# OPTIONS_GHC -fglasgow-exts #-}
module MonadRandom (
MonadRandom,
getRandom,
getRandomR,
evalRandomT,
evalRand,
evalRandIO,
fromList,
Rand, RandomT -- but not the data constructors
) where
import System.Random
import Control.Monad.State
import Control.Monad.Identity
class (Monad m) => MonadRandom m where
getRandom :: (Random a) => m a
getRandomR :: (Random a) => (a,a) -> m a
newtype (RandomGen g) => RandomT g m a = RandomT { unRT :: StateT g m a }
deriving (Functor, Monad, MonadTrans, MonadIO)
liftState :: (MonadState s m) => (s -> (a,s)) -> m a
liftState t = do v <- get
let (x, v') = t v
put v'
return x
instance (Monad m, RandomGen g) => MonadRandom (RandomT g m) where
getRandom = (RandomT . liftState) random
getRandomR (x,y) = (RandomT . liftState) (randomR (x,y))
evalRandomT :: (Monad m, RandomGen g) => RandomT g m a -> g -> m a
evalRandomT x g = evalStateT (unRT x) g
runRandomT :: (Monad m, RandomGen g) => RandomT g m a -> g -> m (a, g)
runRandomT x g = runStateT (unRT x) g
-- Boring random monad :)
newtype Rand g a = Rand { unRand :: RandomT g Identity a }
deriving (Functor, Monad, MonadRandom)
evalRand :: (RandomGen g) => Rand g a -> g -> a
evalRand x g = runIdentity (evalRandomT (unRand x) g)
runRand :: (RandomGen g) => Rand g a -> g -> (a, g)
runRand x g = runIdentity (runRandomT (unRand x) g)
evalRandIO :: Rand StdGen a -> IO a
evalRandIO x = getStdRandom (runIdentity . runStateT (unRT (unRand x)))
fromList :: (MonadRandom m) => [(a,Rational)] -> m a
fromList [] = error "MonadRandom.fromList called with empty list"
fromList [(x,_)] = return x
fromList xs = do let s = fromRational $ sum (map snd xs) -- total weight
cs = scanl1 (\(x,q) (y,s) -> (y, s+q)) xs -- cumulative weight
p <- liftM toRational $ getRandomR (0.0,s)
return $ fst $ head $ dropWhile (\(x,q) -> q < p) cs
```

To make use of common transformer stacks involving Rand and RandomT, the following definitions may prove useful:

```
instance (MonadRandom m) => MonadRandom (StateT s m) where
getRandom = lift getRandom
getRandomR r = lift $ getRandomR r
instance (MonadRandom m, Monoid w) => MonadRandom (WriterT w m) where
getRandom = lift getRandom
getRandomR r = lift $ getRandomR r
instance (MonadRandom m) => MonadRandom (ReaderT r m) where
getRandom = lift getRandom
getRandomR r = lift $ getRandomR r
instance (MonadState s m, RandomGen g) => MonadState s (RandomT g m) where
get = lift get
put s = lift $ put s
instance (MonadReader r m, RandomGen g) => MonadReader r (RandomT g m) where
ask = lift ask
local f m = RandomT $ local f (unRT m)
instance (MonadWriter w m, RandomGen g, Monoid w) => MonadWriter w (RandomT g m) where
tell w = lift $ tell w
listen m = RandomT $ listen (unRT m)
pass m = RandomT $ pass (unRT m)
```

You may also want a MonadRandom instance for IO:

```
instance MonadRandom IO where
getRandom = randomIO
getRandomR = randomRIO
```

## Connection to stochastics

There is some correspondence between notions in programming and in mathematics:

random generator | ~ | random variable / probabilistic experiment |

result of a random generator | ~ | outcome of a probabilistic experiment |

Thus the signature

```
rx :: (MonadRandom m, Random a) => m a
```

can be considered as "`rx`

is a random variable". In the do-notation the line

```
x <- rx
```

means that "`x`

is an outcome of `rx`

".

In a language without higher order functions and using a random
generator "function" it is not possible to work with random variables, it
is only possible to compute with outcomes, e.g. `rand()+rand()`

. In a
language where random generators are implemented as objects, computing
with random variables is possible but still cumbersome.

In Haskell we have both options either computing with outcomes

```
do x <- rx
y <- ry
return (x+y)
```

or computing with random variables

```
liftM2 (+) rx ry
```

This means that `liftM`

like functions convert ordinary arithmetic into
random variable arithmetic. But there is also some arithmetic on random
variables which can not be performed on outcomes. For example, given a
function that repeats an action until the result fulfills a certain
property (I wonder if there is already something of this kind in the
standard libraries)

```
untilM :: Monad m => (a -> Bool) -> m a -> m a
untilM p m =
do x <- m
if p x then return x else untilM p m
```

we can suppress certain outcomes of an experiment. E.g. if

```
getRandomR (-10,10)
```

is a uniformly distributed random variable between -10 and 10, then

```
untilM (0/=) (getRandomR (-10,10))
```

is a random variable with a uniform distribution of .