Data.Random
Contents
Description
Flexible modeling and sampling of random variables.
The central abstraction in this library is the concept of a random variable. It is not fully formalized in the standard measure-theoretic language, but rather is informally defined as a "thing you can get random values out of". Different random variables may have different types of values they can return or the same types but different probabilities for each value they can return. The random values you get out of them are traditionally called "random variates".
Most imperative-language random number libraries are all about obtaining and manipulating random variates. This one is about defining, manipulating and sampling random variables. Computationally, the distinction is small and mostly just a matter of perspective, but from a program design perspective it provides both a powerfully composable abstraction and a very useful separation of concerns.
Abstract random variables as implemented by RVar are composable. They can
be defined in a monadic / "imperative" style that amounts to manipulating
variates, but with strict type-level isolation. Concrete random variables
are also provided, but they do not compose as generically. The Distribution
type class allows concrete random variables to "forget" their concreteness
so that they can be composed. For examples of both, see the documentation
for RVar and Distribution, as well as the code for any of the concrete
distributions such as Uniform, Gamma, etc.
Both abstract and concrete random variables can be sampled (despite the types GHCi may list for the functions) by the functions in Data.Random.Sample.
Random variable sampling is done with regard to a generic basis of primitive
random variables defined in Data.Random.Internal.Primitives. This basis
is very low-level and the actual set of primitives is still fairly experimental,
which is why it is in the "Internal" sub-heirarchy. User-defined variables
should use the existing high-level variables such as Uniform and Normal
rather than these basis variables. Data.Random.Source defines classes for
entropy sources that provide implementations of these primitive variables.
Several implementations are available in the Data.Random.Source.* modules.
- type RVar = RVarT Identity
- data RVarT m a
- runRVar :: RandomSource m s => RVar a -> s -> m a
- runRVarT :: (Lift n m, RandomSource m s) => RVarT n a -> s -> m a
- runRVarTWith :: RandomSource m s => (forall t. n t -> m t) -> RVarT n a -> s -> m a
- class Distribution d t where
- class Distribution d t => CDF d t where
- class Sampleable d m t where
- sampleFrom :: RandomSource m s => s -> d t -> m t
- sample :: (Sampleable d m t, MonadRandom m) => d t -> m t
- sampleState :: (Sampleable d (State s) t, MonadRandom (State s)) => d t -> s -> (t, s)
- sampleStateT :: (Sampleable d (StateT s m) t, MonadRandom (StateT s m)) => d t -> s -> m (t, s)
- data Uniform t = Uniform !t !t
- uniform :: Distribution Uniform a => a -> a -> RVar a
- data StdUniform t = StdUniform
- stdUniform :: Distribution StdUniform a => RVar a
- data Normal a
- normal :: Distribution Normal a => a -> a -> RVar a
- stdNormal :: Distribution Normal a => RVar a
- data Gamma a = Gamma a a
- gamma :: Distribution Gamma a => a -> a -> RVar a
- class Monad m => MonadRandom m
- class Monad m => RandomSource m s
- data StdRandom = StdRandom
- randomElement :: [a] -> RVar a
- shuffle :: [a] -> RVar [a]
- shuffleN :: Int -> [a] -> RVar [a]
- shuffleNofM :: Int -> Int -> [a] -> RVar [a]
Random variables
Abstract (RVar)
type RVar = RVarT IdentitySource
An opaque type modeling a "random variable" - a value
which depends on the outcome of some random event. RVars
can be conveniently defined by an imperative-looking style:
normalPair = do
u <- stdUniform
t <- stdUniform
let r = sqrt (-2 * log u)
theta = (2 * pi) * t
x = r * cos theta
y = r * sin theta
return (x,y)
OR by a more applicative style:
logNormal = exp <$> stdNormal
Once defined (in any style), there are a couple ways to sample RVars:
- In a monad, using a
RandomSource:
sampleFrom DevRandom (uniform 1 100) :: IO Int
- As a pure function transforming a functional RNG:
sampleState (uniform 1 100) :: StdGen -> (Int, StdGen)
A random variable with access to operations in an underlying monad. Useful examples include any form of state for implementing random processes with hysteresis, or writer monads for implementing tracing of complicated algorithms.
For example, a simple random walk can be implemented as an RVarT IO value:
rwalkIO :: IO (RVarT IO Double)
rwalkIO d = do
lastVal <- newIORef 0
let x = do
prev <- lift (readIORef lastVal)
change <- rvarT StdNormal
let new = prev + change
lift (writeIORef lastVal new)
return new
return x
To run the random walk, it must first be initialized, and then it can be sampled as usual:
do
rw <- rwalkIO
x <- sampleFrom DevURandom rw
y <- sampleFrom DevURandom rw
...
The same random-walk process as above can be implemented using MTL types
as follows (using import Control.Monad.Trans as MTL):
rwalkState :: RVarT (State Double) Double
rwalkState = do
prev <- MTL.lift get
change <- rvarT StdNormal
let new = prev + change
MTL.lift (put new)
return new
Invocation is straightforward (although a bit noisy) if you're used
to MTL, but there is a gotcha lurking here: sample and runRVarT
inherit the extreme generality of lift, so there will almost always
need to be an explicit type signature lurking somewhere in any client
code making use of RVarT with MTL types. In this example, the
inferred type of start would be too general to be practical, so the
signature for rwalk explicitly fixes it to Double. Alternatively,
in this case sample could be replaced with
\x -> runRVarTWith MTL.lift x StdRandom.
rwalk :: Int -> Double -> StdGen -> ([Double], StdGen) rwalk count start gen = evalState (runStateT (sample (replicateM count rwalkState)) gen) start
Instances
| MonadTrans RVarT | |
| Monad (RVarT n) | |
| Functor (RVarT n) | |
| Applicative (RVarT n) | |
| MonadIO m => MonadIO (RVarT m) | |
| MonadRandom (RVarT n) | |
| Lift m n => Sampleable (RVarT m) n t | |
| Lift (RVarT Identity) (RVarT m) |
runRVar :: RandomSource m s => RVar a -> s -> m aSource
"Run" an RVar - samples the random variable from the provided
source of entropy.
runRVarT :: (Lift n m, RandomSource m s) => RVarT n a -> s -> m aSource
"Runs" an RVarT, sampling the random variable it defines.
The Lift context allows random variables to be defined using a minimal
underlying functor (Identity is sufficient for "conventional" random
variables) and then sampled in any monad into which the underlying functor
can be embedded (which, for Identity, is all monads).
The lifting is very important - without it, every RVar would have
to either be given access to the full capability of the monad in which it
will eventually be sampled (which, incidentally, would also have to be
monomorphic so you couldn't sample one RVar in more than one monad)
or functions manipulating RVars would have to use higher-ranked
types to enforce the same kind of isolation and polymorphism.
For non-standard liftings or those where you would rather not introduce a
Lift instance, see runRVarTWith.
runRVarTWith :: RandomSource m s => (forall t. n t -> m t) -> RVarT n a -> s -> m aSource
Like runRVarT but allowing a user-specified lift operation. This
operation must obey the "monad transformer" laws:
lift . return = return lift (x >>= f) = (lift x) >>= (lift . f)
One example of a useful non-standard lifting would be one that takes State s to
another monad with a different state representation (such as IO with the
state mapped to an IORef):
embedState :: (Monad m) => m s -> (s -> m ()) -> State s a -> m a
embedState get put = \m -> do
s <- get
(res,s) <- return (runState m s)
put s
return res
Concrete (Distribution)
class Distribution d t whereSource
A Distribution is a data representation of a random variable's probability
structure. For example, in Data.Random.Distribution.Normal, the Normal
distribution is defined as:
data Normal a
= StdNormal
| Normal a a
Where the two parameters of the Normal data constructor are the mean and
standard deviation of the random variable, respectively. To make use of
the Normal type, one can convert it to an rvar and manipulate it or
sample it directly:
x <- sample (rvar (Normal 10 2)) x <- sample (Normal 10 2)
A Distribution is typically more transparent than an RVar
but less composable (precisely because of that transparency). There are
several practical uses for types implementing Distribution:
- Typically, a
Distributionwill expose several parameters of a standard mathematical model of a probability distribution, such as mean and std deviation for the normal distribution. Thus, they can be manipulated analytically using mathematical insights about the distributions they represent. For example, a collection of bernoulli variables could be simplified into a (hopefully) smaller collection of binomial variables. - Because they are generally just containers for parameters, they can be easily serialized to persistent storage or read from user-supplied configurations (eg, initialization data for a simulation).
- If a type additionally implements the
CDFsubclass, which extendsDistributionwith a cumulative density function, an arbitrary random variablexcan be tested against the distribution by testingfmap (cdf dist) xfor uniformity.
On the other hand, most Distributions will not be closed under all the
same operations as RVar (which, being a monad, has a fully turing-complete
internal computational model). The sum of two uniformly-distributed
variables, for example, is not uniformly distributed. To support general
composition, the Distribution class defines a function rvar to
construct the more-abstract and more-composable RVar representation
of a random variable.
Methods
Return a random variable with this distribution.
Instances
class Distribution d t => CDF d t whereSource
Methods
cdf :: d t -> t -> DoubleSource
Return the cumulative distribution function of this distribution.
That is, a function taking x :: t to the probability that the next
sample will return a value less than or equal to x, according to some
order or partial order (not necessarily an obvious one).
In the case where t is an instance of Ord, cdf should correspond
to the CDF with respect to that order.
In other cases, cdf is only required to satisfy the following law:
fmap (cdf d) (rvar d)
must be uniformly distributed over (0,1). Inclusion of either endpoint is optional,
though the preferred range is (0,1].
Note that this definition requires that cdf for a product type
should _not_ be a joint CDF as commonly defined, as that definition
violates both conditions.
Instead, it should be a univariate CDF over the product type. That is,
it should represent the CDF with respect to the lexicographic order
of the product.
The present specification is probably only really useful for testing conformance of a variable to its target distribution, and I am open to suggestions for more-useful specifications (especially with regard to the interaction with product types).
Instances
Sampling random variables
class Sampleable d m t whereSource
A typeclass allowing Distributions and RVars to be sampled. Both may
also be sampled via runRVar or runRVarT, but I find it psychologically
pleasing to be able to sample both using this function, as they are two
separate abstractions for one base concept: a random variable.
Methods
sampleFrom :: RandomSource m s => s -> d t -> m tSource
Directly sample from a distribution or random variable, using the given source of entropy.
Instances
| Distribution d t => Sampleable d m t | |
| Lift m n => Sampleable (RVarT m) n t |
sample :: (Sampleable d m t, MonadRandom m) => d t -> m tSource
Sample a random variable using the default source of entropy for the monad in which the sampling occurs.
sampleState :: (Sampleable d (State s) t, MonadRandom (State s)) => d t -> s -> (t, s)Source
Sample a random variable in a "functional" style. Typical instantiations
of s are System.Random.StdGen or System.Random.Mersenne.Pure64.PureMT.
sampleStateT :: (Sampleable d (StateT s m) t, MonadRandom (StateT s m)) => d t -> s -> m (t, s)Source
Sample a random variable in a "semi-functional" style. Typical instantiations
of s are System.Random.StdGen or System.Random.Mersenne.Pure64.PureMT.
A few very common distributions
A definition of a uniform distribution over the type t. See also uniform.
Constructors
| Uniform !t !t | A uniform distribution defined by a lower and upper range bound.
For |
Instances
uniform :: Distribution Uniform a => a -> a -> RVar aSource
data StdUniform t Source
A name for the "standard" uniform distribution over the type t,
if one exists. See also stdUniform.
For Integral and Enum types that are also Bounded, this is
the uniform distribution over the full range of the type.
For un-Bounded Integral types this is not defined.
For Fractional types this is a random variable in the range [0,1)
(that is, 0 to 1 including 0 but not including 1).
Constructors
| StdUniform |
Instances
stdUniform :: Distribution StdUniform a => RVar aSource
Get a "standard" uniformly distributed value.
For integral types, this means uniformly distributed over the full range
of the type (there is no support for Integer). For fractional
types, this means uniformly distributed on the interval [0,1).
A specification of a normal distribution over the type a.
Constructors
| StdNormal | The "standard" normal distribution - mean 0, stddev 1 |
| Normal a a |
|
Instances
| (Real a, Distribution Normal a) => CDF Normal a | |
| Distribution Normal Double | |
| Distribution Normal Float |
normal :: Distribution Normal a => a -> a -> RVar aSource
normal m s is a random variable with distribution Normal m s
stdNormal :: Distribution Normal a => RVar aSource
Constructors
| Gamma a a |
Instances
| (Floating a, Ord a, Distribution Normal a, Distribution StdUniform a) => Distribution Gamma a |
gamma :: Distribution Gamma a => a -> a -> RVar aSource
Entropy Sources
class Monad m => MonadRandom m Source
A typeclass for monads with a chosen source of entropy. For example,
RVar is such a monad - the source from which it is (eventually) sampled
is the only source from which a random variable is permitted to draw, so
when directly requesting entropy for a random variable these functions
are used.
The minimal definition is supportedPrims and getSupportedRandomPrim
with cases for those primitives where supportedPrims returns True.
It is recommended (despite the warnings it generates) that, even when
all primitives are supported, a final wildcard case of supportedPrims is
specified, as:
supportedPrims _ _ = False
The overlapping pattern warnings can be suppressed (without suppressing
other, genuine, overlapping-pattern warnings) by the GHC flag
-fno-warn-simple-patterns. This is not actually the documented behavior
of that flag as far as I can find in 3 google-minutes, but it works with
GHC 6.12.1 anyway, and that's good enough for me.
Note that it is very important that at least supportedPrims (and preferably
getSupportedRandomPrim as well) gets inlined into the default implementation
of getRandomPrim. If your supportedPrims is more than about 2 or 3
cases, add an INLINE pragma so that it can be optimized out of getRandomPrim.
Instances
| MonadRandom (State PureMT) | |
| MonadRandom (State StdGen) | |
| MonadRandom (State PureMT) | |
| MonadRandom (State StdGen) | |
| MonadRandom (RVarT n) | |
| Monad m => MonadRandom (StateT PureMT m) | |
| Monad m => MonadRandom (StateT StdGen m) | |
| Monad m => MonadRandom (StateT PureMT m) | |
| Monad m => MonadRandom (StateT StdGen m) |
class Monad m => RandomSource m s Source
A source of entropy which can be used in the given monad.
The minimal definition is supportedPrimsFrom and getSupportedRandomPrimFrom
with cases for those primitives where supportedPrimsFrom returns True.
Note that it is very important that at least supportedPrimsFrom (and preferably
getSupportedRandomPrimFrom as well) gets inlined into the default implementation
of getRandomPrimFrom. If your supportedPrimsFrom is more than about 2 or 3
cases, add an INLINE pragma so that it can be optimized out of getRandomPrimFrom.
See also MonadRandom.
Instances
| RandomSource IO DevRandom | |
| MonadRandom m => RandomSource m StdRandom | |
| RandomSource IO (Gen RealWorld) | |
| Monad m => RandomSource m (m Double) | |
| Monad m => RandomSource m (m Word64) | |
| Monad m => RandomSource m (m Word32) | |
| Monad m => RandomSource m (m Word16) | |
| Monad m => RandomSource m (m Word8) | |
| (Monad m, ModifyRef (IORef StdGen) m StdGen) => RandomSource m (IORef StdGen) | |
| (Monad m, ModifyRef (IORef PureMT) m PureMT) => RandomSource m (IORef PureMT) | |
| (Monad m, ModifyRef (STRef s StdGen) m StdGen) => RandomSource m (STRef s StdGen) | |
| (Monad m1, ModifyRef (Ref m2 StdGen) m1 StdGen) => RandomSource m1 (Ref m2 StdGen) | |
| (Monad m, ModifyRef (STRef s PureMT) m PureMT) => RandomSource m (STRef s PureMT) | |
| (Monad m1, ModifyRef (Ref m2 PureMT) m1 PureMT) => RandomSource m1 (Ref m2 PureMT) | |
| RandomSource (ST s) (Gen s) |
A token representing the "standard" entropy source in a MonadRandom
monad. Its sole purpose is to make the following true (when the types check):
sampleFrom StdRandom === sample
Constructors
| StdRandom |
Instances
| MonadRandom m => RandomSource m StdRandom |
Useful list-based operations
randomElement :: [a] -> RVar aSource
A random variable returning an arbitrary element of the given list.
Every element has equal probability of being chosen. Because it is a
pure RVar it has no memory - that is, it "draws with replacement."
shuffle :: [a] -> RVar [a]Source
A random variable that returns the given list in an arbitrary shuffled order. Every ordering of the list has equal probability.
shuffleN :: Int -> [a] -> RVar [a]Source
A random variable that shuffles a list of a known length (or a list prefix of the specified length). Useful for shuffling large lists when the length is known in advance. Avoids needing to traverse the list to discover its length. Each ordering has equal probability.
shuffleNofM :: Int -> Int -> [a] -> RVar [a]Source
A random variable that selects N arbitrary elements of a list of known length M.