Difference between revisions of "New monads/MonadRandom"
(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 donotation 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/haskellcafe/2005May/009775.html 
Revision as of 16:27, 15 November 2006
MonadRandom
A simple monad transformer to allow computations in the transformed monad to generate random values.
{# OPTIONS_GHC fglasgowexts #}
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 donotation 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 .
Cf.:

Arbitrary
type class of QuickCheck  http://www.haskell.org/pipermail/haskellcafe/2005May/009775.html