# New monads/MonadRandom

### From HaskellWiki

(Add instance MonadRandom IO) |
(connection to stochastics) |
||

Line 1: | Line 1: | ||

[[Category:Code]] | [[Category:Code]] | ||

+ | [[Category:Mathematics]] | ||

+ | |||

= MonadRandom = | = MonadRandom = | ||

Line 104: | Line 106: | ||

getRandomR = randomRIO | getRandomR = randomRIO | ||

</haskell> | </haskell> | ||

+ | |||

+ | |||

+ | == 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 | ||

+ | <haskell>rx :: (MonadRandom m, Random a) => m a</haskell> | ||

+ | can be considered as "<hask>rx</hask> is a random variable". In the do-notation the line | ||

+ | <haskell>x <- rx</haskell> | ||

+ | means that "<hask>x</hask> is an outcome of <hask>rx</hask>". | ||

+ | |||

+ | 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. <code>rand()+rand()</code>. 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 | ||

+ | <haskell> | ||

+ | do x <- rx | ||

+ | y <- ry | ||

+ | return (x+y) | ||

+ | </haskell> | ||

+ | or computing with random variables | ||

+ | <haskell> | ||

+ | liftM2 (+) rx ry | ||

+ | </haskell> | ||

+ | |||

+ | This means that <hask>liftM</hask> 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) | ||

+ | <haskell> | ||

+ | 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 | ||

+ | </haskell> | ||

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

+ | <haskell> | ||

+ | getRandomR (-10,10) | ||

+ | </haskell> | ||

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

+ | <haskell> | ||

+ | untilM (0/=) (getRandomR (-10,10)) | ||

+ | </haskell> | ||

+ | is a random variable with a uniform distribution of <math>\{-10, \dots, -1, 1, \dots, 10\}</math>. | ||

+ | |||

+ | |||

+ | Cf.: | ||

+ | * <hask>Arbitrary</hask> type class of [[QuickCheck]] | ||

+ | * http://www.haskell.org/pipermail/haskell-cafe/2005-May/009775.html |

## Revision as of 16:27, 15 November 2006

# 1 MonadRandom

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

{-# 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

## 1.1 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

`x <- 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

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 .

Cf.:

- type class of QuickCheckArbitrary
- http://www.haskell.org/pipermail/haskell-cafe/2005-May/009775.html