packages feed

random-extras 0.10 → 0.11

raw patch · 3 files changed

+206/−206 lines, 3 files

Files

− Control/Monad/Random/Extras.hs 
@@ -1,203 +0,0 @@-{-# LANGUAGE FlexibleContexts #-}--{- |-Module       : Control.Monad.Random.Extras-Copyright    : 2010 Aristid Breitkreuz-License      : BSD3-Stability    : experimental-Portability  : portable--Additional monadic random functions, based on random-fu.--}--module Control.Monad.Random.Extras-(-  -- * Random functions-  -- ** Shuffling-  shuffle-, shuffleSeq-  -- ** Sampling-, sample-, sampleSeq-  -- ** Choice-, choiceExtract-, choiceExtractSeq-, choice-, safeChoice-, iterativeChoice-, choiceSeq-, safeChoiceSeq-, choiceArray-  -- ** Choices-, choices-, safeChoices-, choicesArray-)-where--import Control.Monad-import Data.Random.RVar-import Data.Random.Distribution-import Data.Random.Distribution.Uniform-import Data.List-import Data.Maybe-import qualified Data.Sequence as Seq-import Data.Sequence ((><), ViewL((:<)))-import qualified Data.Array.IArray as Arr-import qualified Data.Array-import Data.Array.IArray ((!))--(.:) :: (c -> c') -> (a -> b -> c) -> (a -> b -> c')-(.:) = (.).(.)--extract :: [a] -> Int -> Maybe ([a], a)-extract s i | null r    = Nothing-            | otherwise = Just (a ++ c, b)-    where (a, r) = splitAt i s-          (b : c) = r--extractSeq :: Seq.Seq a -> Int -> Maybe (Seq.Seq a, a)-extractSeq s i | Seq.null r = Nothing-               | otherwise  = Just (a >< c, b)-    where (a, r) = Seq.splitAt i s -          (b :< c) = Seq.viewl r--backsaw :: Int -> [Int]-backsaw n = [n - 1, n - 2 .. 0]-          --- Shuffling---- | 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 = 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), where /n/ is the length of the input sequence.-shuffleSeq :: Seq.Seq a -> RVar [a]-shuffleSeq s = do-  samples <- mapM (uniform 0) . backsaw $ Seq.length s-  return (shuffleSeq' s samples)--shuffleSeq' :: Seq.Seq a -> [Int] -> [a]-shuffleSeq' = snd .: mapAccumL (fromJust .: extractSeq)---- Sampling---- | 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]-sample m = sampleSeq m . Seq.fromList---- | 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.Seq a -> RVar [a]-sampleSeq m s = do-  samples <- mapM (uniform 0) . take m . backsaw $ Seq.length s-  return (shuffleSeq' s samples)---- Choice---- | 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))-choiceExtract [] = Nothing-choiceExtract xs = Just $ (fromJust . extract xs) `liftM` uniform 0 (length xs - 1)-                    --- | Randomly choose and extract an element from a sequence.--- --- /Complexity:/ O(log n), where /n/ is the length of the input sequence.-choiceExtractSeq :: Seq.Seq a -> Maybe (RVar (Seq.Seq a, a))-choiceExtractSeq s | Seq.null s = Nothing-                   | otherwise  = Just $ (fromJust . extractSeq s) `liftM` uniform 0 (Seq.length s - 1)---- | 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-choice [] = error "Control.Monad.Random.Extras.choice: empty list"-choice xs = (xs !!) `liftM` uniform 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 :: [a] -> Maybe (RVar 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 :: [a] -> RVar a-iterativeChoice xs = fst `liftM` foldl' stepM (return start) xs-    where stepM x y = x >>= step y-          step offered (old, n) = do-            i <- uniform 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.--- --- /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.Seq a -> RVar a-choiceSeq s | Seq.null s = error "Control.Monad.Random.Extras.choiceSeq: empty sequence"-            | otherwise  = Seq.index s `liftM` uniform 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 :: Seq.Seq a -> Maybe (RVar a)-safeChoiceSeq s | Seq.null s = Nothing-                | otherwise  = Just $ choiceSeq s---- | Select a random element from an array.--- --- /Complexity:/ O(1).-choiceArray :: (Arr.IArray arr a, Arr.Ix i, Distribution Uniform i) => arr i a -> RVar a-choiceArray v = (v !) `liftM` uncurry uniform (Arr.bounds v)---- Choices---- | 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]-choices _ [] = error "Control.Monad.Random.Extras.choices: empty list"-choices n xs = choicesArray n $ 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 :: Int -> [a] -> Maybe (RVar [a])-safeChoices _ [] = Nothing-safeChoices n xs = Just $ choices n xs---- | A stream of random elements from an array.------ /Complexity:/ O(1) per element.-choicesArray :: (Arr.IArray arr a, Arr.Ix i, Distribution Uniform i) => Int -> arr i a -> RVar [a]-choicesArray n v = map (v !) `liftM` replicateM n (uncurry uniform (Arr.bounds v))
+ Data/Random/Extras.hs view
@@ -0,0 +1,203 @@+{-# LANGUAGE FlexibleContexts #-}++{- |+Module       : Control.Monad.Random.Extras+Copyright    : 2010 Aristid Breitkreuz+License      : BSD3+Stability    : experimental+Portability  : portable++Additional monadic random functions, based on random-fu.+-}++module Data.Random.Extras+(+  -- * Random functions+  -- ** Shuffling+  shuffle+, shuffleSeq+  -- ** Sampling+, sample+, sampleSeq+  -- ** Choice+, choiceExtract+, choiceExtractSeq+, choice+, safeChoice+, iterativeChoice+, choiceSeq+, safeChoiceSeq+, choiceArray+  -- ** Choices+, choices+, safeChoices+, choicesArray+)+where++import Control.Monad+import Data.Random.RVar+import Data.Random.Distribution+import Data.Random.Distribution.Uniform+import Data.List+import Data.Maybe+import qualified Data.Sequence as Seq+import Data.Sequence ((><), ViewL((:<)))+import qualified Data.Array.IArray as Arr+import qualified Data.Array+import Data.Array.IArray ((!))++(.:) :: (c -> c') -> (a -> b -> c) -> (a -> b -> c')+(.:) = (.).(.)++extract :: [a] -> Int -> Maybe ([a], a)+extract s i | null r    = Nothing+            | otherwise = Just (a ++ c, b)+    where (a, r) = splitAt i s+          (b : c) = r++extractSeq :: Seq.Seq a -> Int -> Maybe (Seq.Seq a, a)+extractSeq s i | Seq.null r = Nothing+               | otherwise  = Just (a >< c, b)+    where (a, r) = Seq.splitAt i s +          (b :< c) = Seq.viewl r++backsaw :: Int -> [Int]+backsaw n = [n - 1, n - 2 .. 0]+          +-- Shuffling++-- | 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 = 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), where /n/ is the length of the input sequence.+shuffleSeq :: Seq.Seq a -> RVar [a]+shuffleSeq s = do+  samples <- mapM (uniform 0) . backsaw $ Seq.length s+  return (shuffleSeq' s samples)++shuffleSeq' :: Seq.Seq a -> [Int] -> [a]+shuffleSeq' = snd .: mapAccumL (fromJust .: extractSeq)++-- Sampling++-- | 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]+sample m = sampleSeq m . Seq.fromList++-- | 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.Seq a -> RVar [a]+sampleSeq m s = do+  samples <- mapM (uniform 0) . take m . backsaw $ Seq.length s+  return (shuffleSeq' s samples)++-- Choice++-- | 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))+choiceExtract [] = Nothing+choiceExtract xs = Just $ (fromJust . extract xs) `liftM` uniform 0 (length xs - 1)+                    +-- | Randomly choose and extract an element from a sequence.+-- +-- /Complexity:/ O(log n), where /n/ is the length of the input sequence.+choiceExtractSeq :: Seq.Seq a -> Maybe (RVar (Seq.Seq a, a))+choiceExtractSeq s | Seq.null s = Nothing+                   | otherwise  = Just $ (fromJust . extractSeq s) `liftM` uniform 0 (Seq.length s - 1)++-- | 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+choice [] = error "Control.Monad.Random.Extras.choice: empty list"+choice xs = (xs !!) `liftM` uniform 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 :: [a] -> Maybe (RVar 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 :: [a] -> RVar a+iterativeChoice xs = fst `liftM` foldl' stepM (return start) xs+    where stepM x y = x >>= step y+          step offered (old, n) = do+            i <- uniform 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.+-- +-- /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.Seq a -> RVar a+choiceSeq s | Seq.null s = error "Control.Monad.Random.Extras.choiceSeq: empty sequence"+            | otherwise  = Seq.index s `liftM` uniform 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 :: Seq.Seq a -> Maybe (RVar a)+safeChoiceSeq s | Seq.null s = Nothing+                | otherwise  = Just $ choiceSeq s++-- | Select a random element from an array.+-- +-- /Complexity:/ O(1).+choiceArray :: (Arr.IArray arr a, Arr.Ix i, Distribution Uniform i) => arr i a -> RVar a+choiceArray v = (v !) `liftM` uncurry uniform (Arr.bounds v)++-- Choices++-- | 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]+choices _ [] = error "Control.Monad.Random.Extras.choices: empty list"+choices n xs = choicesArray n $ 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 :: Int -> [a] -> Maybe (RVar [a])+safeChoices _ [] = Nothing+safeChoices n xs = Just $ choices n xs++-- | A stream of random elements from an array.+--+-- /Complexity:/ O(1) per element.+choicesArray :: (Arr.IArray arr a, Arr.Ix i, Distribution Uniform i) => Int -> arr i a -> RVar [a]+choicesArray n v = map (v !) `liftM` replicateM n (uncurry uniform (Arr.bounds v))
random-extras.cabal view
@@ -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.10+Version:             0.11  -- A short (one-line) description of the package. Synopsis:            Additional functions for random values.@@ -34,7 +34,7 @@ -- A copyright notice. -- Copyright:            -Category:            Control+Category:            Data, Math  Build-type:          Simple @@ -49,7 +49,7 @@ Library   -- Modules exported by the library.   Exposed-modules:-        Control.Monad.Random.Extras+        Data.Random.Extras      -- Packages needed in order to build this package.   Build-depends: