-- 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.0.0.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 a.
--
-- Due to their internal representations, Distribution can not
-- have Functor or Monad instances. However,
-- select is the equivalent of fmap for distributions and
-- always and andThen are respectively the equivalent of
-- return and >>=.
data Distribution a
-- | Converts the distribution to a mapping from values to their
-- probability. Values with probability 0 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 0. 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 value from the given
-- (value, weight) pairs a probability proportional to
-- weight.
--
--
-- >>> fromList [('A', 1), ('B', 2), ('C', 1)]
-- fromList [('A',1 % 4),('B',1 % 2),('C',1 % 4)]
--
--
-- 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 x the probability of 1.
--
--
-- >>> always 0
-- fromList [(0,1 % 1)]
--
--
--
-- >>> always 42
-- fromList [(42,1 % 1)]
--
always :: a -> Distribution a
-- | Uniform distribution over the values. The probability of each element
-- is proportional to its number of appearance in the list.
--
--
-- >>> uniform [1 .. 6]
-- fromList [(1,1 % 6),(2,1 % 6),(3,1 % 6),(4,1 % 6),(5,1 % 6),(6,1 % 6)]
--
uniform :: Ord a => [a] -> Distribution a
-- | True with given probability and False with
-- complementary probability.
withProbability :: Real p => p -> Distribution Bool
-- | Applies a function to the values in the distribution.
--
--
-- >>> select abs $ uniform [-1, 0, 1]
-- fromList [(0,1 % 3),(1,2 % 3)]
--
select :: Ord b => (a -> b) -> Distribution a -> Distribution b
-- | Returns a new distribution conditioning on the predicate holding on
-- the value.
--
--
-- >>> assuming (> 2) $ uniform [1 .. 6]
-- fromList [(3,1 % 4),(4,1 % 4),(5,1 % 4),(6,1 % 4)]
--
--
-- Note that the resulting distribution will be empty if the predicate
-- does not hold on any of the values.
--
--
-- >>> assuming (> 7) $ uniform [1 .. 6]
-- fromList []
--
assuming :: (a -> Bool) -> Distribution a -> Distribution a
-- | Combines multiple weighted distributions into a single distribution.
--
-- The probability of each element is the weighted sum of the element's
-- probability in every distribution.
--
--
-- >>> combine [(always 2, 1 / 3), (uniform [1..6], 2 / 3)]
-- fromList [(1,1 % 9),(2,4 % 9),(3,1 % 9),(4,1 % 9),(5,1 % 9),(6,1 % 9)]
--
--
-- Note that the weights do not have to sum up to 1.
-- Distributions with negative or null weight will be ignored.
combine :: (Ord a, Real p) => [(Distribution a, p)] -> Distribution a
-- | Binomial distribution. Assigns to each number of successes its
-- probability.
--
--
-- >>> trials 2 $ uniform [True, False]
-- fromList [(0,1 % 4),(1,1 % 2),(2,1 % 4)]
--
trials :: Int -> Distribution Bool -> Distribution Int
-- | Takes n samples from the distribution and returns the
-- distribution of their sum.
--
--
-- >>> times 2 $ uniform [1 .. 3]
-- fromList [(2,1 % 9),(3,2 % 9),(4,1 % 3),(5,2 % 9),(6,1 % 9)]
--
--
-- This function makes use of the more efficient trials
-- functions for input distributions of size 2.
--
--
-- >>> size $ times 10000 $ uniform [1, 10]
-- 10001
--
times :: (Num a, Ord 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.
--
--
-- >>> uniform [1 .. 3] `andThen` (\ n -> uniform [1 .. n])
-- fromList [(1,11 % 18),(2,5 % 18),(3,1 % 9)]
--
--
-- See the on function for a convenient way to chain
-- distributions.
andThen :: Ord b => Distribution a -> (a -> Distribution b) -> Distribution b
-- | Utility to partially apply a function on a distribution. A use case
-- for on is to use it in conjunction with andThen to
-- combine distributions.
--
--
-- >>> uniform [1 .. 3] `andThen` (+) `on` uniform [1 .. 2]
-- fromList [(2,1 % 6),(3,1 % 3),(4,1 % 3),(5,1 % 6)]
--
on :: Ord c => (a -> b -> c) -> Distribution b -> a -> Distribution c
instance Eq a => Eq (Distribution a)
instance (Ord a, Monoid a) => Monoid (Distribution a)
instance (Ord a, Floating a) => Floating (Distribution a)
instance (Ord a, Fractional a) => Fractional (Distribution a)
instance (Ord a, Num a) => Num (Distribution a)
instance Bounded a => Bounded (Distribution a)
instance Ord a => Ord (Distribution a)
instance Show a => Show (Distribution a)
-- | This modules provides various measures on finite discrete probability
-- distributions.
module Data.Distribution.Measure
-- | Probability that a predicate holds on the distribution.
--
--
-- >>> probability (\ x -> x == 1 || x == 6) $ uniform [1 .. 6]
-- 1 % 3
--
--
-- Takes O(n) time. See probabilityAt and
-- probabilityIn for a more efficient ways to query elements and
-- ranges.
probability :: (a -> Bool) -> Distribution a -> Probability
-- | Probability of a given value.
--
-- Takes O(log(n)) time.
probabilityAt :: Ord a => a -> Distribution a -> Probability
-- | Probability of a the inclusive [low, high] range. When
-- low > high, the probability is 0.
--
-- Takes O(log(n) + m) time, where n is the size of the
-- distribution and m the size of the range.
probabilityIn :: Ord a => (a, a) -> Distribution a -> Probability
-- | Returns the expectation, or mean, of a distribution.
--
--
-- >>> expectation $ uniform [0, 1]
-- 0.5
--
--
-- Empty distributions have an expectation of 0.
expectation :: (Real a, Fractional b) => Distribution a -> b
-- | Synonym of expectation.
mean :: (Real a, Fractional b) => Distribution a -> b
-- | Returns the variance of a distribution.
--
--
-- >>> variance $ always 1
-- 0.0
--
-- >>> variance $ uniform [0 .. 1]
-- 0.25
--
-- >>> variance $ uniform [1 .. 7]
-- 4.0
--
--
-- Empty distributions have a variance of 0.
variance :: (Real a, Fractional b) => Distribution a -> b
-- | Standard deviation.
--
--
-- >>> standardDeviation $ always 1
-- 0.0
--
-- >>> standardDeviation $ uniform [0 .. 1]
-- 0.5
--
-- >>> standardDeviation $ uniform [1 .. 7]
-- 2.0
--
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.
--
--
-- >>> median $ fromList [(1, 0.6), (2, 0.4)]
-- Just 1
--
-- >>> median $ fromList [(1, 0.4), (2, 0.6)]
-- Just 2
--
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 p of the values are less or equal to it.
--
--
-- >>> quantile 0.0 $ uniform [1, 2, 3]
-- Just 1
--
-- >>> quantile 0.5 $ uniform [1, 2, 3]
-- Just 2
--
-- >>> quantile 1.0 $ uniform [1, 2, 3]
-- Just 3
--
-- >>> quantile 0.5 $ fromList []
-- Nothing
--
quantile :: Probability -> Distribution a -> Maybe 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
-- x and the second on values greater than x. Potential
-- probability at x 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.
--
--
-- >>> aggregateWith cumulative $ toList $ uniform [1 .. 5]
-- [(1,1 % 5),(2,2 % 5),(3,3 % 5),(4,4 % 5),(5,1 % 1)]
--
cumulative :: Aggregator a
-- | Adds to each probability the sum of probabilities later in the list.
--
--
-- >>> aggregateWith decreasing $ toList $ uniform [1 .. 5]
-- [(1,1 % 1),(2,4 % 5),(3,3 % 5),(4,2 % 5),(5,1 % 5)]
--
decreasing :: Aggregator a
-- | Replaces each probability by its complement.
--
--
-- >>> aggregateWith complementary $ toList $ uniform [1 .. 5]
-- [(1,4 % 5),(2,4 % 5),(3,4 % 5),(4,4 % 5),(5,4 % 5)]
--
complementary :: Aggregator a
instance Monoid (Aggregator a)
-- | This modules provides ways to randomly and efficiently sample values
-- from distributions.
--
-- Walker's alias method is used internally, so that values can be
-- sampled in constant time.
module Data.Distribution.Sample
-- | Generator of random values of type a.
--
-- 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 O(n) time where n is the size of the
-- distribution.
fromDistribution :: Distribution a -> Generator a
-- | Safe version of fromDistribution. Returns Nothing when
-- the given distribution is empty.
safeFromDistribution :: Distribution a -> Maybe (Generator a)
-- | Picks a random value from the generator.
--
-- Runs in constant O(1) time.
sample :: RandomGen g => Generator a -> g -> (a, g)
-- | Picks a random value from the generator.
--
-- Runs in constant O(1) time.
getSample :: MonadRandom m => Generator a -> m a
instance Functor Generator
-- | 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 n 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 Eq CoinSide
instance Ord CoinSide
instance Show CoinSide
instance Read CoinSide
instance Enum 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 n faces.
dice :: Int -> Dice
-- | Fair dice of 4 faces.
d4 :: Dice
-- | Fair dice of 6 faces.
d6 :: Dice
-- | Fair dice of 8 faces.
d8 :: Dice
-- | Fair dice of 10 faces.
d10 :: Dice
-- | Fair dice of 20 faces.
d20 :: Dice
-- | Rolls n 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 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