random-extras-0.16: Additional functions for random values.

Portabilityportable
Stabilityexperimental

Data.Random.Shuffle.Weighted

Contents

Description

Functions for shuffling elements according to weights.

Definitions:

Weight
A number above 0 denoting how likely it is for an element to end up in the first position.
Probability
A weight normalised into the (0,1] range.
Weighted list
A list of pairs (w, a), where w is the weight of element a. The probability of an element getting into the first position is equal by its weight divided by the sum of all weights, and the probability of getting into a position other than the first is equal to the probability of getting in the first position when all elements in prior positions have been removed from the weighted list.
CDF Map
A map of summed weights to elements. For example, a weighted list [(0.2, a), (0.6, b), (0.2, c)] corresponds to a CDF map of [(0.2, a), (0.8, b), (1.0, c)] (as a Map). The weights are summed from left to right.

Synopsis

Shuffling

weightedShuffleCDF :: (Num w, Ord w, Distribution Uniform w) => Map w a -> RVar [a]Source

Randomly shuffle a CDF map according to its weights.

weightedShuffle :: (Num w, Ord w, Distribution Uniform w) => [(w, a)] -> RVar [a]Source

Randomly shuffle a weighted list according to its weights.

Sampling

weightedSampleCDF :: (Num w, Ord w, Distribution Uniform w) => Int -> Map w a -> RVar [a]Source

Randomly draw n elements from a CDF map according to its weights.

weightedSample :: (Num w, Ord w, Distribution Uniform w) => Int -> [(w, a)] -> RVar [a]Source

Randomly draw n elements from a weighted list according to its weights.

Extraction

weightedChoiceExtractCDF :: (Num w, Ord w, Distribution Uniform w) => Map w a -> RVar (Map w a, a)Source

Randomly extract an element from a CDF map according to its weights. The element is removed and the resulting weight gap closed.

Utilities

cdfMapFromList :: Num w => [(w, a)] -> Map w aSource

Generate a CDF map from a weighted list.