-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Finite discrete probability distributions.
--   
--   Package for manipulating finite discrete probability distributions.
--   Supports transformations, measurements, efficient sampling and
--   plotting.
@package distribution
@version 1.1.1.0


-- | This modules defines types and functions for manipulating finite
--   discrete probability distributions.
module Data.Distribution.Core

-- | Probability. Should be between 0 and 1.
type Probability = Rational

-- | Distribution over values of type <tt>a</tt>.
--   
--   Due to their internal representations, <tt>Distribution</tt> can not
--   have <tt>Functor</tt> or <tt>Monad</tt> instances. However,
--   <a>select</a> is the equivalent of <tt>fmap</tt> for distributions and
--   <a>always</a> and <a>andThen</a> are respectively the equivalent of
--   <tt>return</tt> and <tt>&gt;&gt;=</tt>.
data Distribution a

-- | Converts the distribution to a mapping from values to their
--   probability. Values with probability <tt>0</tt> are not included in
--   the resulting mapping.
toMap :: Distribution a -> Map a Probability

-- | Converts the distribution to a list of increasing values whose
--   probability is greater than <tt>0</tt>. To each value is associated
--   its probability.
toList :: Distribution a -> [(a, Probability)]

-- | Returns the number of elements with non-zero probability in the
--   distribution.
size :: Distribution a -> Int

-- | Values in the distribution with non-zero probability.
support :: Distribution a -> Set a

-- | Distribution that assigns to each <tt>value</tt> from the given
--   <tt>(value, weight)</tt> pairs a probability proportional to
--   <tt>weight</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; fromList [('A', 1), ('B', 2), ('C', 1)]
--   fromList [('A',1 % 4),('B',1 % 2),('C',1 % 4)]
--   </pre>
--   
--   Values may appear multiple times in the list. In this case, their
--   total weight is the sum of the different associated weights. Values
--   whose total weight is zero or negative are ignored.
fromList :: (Ord a, Real p) => [(a, p)] -> Distribution a

-- | Distribution that assigns to <tt>x</tt> the probability of <tt>1</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; always 0
--   fromList [(0,1 % 1)]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; always 42
--   fromList [(42,1 % 1)]
--   </pre>
always :: a -> Distribution a

-- | Uniform distribution over the values. The probability of each element
--   is proportional to its number of appearance in the list.
--   
--   <pre>
--   &gt;&gt;&gt; uniform [1 .. 6]
--   fromList [(1,1 % 6),(2,1 % 6),(3,1 % 6),(4,1 % 6),(5,1 % 6),(6,1 % 6)]
--   </pre>
uniform :: (Ord a) => [a] -> Distribution a

-- | <tt>True</tt> with given probability and <tt>False</tt> with
--   complementary probability.
withProbability :: Real p => p -> Distribution Bool

-- | Applies a function to the values in the distribution.
--   
--   <pre>
--   &gt;&gt;&gt; select abs $ uniform [-1, 0, 1]
--   fromList [(0,1 % 3),(1,2 % 3)]
--   </pre>
select :: Ord b => (a -> b) -> Distribution a -> Distribution b

-- | Returns a new distribution conditioning on the predicate holding on
--   the value.
--   
--   <pre>
--   &gt;&gt;&gt; assuming (&gt; 2) $ uniform [1 .. 6]
--   fromList [(3,1 % 4),(4,1 % 4),(5,1 % 4),(6,1 % 4)]
--   </pre>
--   
--   Note that the resulting distribution will be invalid if the predicate
--   does not hold on any of the values.
--   
--   <pre>
--   &gt;&gt;&gt; assuming (&gt; 7) $ uniform [1 .. 6]
--   fromList []
--   </pre>
assuming :: (a -> Bool) -> Distribution a -> Distribution a

-- | Returns a new distribution using the Bayesian update rule.
--   
--   Using this example:
--   <a>https://en.wikipedia.org/wiki/Bayesian_inference#Probability_of_a_hypothesis</a>
--   
--   <pre>
--   data CookieBowl = Bowl1 | Bowl2 deriving (Eq,Ord)
--   data CookieType = Plain | ChocolateChip deriving (Eq,Ord)
--   
--   assumption :: Distribution CookieBowl
--   assumption = uniform [Bowl1,Bowl2]
--   
--   update :: Cookie -&gt; Distribution CookieBowl -&gt; Distribution CookieBowl
--   update c = observing f where
--     f b = case b of
--       -- Bowl #1 contains 10 chocolate chip cookies and 30 plain cookies
--       Bowl1 -&gt; fromList [(c == ChocolateChip,10),(c == Plain,30)]
--       -- Bowl #2 contains 20 of each flavour of cookie
--       Bowl2 -&gt; fromList [(c == ChocolateChip,20),(c == Plain,20)]
--   </pre>
--   
--   The "update" function in this example can be used to update the
--   probability distribution of which bowl you have based on observing a
--   random cookie inside the bowl.
observing :: (a -> Distribution Bool) -> Distribution a -> Distribution a
combineWith :: (Ord b) => (a -> a -> b) -> Distribution a -> Distribution a -> Distribution b

-- | Binomial distribution. Assigns to each number of successes its
--   probability.
--   
--   <pre>
--   &gt;&gt;&gt; trials 2 $ uniform [True, False]
--   fromList [(0,1 % 4),(1,1 % 2),(2,1 % 4)]
--   </pre>
trials :: Int -> Distribution Bool -> Distribution Int

-- | Takes <tt>n</tt> samples from the distribution and returns the
--   distribution of their sum.
--   
--   <pre>
--   &gt;&gt;&gt; times 2 $ uniform [1 .. 3]
--   fromList [(2,1 % 9),(3,2 % 9),(4,1 % 3),(5,2 % 9),(6,1 % 9)]
--   </pre>
--   
--   This function makes use of the more efficient <tt>trials</tt>
--   functions for input distributions of size <tt>2</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; size $ times 10000 $ uniform [1, 10]
--   10001
--   </pre>
times :: (Num a, Ord a) => Int -> Distribution a -> Distribution a
iid :: (Ord a) => (a -> a -> a) -> Int -> Distribution a -> Distribution a

-- | Computes for each value in the distribution a new distribution, and
--   then combines those distributions, giving each the weight of the
--   original value.
--   
--   <pre>
--   &gt;&gt;&gt; uniform [1 .. 3] `andThen` (\ n -&gt; uniform [1 .. n])
--   fromList [(1,11 % 18),(2,5 % 18),(3,1 % 9)]
--   </pre>
--   
--   See the <tt>Experiment</tt> data type in the <a>Monadic</a> module for
--   a more "natural" monadic interface.
andThen :: Ord b => Distribution a -> (a -> Distribution b) -> Distribution b
infixl 7 `andThen`

-- | Determines if a distribution is valid.
--   
--   A distribution is valid if and only if its domain is non-empty.
--   Invalid distributions may arise from the use of <a>assuming</a> for
--   instance.
isValid :: Distribution a -> Bool
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Distribution.Core.Distribution a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Distribution.Core.Distribution a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Distribution.Core.Distribution a)
instance GHC.Enum.Bounded a => GHC.Enum.Bounded (Data.Distribution.Core.Distribution a)
instance (GHC.Classes.Ord a, GHC.Num.Num a) => GHC.Num.Num (Data.Distribution.Core.Distribution a)
instance (GHC.Classes.Ord a, GHC.Real.Fractional a) => GHC.Real.Fractional (Data.Distribution.Core.Distribution a)
instance (GHC.Classes.Ord a, GHC.Float.Floating a) => GHC.Float.Floating (Data.Distribution.Core.Distribution a)
instance (GHC.Classes.Ord a, GHC.Base.Monoid a) => GHC.Base.Monoid (Data.Distribution.Core.Distribution a)


-- | Module containing functions to apply on lists of values tagged with
--   their probability, in order to somehow aggregate or transform the
--   probabilities.
module Data.Distribution.Aggregator

-- | Functions that can modify probabilities.
data Aggregator a

-- | Creates an aggregator from a function. The function should not modify
--   the number of elements.
makeAggregator :: ([(a, Probability)] -> [Probability]) -> Aggregator a

-- | Creates an aggregator from a function ignoring the values. The
--   function should not modify the number of elements.
makePureAggregator :: ([Probability] -> [Probability]) -> Aggregator a

-- | Aggregator that applies the first aggregator on values less than
--   <tt>x</tt> and the second on values greater than <tt>x</tt>. Potential
--   probability at <tt>x</tt> is left untouched.
separated :: Ord a => a -> Aggregator a -> Aggregator a -> Aggregator a

-- | Applies the aggregator and returns the modified list of probabilities.
modifyProbabilities :: Aggregator a -> [(a, Probability)] -> [Probability]

-- | Applies an aggregator on a list of values tagged with their
--   probability. The values themselves are left unchanged.
aggregateWith :: Aggregator a -> [(a, Probability)] -> [(a, Probability)]

-- | Adds to each probability the sum of the probabilities earlier in the
--   list.
--   
--   <pre>
--   &gt;&gt;&gt; aggregateWith cumulative $ toList $ uniform [1 .. 5]
--   [(1,1 % 5),(2,2 % 5),(3,3 % 5),(4,4 % 5),(5,1 % 1)]
--   </pre>
cumulative :: Aggregator a

-- | Adds to each probability the sum of probabilities later in the list.
--   
--   <pre>
--   &gt;&gt;&gt; aggregateWith decreasing  $ toList $ uniform [1 .. 5]
--   [(1,1 % 1),(2,4 % 5),(3,3 % 5),(4,2 % 5),(5,1 % 5)]
--   </pre>
decreasing :: Aggregator a

-- | Replaces each probability by its complement.
--   
--   <pre>
--   &gt;&gt;&gt; aggregateWith complementary $ toList $ uniform [1 .. 5]
--   [(1,4 % 5),(2,4 % 5),(3,4 % 5),(4,4 % 5),(5,4 % 5)]
--   </pre>
complementary :: Aggregator a
instance GHC.Base.Monoid (Data.Distribution.Aggregator.Aggregator a)


-- | This modules provides distributions from coins and functions on coins.
module Data.Distribution.Domain.Coin

-- | Distribution over the sides of a coin.
type Coin = Distribution CoinSide

-- | Possible outcomes of a coin flip.
data CoinSide
Head :: CoinSide
Tail :: CoinSide

-- | Fair coin.
coin :: Coin

-- | Flips <tt>n</tt> times the given coin and counts the number of heads.
flipsOf :: Int -> Coin -> Distribution Int

-- | Rerolls the coin once if the first outcome satifies the given
--   predicate.
reflipOn :: CoinSide -> Coin -> Coin
instance GHC.Enum.Enum Data.Distribution.Domain.Coin.CoinSide
instance GHC.Read.Read Data.Distribution.Domain.Coin.CoinSide
instance GHC.Show.Show Data.Distribution.Domain.Coin.CoinSide
instance GHC.Classes.Ord Data.Distribution.Domain.Coin.CoinSide
instance GHC.Classes.Eq Data.Distribution.Domain.Coin.CoinSide


-- | This modules provides distributions from dice and functions on dice.
module Data.Distribution.Domain.Dice

-- | Distribution of the result of dice rolls.
type Dice = Distribution Int

-- | Fair dice of <tt>n</tt> faces.
dice :: Int -> Dice

-- | Fair dice of <tt>4</tt> faces.
d4 :: Dice

-- | Fair dice of <tt>6</tt> faces.
d6 :: Dice

-- | Fair dice of <tt>8</tt> faces.
d8 :: Dice

-- | Fair dice of <tt>10</tt> faces.
d10 :: Dice

-- | Fair dice of <tt>20</tt> faces.
d20 :: Dice

-- | Rolls <tt>n</tt> times the given dice and sums the results.
rollsOf :: Int -> Dice -> Dice

-- | Rerolls the dice once if the first outcome satifies the given
--   predicate.
rerollOn :: (Int -> Bool) -> Dice -> Dice


-- | This modules provides various measures on finite discrete probability
--   distributions.
module Data.Distribution.Measure

-- | Probability that a predicate holds on the distribution.
--   
--   <pre>
--   &gt;&gt;&gt; probability (\ x -&gt; x == 1 || x == 6) $ uniform [1 .. 6]
--   1 % 3
--   </pre>
--   
--   Takes <tt>O(n)</tt> time. See <a>probabilityAt</a> and
--   <a>probabilityIn</a> for a more efficient ways to query elements and
--   ranges.
probability :: (a -> Bool) -> Distribution a -> Probability

-- | Probability of a given value.
--   
--   Takes <tt>O(log(n))</tt> time.
probabilityAt :: Ord a => a -> Distribution a -> Probability

-- | Probability of a the inclusive <tt>[low, high]</tt> range. When
--   <tt>low &gt; high</tt>, the probability is 0.
--   
--   Takes <tt>O(log(n) + m)</tt> time, where <tt>n</tt> is the size of the
--   distribution and <tt>m</tt> the size of the range.
probabilityIn :: Ord a => (a, a) -> Distribution a -> Probability

-- | Returns the expectation, or mean, of a distribution.
--   
--   <pre>
--   &gt;&gt;&gt; expectation $ uniform [0, 1]
--   0.5
--   </pre>
--   
--   Empty distributions have an expectation of <tt>0</tt>.
expectation :: (Real a, Fractional b) => Distribution a -> b

-- | Synonym of <a>expectation</a>.
mean :: (Real a, Fractional b) => Distribution a -> b

-- | Returns the variance of a distribution.
--   
--   <pre>
--   &gt;&gt;&gt; variance $ always 1
--   0.0
--   
--   &gt;&gt;&gt; variance $ uniform [0 .. 1]
--   0.25
--   
--   &gt;&gt;&gt; variance $ uniform [1 .. 7]
--   4.0
--   </pre>
--   
--   Empty distributions have a variance of <tt>0</tt>.
variance :: (Real a, Fractional b) => Distribution a -> b

-- | Standard deviation.
--   
--   <pre>
--   &gt;&gt;&gt; standardDeviation $ always 1
--   0.0
--   
--   &gt;&gt;&gt; standardDeviation $ uniform [0 .. 1]
--   0.5
--   
--   &gt;&gt;&gt; standardDeviation $ uniform [1 .. 7]
--   2.0
--   </pre>
standardDeviation :: (Real a, Floating b) => Distribution a -> b

-- | Returns the median of the values. The median is the smallest value
--   such that at least 50% of the values are less or equal to it.
--   
--   <pre>
--   &gt;&gt;&gt; median $ fromList [(1, 0.6), (2, 0.4)]
--   Just 1
--   
--   &gt;&gt;&gt; median $ fromList [(1, 0.4), (2, 0.6)]
--   Just 2
--   </pre>
median :: Distribution a -> Maybe a

-- | Returns all values whose probability is maximal.
modes :: Distribution a -> [a]

-- | Returns the smallest value in the distribution such that at least a
--   fraction <tt>p</tt> of the values are less or equal to it.
--   
--   <pre>
--   &gt;&gt;&gt; quantile 0.0 $ uniform [1, 2, 3]
--   Just 1
--   
--   &gt;&gt;&gt; quantile 0.5 $ uniform [1, 2, 3]
--   Just 2
--   
--   &gt;&gt;&gt; quantile 1.0 $ uniform [1, 2, 3]
--   Just 3
--   
--   &gt;&gt;&gt; quantile 0.5 $ fromList []
--   Nothing
--   </pre>
quantile :: Probability -> Distribution a -> Maybe a


-- | This modules provides a monadic interface to build distributions.
module Data.Distribution.Monadic

-- | Monadic description of distributions.
data Experiment a

-- | Converts a concrete distribution into its monadic representation.
from :: (Ord a) => Distribution a -> Experiment a

-- | Converts the monadic description of the distribution to a concrete
--   distribution.
run :: (Ord a) => Experiment a -> Distribution a
instance GHC.Base.Functor Data.Distribution.Monadic.Experiment
instance GHC.Base.Applicative Data.Distribution.Monadic.Experiment
instance GHC.Base.Monad Data.Distribution.Monadic.Experiment


-- | This modules provides ways to randomly and efficiently sample values
--   from distributions.
--   
--   Walker's <a>alias method</a> is used internally, so that values can be
--   sampled in constant time.
module Data.Distribution.Sample

-- | Generator of random values of type <tt>a</tt>.
--   
--   Can be created in linear time from distributions and sampled in
--   constant time.
data Generator a

-- | Creates a generator from the given non-empty distribution.
--   
--   Runs in <tt>O(n)</tt> time where <tt>n</tt> is the size of the
--   distribution.
fromDistribution :: Distribution a -> Generator a

-- | Safe version of <a>fromDistribution</a>. Returns <tt>Nothing</tt> when
--   the given distribution is empty.
safeFromDistribution :: Distribution a -> Maybe (Generator a)

-- | Picks a random value from the generator.
--   
--   Runs in constant <tt>O(1)</tt> time.
sample :: RandomGen g => Generator a -> g -> (a, g)

-- | Picks a random value from the generator.
--   
--   Runs in constant <tt>O(1)</tt> time.
getSample :: MonadRandom m => Generator a -> m a
instance GHC.Base.Functor Data.Distribution.Sample.Generator


-- | This module defines finite discrete probability distributions and
--   efficient ways to construct, modify, combine, measure and sample them.
--   
--   The various functionalities are each defined in their own submodules
--   and simply re-exported here. Note that not all modules in the package
--   are directly exported by this top-level module.
module Data.Distribution
