random-extras 0.3 → 0.4

raw patch · 2 files changed

+71/−19 lines, 2 files

Files

• Control/Monad/Random/Extras.hs +70/−18
• random-extras.cabal +1/−1

@@ -23,10 +23,14 @@ , choiceExtract , choiceExtractSeq , choice+, safeChoice+, iterativeChoice , choiceSeq+, safeChoiceSeq , choiceArray   -- ** Choices , choices+, safeChoices , choicesArray ) where@@ -34,7 +38,7 @@ import Control.Monad (liftM) import Control.Monad.Random (MonadRandom, getRandomR, getRandomRs) import System.Random (Random)-import Data.List (mapAccumL)+import Data.List (mapAccumL, foldl') import Data.Maybe (fromJust) import qualified Data.Sequence as Seq import Data.Sequence ((><), ViewL((:<)))@@ -73,14 +77,14 @@ -- but much simpler because it uses existing data structures. The efficiency -- of both methods should be comparable. ----- Complexity: O(n * log n)+-- /Complexity:/ O(n * log n), where /n/ is the length of the input list. shuffle :: (MonadRandom m) => [a] -> m [a] shuffle = shuffleSeq . Seq.fromList  -- | Shuffle a sequence randomly. This is being used by 'shuffle', -- so it logically uses the same method. ----- Complexity: O(n * log n)+-- /Complexity:/ O(n * log n), where /n/ is the length of the input sequence. shuffleSeq :: (MonadRandom m) => Seq.Seq a -> m [a] shuffleSeq s = do   samples <- getRandomRNums . backsaw $ Seq.length s@@ -93,13 +97,15 @@  -- | Take a random sample from a list. -- --- Complexity: O(n + m * log n)+-- /Complexity:/ O(n + m * log n), where /n/ is the length of the input list +-- and /m/ is the sample size. sample :: (MonadRandom m) => Int -> [a] -> m [a] sample m = sampleSeq m . Seq.fromList  -- | Take a random sample from a sequence. -- --- Complexity: O(m * log n)+-- /Complexity:/ O(m * log n), where /n/ is the length of the input sequence +-- and /m/ is the sample size. sampleSeq :: (MonadRandom m) => Int -> Seq.Seq a -> m [a] sampleSeq m s = do   samples <- getRandomRNums . take m . backsaw $ Seq.length s@@ -108,49 +114,95 @@ -- Choice  -- | Randomly choose and extract an element from a list.------ Complexity: O(n)+-- +-- /Complexity:/ O(n), where /n/ is the length of the input list. choiceExtract :: (MonadRandom m) => [a] -> m (Maybe ([a], a)) choiceExtract [] = return Nothing choiceExtract xs = extract xs `liftM` getRandomR (0, length xs - 1)                      -- | Randomly choose and extract an element from a sequence.------ Complexity: O(log n)+-- +-- /Complexity:/ O(log n), where /n/ is the length of the input sequence. choiceExtractSeq :: (MonadRandom m) => Seq.Seq a -> m (Maybe (Seq.Seq a, a)) choiceExtractSeq s | Seq.null s = return Nothing                    | otherwise  = extractSeq s `liftM` getRandomR (0, Seq.length s - 1)  -- | Select a random element from a list.------ Complexity: O(n).+-- +-- /Partial function:/ This function is only defined on non-empty lists.+-- +-- /Complexity:/ O(n), where /n/ is the length of the input list. choice :: (MonadRandom m) => [a] -> m a choice [] = error "Control.Monad.Random.Extras.choice: empty list" choice xs = (xs !!) `liftM` getRandomR (0, length xs - 1) +-- | Safely select a random element from a list.+-- +-- /Complexity:/ O(n), where /n/ is the length of the input list.+safeChoice :: (MonadRandom m) => [a] -> Maybe (m a)+safeChoice [] = Nothing+safeChoice xs = Just $ choice xs++-- | 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 :: MonadRandom m => [a] -> m a+iterativeChoice xs = fst `liftM` foldl' stepM (return start) xs+    where stepM x y = x >>= step y+          step offered (old, n) = do+            i <- getRandomR (0, n)+            let new | i == 0    = offered+                    | otherwise = old+            return $! new `seq` (new, n + 1)+          start = (err, 0 :: Int)+          err = error "Control.Monad.Random.Extras.iterativeChoice: empty list"+ -- | Select a random element from a sequence.------ Complexity: O(log n).+-- +-- /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 :: (MonadRandom m) => Seq.Seq a -> m a choiceSeq s | Seq.null s = error "Control.Monad.Random.Extras.choiceSeq: empty sequence"             | otherwise  = Seq.index s `liftM` getRandomR (0, Seq.length s - 1)+                           +-- | Safely select a random element from a sequence.+-- +-- /Complexity:/ O(log n), where /n/ is the length of the input sequence.+safeChoiceSeq :: (MonadRandom m) => Seq.Seq a -> Maybe (m a)+safeChoiceSeq s | Seq.null s = Nothing+                | otherwise  = Just $ choiceSeq s  -- | Select a random element from an array.------ Complexity: O(1).+-- +-- /Complexity:/ O(1). choiceArray :: (MonadRandom m, Arr.IArray arr a, Arr.Ix i, Random i) => arr i a -> m a choiceArray v = (v !) `liftM` getRandomR (Arr.bounds v)  -- Choices  -- | A stream of random elements from a list.------ Complexity: O(n) base and O(1) per element+-- +-- /Partial function:/ This function is only defined on non-empty lists.+-- +-- /Complexity:/ O(n) base and O(1) per element. choices :: (MonadRandom m) => [a] -> m [a]+choices [] = error "Control.Monad.Random.Extras.choices: empty list" choices xs = choicesArray $ Data.Array.listArray (1, length xs) xs +-- | 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 :: (MonadRandom m) => [a] -> Maybe (m [a])+safeChoices [] = Nothing+safeChoices xs = Just $ choices xs+ -- | A stream of random elements from an array. ----- Complexity: O(1) per element+-- /Complexity:/ O(1) per element. choicesArray :: (MonadRandom m, Arr.IArray arr a, Arr.Ix i, Random i) => arr i a -> m [a] choicesArray v = map (v !) `liftM` getRandomRs (Arr.bounds v)

@@ -7,7 +7,7 @@ -- The package version. See the Haskell package versioning policy -- (http://www.haskell.org/haskellwiki/Package_versioning_policy) for -- standards guiding when and how versions should be incremented.-Version:             0.3+Version:             0.4  -- A short (one-line) description of the package. Synopsis:            Additional functions for random values.