-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Additional functions for random values. -- -- Additional functions for random values, based on random-fu. Inspired -- by random-shuffle. @package random-extras @version 0.16 -- | Functions for shuffling elements according to weights. -- -- Definitions: -- -- module Data.Random.Shuffle.Weighted -- | Randomly shuffle a CDF map according to its weights. weightedShuffleCDF :: (Num w, Ord w, Distribution Uniform w) => Map w a -> RVar [a] -- | Randomly shuffle a weighted list according to its weights. weightedShuffle :: (Num w, Ord w, Distribution Uniform w) => [(w, a)] -> RVar [a] -- | Randomly draw n elements from a CDF map according to its -- weights. weightedSampleCDF :: (Num w, Ord w, Distribution Uniform w) => Int -> Map w a -> RVar [a] -- | Randomly draw n elements from a weighted list according to its -- weights. weightedSample :: (Num w, Ord w, Distribution Uniform w) => Int -> [(w, a)] -> RVar [a] -- | Randomly extract an element from a CDF map according to its weights. -- The element is removed and the resulting weight gap closed. weightedChoiceExtractCDF :: (Num w, Ord w, Distribution Uniform w) => Map w a -> RVar (Map w a, a) -- | Generate a CDF map from a weighted list. cdfMapFromList :: (Num w) => [(w, a)] -> Map w a -- | Additional monadic random functions, based on random-fu. module Data.Random.Extras -- | 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. shuffle :: [a] -> RVar [a] -- | 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. shuffleSeq :: Seq a -> RVar [a] -- | 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. sample :: Int -> [a] -> RVar [a] -- | 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. sampleSeq :: Int -> Seq a -> RVar [a] -- | Randomly choose and extract an element from a list. -- -- Complexity: O(n), where n is the length of the input -- list. choiceExtract :: [a] -> Maybe (RVar ([a], a)) -- | Randomly choose and extract an element from a sequence. -- -- Complexity: O(log n), where n is the length of the input -- sequence. choiceExtractSeq :: Seq a -> Maybe (RVar (Seq a, a)) -- | 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. choice :: [a] -> RVar a -- | Safely select a random element from a list. -- -- Complexity: O(n), where n is the length of the input -- list. safeChoice :: [a] -> Maybe (RVar a) -- | 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. iterativeChoice :: [a] -> RVar a -- | 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. choiceSeq :: Seq a -> RVar a -- | Safely select a random element from a sequence. -- -- Complexity: O(log n), where n is the length of the input -- sequence. safeChoiceSeq :: Seq a -> Maybe (RVar a) -- | Select a random element from an array. -- -- Complexity: O(1). choiceArray :: (IArray arr a, Ix i, Distribution Uniform i) => arr i a -> RVar a -- | 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. choices :: Int -> [a] -> RVar [a] -- | 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. safeChoices :: Int -> [a] -> Maybe (RVar [a]) -- | A stream of random elements from an array. -- -- Complexity: O(1) per element. choicesArray :: (IArray arr a, Ix i, Distribution Uniform i) => Int -> arr i a -> RVar [a] -- | Functions for splitting a deck of cards like game players. -- -- Decks are represented by Seqs, because these efficiently -- support the required operations. -- -- module Data.Random.Dovetail -- | Split a deck into two roughly equal halves. splitDeck :: Seq a -> RVar (Seq a, Seq a) -- | Split a deck into n roughly equal parts. generalizedSplitDeck :: Int -> Seq a -> RVar [Seq a] -- | Riffle two halves of a deck into one deck. riffleDecks :: Seq a -> Seq a -> RVar (Seq a) -- | Riffle n parts into one deck. generalizedRiffleDecks :: [Seq a] -> RVar (Seq a) -- | Perform an inverse riffle, i.e. letting the cards from a deck drop -- randomly into two heaps. inverseRiffleDecks :: Seq a -> RVar (Seq a, Seq a) -- | Perform an inverse riffle, i.e. letting the cards from a deck drop -- randomly into n heaps. generalizedInverseRiffleDecks :: Int -> Seq a -> RVar (Seq (Seq a)) -- | Dovetail shuffle a deck, i.e. split the deck with splitDeck and riffle -- the resulting halves with riffleDecks. dovetail :: Seq a -> RVar (Seq a) -- | Dovetail shuffle a deck (generalized), i.e. split the deck into -- n parts and riffle them back together. generalizedDovetail :: Int -> Seq a -> RVar (Seq a) -- | Dovetail shuffle a deck repeatedly for n times. dovetails :: Int -> Seq a -> RVar (Seq a) -- | Dovetail shuffle a deck repeatedly for shuffles times, using -- parts parts. -- -- Invocation: generalizedDovetails shuffles parts deck generalizedDovetails :: Int -> Int -> Seq a -> RVar (Seq a) -- | Perform an inverse dovetail shuffle, i.e. letting the cards from a -- deck drop randomly into two heaps and then stack these heaps. inverseDovetail :: Seq a -> RVar (Seq a) -- | Perform a generalized inverse dovetail shuffle, i.e. letting the cards -- from a deck drop randomly into n heaps and then stack them back -- together. generalizedInverseDovetail :: Int -> Seq a -> RVar (Seq a) -- | Perform a face up, face down shuffle, which is like a dovetail -- shuffle where the lower of the two halves is reversed. faceUpFaceDown :: Seq a -> RVar (Seq a)