New monads/MonadRandom

From HaskellWiki

(Difference between revisions)

Revision as of 00:02, 4 December 2006

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

1 The code

{-# OPTIONS_GHC -fglasgow-exts #-}
 
module MonadRandom (
    MonadRandom,
    getRandom,
    getRandomR,
    getRandoms,
    getRandomRs,
    evalRandomT,
    evalRand,
    evalRandIO,
    fromList,
    Rand, RandomT -- but not the data constructors
    ) where
 
import System.Random
import Control.Monad.State
import Control.Monad.Identity
import Control.Arrow
 
class (Monad m) => MonadRandom m where
    getRandom :: (Random a) => m a
    getRandoms :: (Random a) => m [a]
    getRandomR :: (Random a) => (a,a) -> m a
    getRandomRs :: (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
    getRandoms = RandomT . liftState $ first randoms . split
    getRandomR (x,y) = RandomT . liftState $ randomR (x,y)
    getRandomRs (x,y) = RandomT . liftState $
                            first (randomRs (x,y)) . split
 
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

2 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 $\{-10, \dots, -1, 1, \dots, 10\}$ .

3 See also

Arbitrary
type class of Quickcheck
http://www.haskell.org/pipermail/haskell-cafe/2005-May/009775.html
New monads/MonadRandomSplittable

Retrieved from "http://www.haskell.org/haskellwiki/New_monads/MonadRandom"

Categories: Code | Mathematics

Personal tools

Views