Data.Random.Shuffle.Weighted

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.

Shuffling

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

Randomly shuffle a CDF map according to its weights.

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

Randomly shuffle a weighted list according to its weights.

Sampling

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

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

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

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

Extraction

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

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, Eq w) => [(w, a)] -> Map w a

Generate a CDF map from a weighted list.