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

Portability portable experimental

Contents

Description

Additional monadic random functions, based on `MonadRandom`.

Synopsis

# Random functions

## Shuffling

shuffle :: MonadRandom m => [a] -> m [a]Source

Shuffle a list randomly. The method is based on Oleg Kiselyov's perfect shuffle http://okmij.org/ftp/Haskell/perfect-shuffle.txt, but much simpler because it uses existing data structures. The efficiency of both methods should be comparable.

Complexity: O(n * log n), where n is the length of the input list.

shuffleSeq :: MonadRandom m => Seq a -> m [a]Source

Shuffle a sequence randomly. This is being used by `shuffle`, so it logically uses the same method.

Complexity: O(n * log n), where n is the length of the input sequence.

## Sampling

sample :: MonadRandom m => Int -> [a] -> m [a]Source

Take a random sample from a list.

Complexity: O(n + m * log n), where n is the length of the input list and m is the sample size.

sampleSeq :: MonadRandom m => Int -> Seq a -> m [a]Source

Take a random sample from a sequence.

Complexity: O(m * log n), where n is the length of the input sequence and m is the sample size.

## Choice

choiceExtract :: MonadRandom m => [a] -> m (Maybe ([a], a))Source

Randomly choose and extract an element from a list.

Complexity: O(n), where n is the length of the input list.

choiceExtractSeq :: MonadRandom m => Seq a -> m (Maybe (Seq a, a))Source

Randomly choose and extract an element from a sequence.

Complexity: O(log n), where n is the length of the input sequence.

choice :: MonadRandom m => [a] -> m aSource

Select a random element from a list.

Partial function: This function is only defined on non-empty lists.

Complexity: O(n), where n is the length of the input list.

safeChoice :: MonadRandom m => [a] -> Maybe (m a)Source

Safely select a random element from a list.

Complexity: O(n), where n is the length of the input list.

iterativeChoice :: MonadRandom m => [a] -> m aSource

Select a random element from a list, traversing the list only once.

Partial function: This function is only defined on non-empty lists with a length below (`maxBound` + 1 :: Int).

Complexity: O(n), where n is the length of the input list.

choiceSeq :: MonadRandom m => Seq a -> m aSource

Select a random element from a sequence.

Partial function: This function is only defined on non-empty sequences.

Complexity: O(log n), where n is the length of the input sequence.

safeChoiceSeq :: MonadRandom m => Seq a -> Maybe (m a)Source

Safely select a random element from a sequence.

Complexity: O(log n), where n is the length of the input sequence.

choiceArray :: (MonadRandom m, IArray arr a, Ix i, Random i) => arr i a -> m aSource

Select a random element from an array.

Complexity: O(1).

## Choices

choices :: MonadRandom m => [a] -> m [a]Source

A stream of random elements from a list.

Partial function: This function is only defined on non-empty lists.

Complexity: O(n) base and O(1) per element.

safeChoices :: MonadRandom m => [a] -> Maybe (m [a])Source

Safely get a stream of random elements from a list.

Complexity: O(n) base and O(1) per element, where n is the length of the input list.

choicesArray :: (MonadRandom m, IArray arr a, Ix i, Random i) => arr i a -> m [a]Source

A stream of random elements from an array.

Complexity: O(1) per element.