-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A Haskell library for probability distributions
--
-- This library provides a data structure and associated functions for
-- representing discrete probability distributions.
@package Dist
@version 0.4.2
-- | This module provides a data structure and associated functions for
-- representing discrete probability distributions.
--
-- All time and space complexity metrics are given in terms of
-- n. In this case, n refers to the number of unique
-- outcomes inserted into the tree. If one were to construct a tree by
-- inserting a billion of the same outcome, n would still be 1.
--
-- The data structure is optimized for fast sampling from the
-- distribution. Sampling ranges from O(1) to O(log(n))
-- depending on the distribution.
--
-- Under the hood, the distribution is represented by a perfectly
-- balanced binary tree. The tree enforces a heap property, where more
-- likely outcomes are closer to the top than less likely outcomes.
-- Because we're more likely to sample from those outcomes, we minimize
-- the amount of time spent traversing the tree.
--
-- When a duplicate outcome is inserted into the tree, the tree's "dups"
-- counter is incremented. When more than half the tree is duplicate
-- entries, the entire tree is rebuilt from scratch. Using amortized
-- complexity analysis, we can show that insertion is, at worst,
-- log(n) amortized complexity. This prevents the size of tree
-- from increasing to more than O(n), even with many duplicate
-- outcomes inserted.
module Numeric.Probability.Distribution
-- | A probability distribution with probabilities of type p and
-- outcomes/events of type o.
data Distribution p o
-- | Take a sample from the distribution. Can be used with e.g.
-- evalRand or evalRandIO from
-- Control.Monad.Random. O(log(n)) for a uniform
-- distribution (worst case), but approaches O(1) with less
-- balanced distributions.
sample :: (Ord p, Num p, Random p, MonadRandom m) => Distribution p o -> m o
-- | The sum of all probabilities in the distribution. O(1)
cumulate :: Num p => Distribution p o -> p
-- | Normalizes the distribution. After normalizing, cumulate
-- distribution is 1. O(n)
normalize :: Fractional p => Distribution p o -> Distribution p o
-- | Given an outcome, returns the probability. Note that the probability
-- is not always normalized. If you want the probability to be in the 0-1
-- range, you should divide it by cumulate dist (the sum of the
-- probability of all outcomes)
lookup :: (Ord o, Num p) => Distribution p o -> o -> p
-- | The empty distribution. O(1)
empty :: Num p => Distribution p o
-- | Insert an outcome into the distribution. Inserting (o,p1) and
-- (o,p2) results in the same sampled distribution as inserting
-- (o,p1+p2). O(log(n)) amortized.
insert :: (Ord o, Num p, Ord p) => (o, p) -> Distribution p o -> Distribution p o
-- |
-- O(n*log(n))
--
fromList :: (Ord o, Num p, Ord p) => [(o, p)] -> Distribution p o
-- | Reweights the probabilities in the distribution based on the given
-- function. n*log(n)
reweight :: (Ord o, Num p, Ord p) => ((o, p) -> p) -> Distribution p o -> Distribution p o
-- |
-- O(n*log(n))
--
toList :: (Ord o, Num p) => Distribution p o -> [(o, p)]
-- | A right-associative fold on the tree structure, including the
-- probabilities. Note that outcomes may be repeated within the data
-- structure. If you want identical outcomes to be lumped together, fold
-- on the list produced by toList. O(n).
foldrWithP :: ((o, p) -> b -> b) -> b -> Distribution p o -> b
-- | Creates a new distribution that's the joint distribution of the two
-- provided. O(nm*log(nm)) amortized.
joint :: (Ord o1, Ord o2, Num p, Ord p) => Distribution p o1 -> Distribution p o2 -> Distribution p (o1, o2)
-- | Creates a new distribution by summing the probabilities of the
-- outcomes in the two provided. O((n+m)log(n+m)) amortized.
sum :: (Ord o, Num p, Ord p) => Distribution p o -> Distribution p o -> Distribution p o
-- | A series of tests on the internal structure of the distribution. For
-- debugging purposes.
invariants :: (Num p, Ord p, Show p, Ord e, Show e) => Distribution p e -> Either String ()
instance (GHC.Num.Num p, GHC.Show.Show p, GHC.Classes.Ord o, GHC.Show.Show o) => GHC.Show.Show (Numeric.Probability.Distribution.Distribution p o)