SpH      !"#$%& ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; < = > ? @ A B C D E F G H I J K L M NOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~@Given an upward-closed predicate on an ordered Fractional type, 3 find the smallest value satisfying the predicate. The  type doesn'/t expose its constructors, but I need a way to F convert them to and from their raw representation in order to sample  them. As long as  is a newtype wrapping ,  and  9 as defined here will work. Both are implemented using  . GBuild a word out of 8 bytes. No promises are made regarding the order > in which the bytes are stuffed. Note that this means that a  RandomSource  or  MonadRandom) making use of the default definition of  getRandomWord, etc., I may return different random values on different platforms when started . with the same seed, depending on the platform's endianness. Pack the low 23 bits from a  into a  in the range [0,1).  Used to convert a  stdUniform  to a  stdUniform . @Same as wordToFloat, but also return the unused bits (as the 41  least significant bits of a ) Pack the low 52 bits from a  into a  in the range [0,1).  Used to convert a  stdUniform  to a  stdUniform . ASame as wordToDouble, but also return the unused bits (as the 12  least significant bits of a )     Names of standard  types Names of standard  types &replicateInstances standin types decls will take the template-haskell  s in decls& and substitute every instance of the  standin with  each  in types, producing one copy of the s in decls for every   in types.  For example,  Data.Random.Distribution.Uniform# has the following bit of TH code:   $( replicateInstances ''Int integralTypes [d| Y instance Distribution Uniform Int where rvar (Uniform a b) = integralUniform a b \ instance CDF Uniform Int where cdf (Uniform a b) = integralUniformCDF a b  |])MThis code takes those 2 instance declarations and creates identical ones for  every type named in  .     A class for "liftable" data structures. Conceptually  an extension of  to allow deep lifting, > but lifting need not be done between monads only. Eg lifting  between  Applicatives is allowed. For instances where m and n have 'return'/'pure' defined,  these instances must satisfy  lift (return x) == return x. 9This instance is incoherent with the other two. However,  by the law lift (return x) == return x, the results  must always be the same. :A source of entropy which can be used in the given monad. !The minimal definition is either  or .   is defaulted in terms of  )Get a random uniformly-distributed byte.  Get a random 8 uniformly-distributed over the full range of the type.  Get a random / uniformly-distributed over the interval [0,1) FA typeclass for monads with a chosen source of entropy. For example,  RVarD is such a monad - the source from which it is (eventually) sampled J is the only source from which a random variable is permitted to draw, so H when directly requesting entropy for a random variable these functions  are used. !The minimal definition is either  or .   is defaulted in terms of . )Get a random uniformly-distributed byte.  Get a random 8 uniformly-distributed over the full range of the type.  Get a random / uniformly-distributed over the interval [0,1) On systems that have it, /dev/,random is a handy-dandy ready-to-use source B of nonsense. Keep in mind that on some systems, Linux included, /dev/random  collects "real" entropy, and if you don'$t have a good source of it, such as C special hardware for the purpose or a *lot* of network traffic, it's pretty easy M to suck the entropy pool dry with entropy-intensive applications. For many # purposes other than cryptography, /dev/&urandom is preferable because when it  runs out of real entropy it'&ll still churn out pseudorandom data.   Given a mutable reference to a  generator, we can make a  = usable in any monad in which the reference can be modified. For example, if x :: TVar StdGen, getRandomByteFromRandomGenRef x can be  used as a  in , $, or any monad which is an instance  of . It'#s generally probably better to use  !( though, as this one is likely to throw Q away a lot of perfectly good entropy. Better still is to use these 3 functions  together to create a  instance for the reference you' re using,  if one does not already exist. !"# Similarly, !getRandomWordFromRandomGenState x can be used in any "state" ) monad in the mtl sense whose state is a  generator. 2 Additionally, the standard mtl state monads have  instances 9 which do precisely that, allowing an easy conversion of RVars and  other  Distribution instances to "pure" random variables. $%  !"#$%  !"#$%  !"#$% &Given a mutable reference to a  generator, we can make a  = usable in any monad in which the reference can be modified. For example, if x :: TVar PureMT, getRandomWordFromMTRef x can be  used as a  in , $, or any monad which is an instance  of <. These functions can also be used to implement additional  % instances for mutable references to  states. '() Similarly, getRandomWordFromMTState x can be used in any "state" ) monad in the mtl sense whose state is a  generator. 2 Additionally, the standard mtl state monads have  instances 9 which do precisely that, allowing an easy conversion of RVars and  other  Distribution instances to "pure" random variables (e.g., by  ErunState . sample :: Distribution d t => d t -> PureMT -> (t, PureMT).  & in the type there can be replaced by StdGen or anything else  satisfying MonadRandom (State s) => s). *+&'()*+&'()*+&'()*+ ,A token representing the "standard" entropy source in a  P monad. Its sole purpose is to make the following true (when the types check): ! sampleFrom StdRandom === sample -,-,-,-- .LA random variable with access to operations in an underlying monad. Useful W examples include any form of state for implementing random processes with hysteresis, F or writer monads for implementing tracing of complicated algorithms. 5single combined container allowing all the relevant ? dictionaries (plus the RandomSource item itself) to be passed  with one pointer. /An opaque type containing a "random variable" - a value 6 which depends on the outcome of some random process. 01"Runs" the monad. 2EA random variable evenly distributed over all unsigned integers from  0 to 2^(8*n)-1, inclusive. 3EA random variable evenly distributed over all unsigned integers from  0 to 2^n-1, inclusive. ./0123/0.123./0123 45BReturn the cumulative distribution function of this distribution.  That is, a function taking x :: t" to the probability that the next G 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, 5 should correspond ( to the CDF with respect to that order. In other cases, 50 is only required to satisfy the following law:  fmap (cdf d) (rvar d) V must be uniformly distributed over (0,1). Inclusion of either endpoint is optional, # though the preferred range is (0,1]. Thus, 5; for a product type should not be a joint CDF as commonly 7 defined, as that definition violates both conditions. I Instead, it should be a univariate CDF over the product type. That is, E it should represent the CDF with respect to the lexicographic order  of the tuple. 6!A definition of a random variable''s distribution. From the distribution  an /D can be created, or the distribution can be directly sampled using   sampleFrom or sample. 71Return a random variable with this distribution. 8QReturn a random variable with the given distribution, pre-lifted to an arbitrary ..  Any arbitrary / can also be converted to an 'RVarT m' for an arbitrary m, using  either  or sample. 45678674584556778 9A name for the "standard"$ uniform distribution over the type t,  if one exists. See also K. For  and  types that are also  , this is ; the uniform distribution over the full range of the type.  For un-  types this is not defined.  For 4 types this is a random variable in the range [0,1) 4 (that is, 0 to 1 including 0 but not including 1). :;5A definition of a uniform distribution over the type t . See also J. <AA uniform distribution defined by a lower and upper range bound.  For  and % types, the range is inclusive. For  = types the range includes the lower bound but not the upper. =Compute a random 2 value between the 2 values provided (inclusive). >Compute a random value for a  type, between  and   (inclusive for  or  types, in [, ) for Fractional types.) ?Compute a random value for a   type, between  and   (inclusive) @Compute a uniform random  value in the range [0,1) ACompute a uniform random  value in the range [0,1) B:Compute a uniform random value in the range [0,1) for any  type CCompute a uniform random $ value in the range [0,1), with any  desired precision. DThe CDF of the random variable B. EfloatUniform a b computes a uniform random  value in the range [a,b) FdoubleUniform a b computes a uniform random  value in the range [a,b) GrealFloatUniform a b8 computes a uniform random value in the range [a,b) for  any  type HfixedUniform a b computes a uniform random  value in the range $ [a,b), with any desired precision. IrealUniformCDF a b# is the CDF of the random variable realFloatUniform a b. realFloatUniform a b8 computes a uniform random value in the range [a,b) for  any  type JKGet a "standard" uniformly distributed value. J For integral types, this means uniformly distributed over the full range J of the type (and hence there is no support for Integer). For fractional @ types, this means uniformly distributed on the interval [0,1). LLike K , but uses ) to return only positive or zero values. MLike K# but only returns positive values. 9:;<=>?@ABCDEFGHIJKLM;<J9:KLM=GEFH>?BC@ADI9::;<<=>?@ABCDEFGHIJKLMNOP>Generate a Bernoulli variate with the given probability. For Bool results,   bernoulli p< will return True (p*100)% of the time and False otherwise. < For numerical types, True is replaced by 1 and False by 0. Q!A random variable whose value is  the given fraction of the time  and  the rest. RSgeneralBernoulli t f p, generates a random variable whose value is t  with probability p and f with probability 1-p. TNOPQRSTPQRSTNONOOPQRSTUVWXYUVWXYUVWXYUVVWXYZ1The rayleigh distribution with a specified mode ("sigma" ) parameter.  Its mean will be  sigma*sqrt(pi,2)@ and its variance will be @sigma^2*(4-pi)2 2(therefore if you want one with a particular mean m, sigma should be m*sqrt(2/pi)) [\]^Z[\]^\Z[]^Z[[\]^_FA description of a triangular distribution - a distribution whose PDF E is a triangle ramping up from a lower bound to a specified midpoint G and back down to the upper bound. This is a very simple distribution E that does not generally occur naturally but is used sometimes as an G estimate of a true distribution when only the range of the values and 9 an approximate mode of the true distribution are known. `a_The lower bound of the triangle in the PDF (the smallest number the distribution can generate) bAThe midpoint of the triangle (also the mode of the distribution) cWThe upper bound of the triangle (and the largest number the distribution can generate) d(Compute a triangular distribution for a  type. The name is 5 a historical accident and may change in the future. erealFloatTriangularCDF a b c is the CDF of realFloatTriangular a b c. _`abcde_`abcde_`abc`abcdef8A data structure containing all the data that is needed  to implement Marsaglia & Tang's "ziggurat" algorithm for 1 sampling certain kinds of random distributions. IThe documentation here is probably not sufficient to tell a user exactly J how to build one of these from scratch, but it is not really intended to 9 be. There are several helper functions that will build gfs. 1 The pathologically curious may wish to read the p source. J That is the ultimate specification of the semantics of all these fields. gh?The X locations of each bin in the distribution. Bin 0 is the  infinite one. >In the case of bin 0, the value given is sort of magical - x[0] is  defined to be V/ f(R). It')s not actually the location of any bin, G but a value computed to make the algorithm more concise and slightly A faster by not needing to specially-handle bin 0 quite as often. 2 If you really need to know why it works, see the p  source or "the literature" - it's a fairly standard setup. iThe ratio of each bin's Y value to the next bin' s Y value j"The Y value (zFunc x) of each bin k0An RVar providing a random tuple consisting of: / a bin index, uniform over [0,c) :: Int (where c is the " number of bins in the tables) 9 a uniformly distributed fractional value, from -1 to 1 , if not mirrored, from 0 to 1 otherwise. This is provided as a single / because it can be implemented > more efficiently than naively sampling 2 separate values - a > single random word (64 bits) can be efficiently converted to B a double (using 52 bits) and a bin number (using up to 12 bits),  for example. lThe distribution for the final "virtual" bin 7 (the ziggurat algorithm does not handle distributions @ that wander off to infinity, so another distribution is needed  to handle the last "bin" that stretches to infinity) m8A copy of the uniform RVar generator for the base type,  so that Distribution Uniform t is not needed when sampling 7 from a Ziggurat (makes it a bit more self-contained). n9The (one-sided antitone) PDF, not necessarily normalized o5A flag indicating whether the distribution should be 6 mirrored about the origin (the ziggurat algorithm it < its native form only samples from one-sided distributions. ; By mirroring, we can extend it to symmetric distributions " such as the normal distribution) p*Sample from the distribution encoded in a gf data structure. q"Build the tables to implement the "ziggurat algorithm" devised by  Marsaglia &7 Tang, attempting to automatically compute the R and V  values.  Arguments: 4 flag indicating whether to mirror the distribution : the (one-sided antitone) PDF, not necessarily normalized  the inverse of the PDF  the number of bins ! R, the x value of the first bin  V, the volume of each bin  an RVar providing the k random tuple 9 an RVar sampling from the tail (the region where x > R) r"Build the tables to implement the "ziggurat algorithm" devised by  Marsaglia &7 Tang, attempting to automatically compute the R and V  values. Arguments are the same as for s, with an additional B argument for the tail distribution as a function of the selected  R value. sEBuild a lazy recursive ziggurat. Uses a lazily-constructed ziggurat B as its tail distribution (with another as its tail, ad nauseum).  Arguments: 4 flag indicating whether to mirror the distribution : the (one-sided antitone) PDF, not necessarily normalized  the inverse of the PDF , the integral of the PDF (definite, from 0) : the estimated volume under the PDF (from 0 to +infinity) = the chunk size (number of bins in each layer). 64 seems to  perform well in practice.  an RVar providing the k random tuple tI suspect this isn'.t completely right, but it works well so far. 5 Search the distribution for an appropriate R and V.  Arguments:  Number of bins F target function (one-sided antitone PDF, not necessarily normalized)  function inverse * function definite integral (from 0 to _) G estimate of total volume under function (integral from 0 to infinity) Result: (R,V) fghijklmnopqrstfghijklmnosrqtpf ghijklmnoghijklmnopqrstu7A specification of a normal distribution over the type a. v Normal m s$ is a normal distribution with mean m and stddev s. wThe "standard"( normal distribution - mean 0, stddev 1 x6A random variable that produces a pair of independent  normally-distributed values. y6A random variable that produces a pair of independent D normally-distributed values, computed using the Box-Muller method. - This algorithm is slightly slower than Knuth's method but using a " constant amount of entropy (Knuth'!s method is a rejection method). ( It is also slightly more general (Knuth's method require an   instance). z6A random variable that produces a pair of independent 2 normally-distributed values, computed using Knuth's polar method.  Slightly faster than y when it accepts on the ' first try, but does not always do so. {SDraw from the tail of a normal distribution (the region beyond the provided value)  Construct a gf+ for sampling a normal distribution, given   logBase 2 c and the k implementation. GZiggurat target function (upper half of a non-normalized gaussian PDF)  inverse of   integral of   volume of  |AA random variable sampling from the standard normal distribution  over any 0 type (subject to the rest of the constraints -  it builds and uses a gf internally, which requires the   and  classes). Because it computes a gf", it is very expensive to use for G just one evaluation, or even for multiple evaluations if not used and H reused monomorphically (to enable the ziggurat table to be let-floated  out). If you don'3t know whether your use case fits this description  then you'<re probably better off using a different algorithm, such as  y or z. And of course if  you don'6t need the full generality of this definition then you're much  better off using } or ~. @As far as I know, this should be safe to use in any monomorphic  Distribution Normal instance declaration. }AA random variable sampling from the standard normal distribution  over the  type. ~AA random variable sampling from the standard normal distribution  over the  type. ( is a normal variable with distribution w.  normal m s( is a random variable with distribution vu m s. uvwxyz{|}~ uwv}~|{xyz uwvvwxyz{|}~DA random variable returning an arbitrary element of the given list. G Every element has equal probability of being chosen. Because it is a  pure / it has no memory - that is, it "draws with replacement." GA random variable that returns the given list in an arbitrary shuffled ; order. Every ordering of the list has equal probability. FA random variable that shuffles a list of a known length. Useful for < shuffling large lists when the length is known in advance. L Avoids needing to traverse the list to discover its length. Each ordering  has equal probability. <Throws an error the list is not exactly as long as claimed. Like 2, but for the weights of a discrete distribution. @Adjust all the weights of a discrete distribution so that they D sum to unity. If not possible, returns the original distribution  unchanged. ISimplify a discrete distribution by combining equivalent events (the new B event will have a weight equal to the sum of all the originals). ISimplify a discrete distribution by combining equivalent events (the new B event will have a weight equal to the sum of all the originals). N The comparator function is used to identify events to combine. Once chosen, K the events and their weights are combined (independently) by the provided ) weight and event aggregation functions. A typeclass allowing 6s and /s to be sampled. Both may  also be sampled via 0 or 1 , but I find it psychologically 9 pleasing to be able to sample both using this function. [Directly sample from a distribution or random variable, using the given source of entropy. BSample a distribution using the default source of entropy for the % monad in which the sampling occurs.  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ !"#$%&'()*+,-./01234567689:;<=>?@ A B C D E F G G H I J K L M N O P Q R S S T T U V W X Y Z [ \ ] ^ _ ` a b c d effghijklmnopqqrstuuvwxyz{{|}~ H   random-fu-0.0.3.2Data.Random.Internal.FindData.Random.Internal.FixedData.Random.Internal.WordsData.Random.Internal.THData.Random.LiftData.Random.SourceData.Random.Source.DevRandomData.Random.Source.StdGenData.Random.Source.PureMTData.Random.Source.StdData.Random.RVarData.Random.Distribution Data.Random.Distribution.Uniform"Data.Random.Distribution.Bernoulli$Data.Random.Distribution.Exponential!Data.Random.Distribution.Rayleigh#Data.Random.Distribution.Triangular!Data.Random.Distribution.ZigguratData.Random.Distribution.NormalData.Random.Distribution.GammaData.Random.Distribution.Beta!Data.Random.Distribution.Binomial Data.Random.Distribution.PoissonData.Random.List!Data.Random.Distribution.DiscreteData.Random.Sample Data.RandomfindMax findMaxFromfindMin findMinFrom resolutionOf resolutionOf2mkFixed unMkFixed buildWord wordToFloatwordToFloatWithExcess wordToDoublewordToDoubleWithExcess integralTypesrealFloatTypesreplicateInstancesLiftlift RandomSourcegetRandomByteFromgetRandomWordFromgetRandomDoubleFrom MonadRandom getRandomByte getRandomWordgetRandomDouble DevRandom DevURandomgetRandomByteFromStdGenIOgetRandomWordFromStdGenIOgetRandomDoubleFromStdGenIOgetRandomByteFromRandomGenRefgetRandomWordFromRandomGenRefgetRandomDoubleFromRandomGenRefgetRandomByteFromRandomGenStategetRandomWordFromRandomGenState!getRandomDoubleFromRandomGenStategetRandomWordFromMTRefgetRandomByteFromMTRefgetRandomDoubleFromMTRefgetRandomWordFromMTStategetRandomByteFromMTStategetRandomDoubleFromMTState StdRandomRVarTRVarrunRVarrunRVarT nByteInteger nBitIntegerCDFcdf DistributionrvarrvarT StdUniformUniformintegralUniformboundedStdUniformboundedEnumStdUniformfloatStdUniformdoubleStdUniformrealFloatStdUniformfixedStdUniformrealStdUniformCDF floatUniform doubleUniformrealFloatUniform fixedUniformrealUniformCDFuniform stdUniformstdUniformNonneg stdUniformPos Bernoulli bernoulli boolBernoulliboolBernoulliCDFgeneralBernoulligeneralBernoulliCDF ExponentialExpfloatingExponentialfloatingExponentialCDF exponentialRayleighfloatingRayleighrayleigh rayleighCDF TriangulartriLowertriMidtriUpperrealFloatTriangularrealFloatTriangularCDFZiggurat zTable_xszTable_x_ratios zTable_yszGetIU zTailDistzUniformzFunczMirror runZiggurat mkZiggurat_ mkZiggurat mkZigguratRecfindBin0Normal StdNormal normalPairboxMullerNormalPairknuthPolarNormalPair normalTailrealFloatStdNormaldoubleStdNormalfloatStdNormal stdNormalnormalErlangGammarealFloatGammarealFloatErlanggammaerlangBetafractionalBetafractionalBetaFromIntegralbetaBinomialintegralBinomialintegralBinomialCDFfloatingBinomialfloatingBinomialCDFbinomialPoissonintegralPoissonintegralPoissonCDFfractionalPoissonfractionalPoissonCDFpoisson randomElementshuffleshuffleNDiscretediscrete empiricalmapDiscreteWeightsnormalizeDiscreteWeightscollectDiscreteEventscollectDiscreteEventsBy Sampleable sampleFromsamplebase Data.FixedFixed integer-gmpGHC.Integer.TypeInteger Unsafe.Coerce unsafeCoerceGHC.WordWord64ghc-prim GHC.TypesFloatDoubleGHC.RealIntegral GHC.Float RealFloat replaceNametemplate-haskellLanguage.Haskell.TH.SyntaxDecName mtl-1.1.1.0Control.Monad.Trans MonadTrans$fLiftIdentitymrandom-1.0.0.2 System.Random RandomGenIOGHC.ConcSTMMonadIOmersenne-random-pure64-0.2.0.3System.Random.Mersenne.Pure64PureMTunRVarTRVarDictGHC.EnumEnumBounded FractionalminBoundmaxBoundboundedStdUniformCDFboundedEnumStdUniformCDF enumUniformenumUniformCDFGHC.NumabsGHC.BoolTrueFalse zigguratTable GHC.ClassesOrdnormalZnormalF normalFInv normalFInt normalFVol erf-1.0.0.0Data.Number.ErfErfForeign.StorableStorabledoubleStdNormalCdoubleStdNormalRdoubleStdNormalVdoubleStdNormalZfloatStdNormalCfloatStdNormalRfloatStdNormalVfloatStdNormalZ normalPdf normalCdfGHC.Basefmap