permutation 0.4 → 0.4.1
raw patch · 5 files changed
+37/−5 lines, 5 filesPVP: major bump suggested
API removals or changes: PVP suggests a major version bump
API changes (from Hackage documentation)
+ Data.Permute: indexOf :: Permute -> Int -> Int
+ Data.Permute.MPermute: getIndexOf :: MPermute p m => p -> Int -> m Int
- Data.Choose.MChoose: class (Monad m) => MChoose c m | c -> m, m -> c
+ Data.Choose.MChoose: class Monad m => MChoose c m | c -> m, m -> c
- Data.Choose.MChoose: copyChoose :: (MChoose c m) => c -> c -> m ()
+ Data.Choose.MChoose: copyChoose :: MChoose c m => c -> c -> m ()
- Data.Choose.MChoose: freeze :: (MChoose c m) => c -> m Choose
+ Data.Choose.MChoose: freeze :: MChoose c m => c -> m Choose
- Data.Choose.MChoose: getComplElems :: (MChoose c m) => c -> m [Int]
+ Data.Choose.MChoose: getComplElems :: MChoose c m => c -> m [Int]
- Data.Choose.MChoose: getComplement :: (MChoose c m) => c -> m c
+ Data.Choose.MChoose: getComplement :: MChoose c m => c -> m c
- Data.Choose.MChoose: getElem :: (MChoose c m) => c -> Int -> m Int
+ Data.Choose.MChoose: getElem :: MChoose c m => c -> Int -> m Int
- Data.Choose.MChoose: getElems :: (MChoose c m) => c -> m [Int]
+ Data.Choose.MChoose: getElems :: MChoose c m => c -> m [Int]
- Data.Choose.MChoose: getPossible :: (MChoose c m) => c -> m Int
+ Data.Choose.MChoose: getPossible :: MChoose c m => c -> m Int
- Data.Choose.MChoose: getSize :: (MChoose c m) => c -> m Int
+ Data.Choose.MChoose: getSize :: MChoose c m => c -> m Int
- Data.Choose.MChoose: isValid :: (MChoose c m) => c -> m Bool
+ Data.Choose.MChoose: isValid :: MChoose c m => c -> m Bool
- Data.Choose.MChoose: newChoose :: (MChoose c m) => Int -> Int -> m c
+ Data.Choose.MChoose: newChoose :: MChoose c m => Int -> Int -> m c
- Data.Choose.MChoose: newChoose_ :: (MChoose c m) => Int -> Int -> m c
+ Data.Choose.MChoose: newChoose_ :: MChoose c m => Int -> Int -> m c
- Data.Choose.MChoose: newCopyChoose :: (MChoose c m) => c -> m c
+ Data.Choose.MChoose: newCopyChoose :: MChoose c m => c -> m c
- Data.Choose.MChoose: newListChoose :: (MChoose c m) => Int -> Int -> [Int] -> m c
+ Data.Choose.MChoose: newListChoose :: MChoose c m => Int -> Int -> [Int] -> m c
- Data.Choose.MChoose: setElem :: (MChoose c m) => c -> Int -> Int -> m ()
+ Data.Choose.MChoose: setElem :: MChoose c m => c -> Int -> Int -> m ()
- Data.Choose.MChoose: setElems :: (MChoose c m) => c -> [Int] -> m ()
+ Data.Choose.MChoose: setElems :: MChoose c m => c -> [Int] -> m ()
- Data.Choose.MChoose: setFirst :: (MChoose c m) => c -> m ()
+ Data.Choose.MChoose: setFirst :: MChoose c m => c -> m ()
- Data.Choose.MChoose: setNext :: (MChoose c m) => c -> m Bool
+ Data.Choose.MChoose: setNext :: MChoose c m => c -> m Bool
- Data.Choose.MChoose: setPrev :: (MChoose c m) => c -> m Bool
+ Data.Choose.MChoose: setPrev :: MChoose c m => c -> m Bool
- Data.Choose.MChoose: thaw :: (MChoose c m) => Choose -> m c
+ Data.Choose.MChoose: thaw :: MChoose c m => Choose -> m c
- Data.Choose.MChoose: unsafeFreeze :: (MChoose c m) => c -> m Choose
+ Data.Choose.MChoose: unsafeFreeze :: MChoose c m => c -> m Choose
- Data.Choose.MChoose: unsafeGetElem :: (MChoose c m) => c -> Int -> m Int
+ Data.Choose.MChoose: unsafeGetElem :: MChoose c m => c -> Int -> m Int
- Data.Choose.MChoose: unsafeNewListChoose :: (MChoose c m) => Int -> Int -> [Int] -> m c
+ Data.Choose.MChoose: unsafeNewListChoose :: MChoose c m => Int -> Int -> [Int] -> m c
- Data.Choose.MChoose: unsafeSetElem :: (MChoose c m) => c -> Int -> Int -> m ()
+ Data.Choose.MChoose: unsafeSetElem :: MChoose c m => c -> Int -> Int -> m ()
- Data.Choose.MChoose: unsafeThaw :: (MChoose c m) => Choose -> m c
+ Data.Choose.MChoose: unsafeThaw :: MChoose c m => Choose -> m c
- Data.Permute: order :: (Ord a) => Int -> [a] -> Permute
+ Data.Permute: order :: Ord a => Int -> [a] -> Permute
- Data.Permute: rank :: (Ord a) => Int -> [a] -> Permute
+ Data.Permute: rank :: Ord a => Int -> [a] -> Permute
- Data.Permute: sort :: (Ord a) => Int -> [a] -> ([a], Permute)
+ Data.Permute: sort :: Ord a => Int -> [a] -> ([a], Permute)
- Data.Permute.MPermute: class (Monad m) => MPermute p m | p -> m, m -> p
+ Data.Permute.MPermute: class Monad m => MPermute p m | p -> m, m -> p
- Data.Permute.MPermute: copyInverse :: (MPermute p m) => p -> p -> m ()
+ Data.Permute.MPermute: copyInverse :: MPermute p m => p -> p -> m ()
- Data.Permute.MPermute: copyPermute :: (MPermute p m) => p -> p -> m ()
+ Data.Permute.MPermute: copyPermute :: MPermute p m => p -> p -> m ()
- Data.Permute.MPermute: freeze :: (MPermute p m) => p -> m Permute
+ Data.Permute.MPermute: freeze :: MPermute p m => p -> m Permute
- Data.Permute.MPermute: getCycleFrom :: (MPermute p m) => p -> Int -> m [Int]
+ Data.Permute.MPermute: getCycleFrom :: MPermute p m => p -> Int -> m [Int]
- Data.Permute.MPermute: getCycles :: (MPermute p m) => p -> m [[Int]]
+ Data.Permute.MPermute: getCycles :: MPermute p m => p -> m [[Int]]
- Data.Permute.MPermute: getElem :: (MPermute p m) => p -> Int -> m Int
+ Data.Permute.MPermute: getElem :: MPermute p m => p -> Int -> m Int
- Data.Permute.MPermute: getElems :: (MPermute p m) => p -> m [Int]
+ Data.Permute.MPermute: getElems :: MPermute p m => p -> m [Int]
- Data.Permute.MPermute: getInvSwaps :: (MPermute p m) => p -> m [(Int, Int)]
+ Data.Permute.MPermute: getInvSwaps :: MPermute p m => p -> m [(Int, Int)]
- Data.Permute.MPermute: getInverse :: (MPermute p m) => p -> m p
+ Data.Permute.MPermute: getInverse :: MPermute p m => p -> m p
- Data.Permute.MPermute: getIsEven :: (MPermute p m) => p -> m Bool
+ Data.Permute.MPermute: getIsEven :: MPermute p m => p -> m Bool
- Data.Permute.MPermute: getOrderBy :: (MPermute p m) => (a -> a -> Ordering) -> Int -> [a] -> m p
+ Data.Permute.MPermute: getOrderBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m p
- Data.Permute.MPermute: getPeriod :: (MPermute p m) => p -> m Integer
+ Data.Permute.MPermute: getPeriod :: MPermute p m => p -> m Integer
- Data.Permute.MPermute: getRankBy :: (MPermute p m) => (a -> a -> Ordering) -> Int -> [a] -> m p
+ Data.Permute.MPermute: getRankBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m p
- Data.Permute.MPermute: getSize :: (MPermute p m) => p -> m Int
+ Data.Permute.MPermute: getSize :: MPermute p m => p -> m Int
- Data.Permute.MPermute: getSortBy :: (MPermute p m) => (a -> a -> Ordering) -> Int -> [a] -> m ([a], p)
+ Data.Permute.MPermute: getSortBy :: MPermute p m => (a -> a -> Ordering) -> Int -> [a] -> m ([a], p)
- Data.Permute.MPermute: getSwaps :: (MPermute p m) => p -> m [(Int, Int)]
+ Data.Permute.MPermute: getSwaps :: MPermute p m => p -> m [(Int, Int)]
- Data.Permute.MPermute: isValid :: (MPermute p m) => p -> m Bool
+ Data.Permute.MPermute: isValid :: MPermute p m => p -> m Bool
- Data.Permute.MPermute: newCopyPermute :: (MPermute p m) => p -> m p
+ Data.Permute.MPermute: newCopyPermute :: MPermute p m => p -> m p
- Data.Permute.MPermute: newCyclesPermute :: (MPermute p m) => Int -> [[Int]] -> m p
+ Data.Permute.MPermute: newCyclesPermute :: MPermute p m => Int -> [[Int]] -> m p
- Data.Permute.MPermute: newListPermute :: (MPermute p m) => Int -> [Int] -> m p
+ Data.Permute.MPermute: newListPermute :: MPermute p m => Int -> [Int] -> m p
- Data.Permute.MPermute: newPermute :: (MPermute p m) => Int -> m p
+ Data.Permute.MPermute: newPermute :: MPermute p m => Int -> m p
- Data.Permute.MPermute: newPermute_ :: (MPermute p m) => Int -> m p
+ Data.Permute.MPermute: newPermute_ :: MPermute p m => Int -> m p
- Data.Permute.MPermute: newSwapsPermute :: (MPermute p m) => Int -> [(Int, Int)] -> m p
+ Data.Permute.MPermute: newSwapsPermute :: MPermute p m => Int -> [(Int, Int)] -> m p
- Data.Permute.MPermute: setElem :: (MPermute p m) => p -> Int -> Int -> m ()
+ Data.Permute.MPermute: setElem :: MPermute p m => p -> Int -> Int -> m ()
- Data.Permute.MPermute: setElems :: (MPermute p m) => p -> [Int] -> m ()
+ Data.Permute.MPermute: setElems :: MPermute p m => p -> [Int] -> m ()
- Data.Permute.MPermute: setIdentity :: (MPermute p m) => p -> m ()
+ Data.Permute.MPermute: setIdentity :: MPermute p m => p -> m ()
- Data.Permute.MPermute: setNext :: (MPermute p m) => p -> m Bool
+ Data.Permute.MPermute: setNext :: MPermute p m => p -> m Bool
- Data.Permute.MPermute: setPrev :: (MPermute p m) => p -> m Bool
+ Data.Permute.MPermute: setPrev :: MPermute p m => p -> m Bool
- Data.Permute.MPermute: swapElems :: (MPermute p m) => p -> Int -> Int -> m ()
+ Data.Permute.MPermute: swapElems :: MPermute p m => p -> Int -> Int -> m ()
- Data.Permute.MPermute: thaw :: (MPermute p m) => Permute -> m p
+ Data.Permute.MPermute: thaw :: MPermute p m => Permute -> m p
- Data.Permute.MPermute: unsafeFreeze :: (MPermute p m) => p -> m Permute
+ Data.Permute.MPermute: unsafeFreeze :: MPermute p m => p -> m Permute
- Data.Permute.MPermute: unsafeGetElem :: (MPermute p m) => p -> Int -> m Int
+ Data.Permute.MPermute: unsafeGetElem :: MPermute p m => p -> Int -> m Int
- Data.Permute.MPermute: unsafeNewCyclesPermute :: (MPermute p m) => Int -> [[Int]] -> m p
+ Data.Permute.MPermute: unsafeNewCyclesPermute :: MPermute p m => Int -> [[Int]] -> m p
- Data.Permute.MPermute: unsafeNewListPermute :: (MPermute p m) => Int -> [Int] -> m p
+ Data.Permute.MPermute: unsafeNewListPermute :: MPermute p m => Int -> [Int] -> m p
- Data.Permute.MPermute: unsafeNewSwapsPermute :: (MPermute p m) => Int -> [(Int, Int)] -> m p
+ Data.Permute.MPermute: unsafeNewSwapsPermute :: MPermute p m => Int -> [(Int, Int)] -> m p
- Data.Permute.MPermute: unsafeSetElem :: (MPermute p m) => p -> Int -> Int -> m ()
+ Data.Permute.MPermute: unsafeSetElem :: MPermute p m => p -> Int -> Int -> m ()
- Data.Permute.MPermute: unsafeSwapElems :: (MPermute p m) => p -> Int -> Int -> m ()
+ Data.Permute.MPermute: unsafeSwapElems :: MPermute p m => p -> Int -> Int -> m ()
- Data.Permute.MPermute: unsafeThaw :: (MPermute p m) => Permute -> m p
+ Data.Permute.MPermute: unsafeThaw :: MPermute p m => Permute -> m p
Files
- NEWS +4/−0
- lib/Data/Permute.hs +7/−1
- lib/Data/Permute/MPermute.hs +13/−1
- permutation.cabal +8/−3
- tests/Permute.hs +5/−0
NEWS view
@@ -1,3 +1,7 @@+Changes in 0.4.1:++* added indexOf/getIndexOf+ Changes in 0.4: * Amir Livne Bar-on implemented cycle-related functions
lib/Data/Permute.hs view
@@ -22,6 +22,7 @@ -- * Accessing permutation elements at, unsafeAt,+ indexOf, -- * Permutation properties size,@@ -99,7 +100,12 @@ error "Invalid index" {-# INLINE at #-} --- | Get the inverse of a permutation+-- | @indexOf p x@ gets an index @i@ such that @at p i@ equals @x@.+indexOf :: Permute -> Int -> Int+indexOf p x = runST $ flip getIndexOf x =<< unsafeThaw p+{-# INLINE indexOf #-}++-- | Get the inverse of a permutation. inverse :: Permute -> Permute inverse p = runST $ unsafeFreeze =<< getInverse =<< unsafeThaw p
lib/Data/Permute/MPermute.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, +{-# LANGUAGE BangPatterns, MultiParamTypeClasses, FunctionalDependencies, FlexibleContexts #-} ----------------------------------------------------------------------------- -- |@@ -29,6 +29,7 @@ -- * Accessing permutation elements getElem, setElem,+ getIndexOf, swapElems, -- * Permutation properties@@ -212,6 +213,17 @@ when (i < 0 || i >= n) $ fail "getElem: invalid index" unsafeGetElem p i {-# INLINE getElem #-}++-- | @getIndexOf p x@ returns @i@ sutch that @getElem p i@ equals @x@. This+-- is a linear-time operation.+getIndexOf :: (MPermute p m) => p -> Int -> m Int+getIndexOf p x = + let go !i (y:ys) | y == x = i+ | otherwise = go (i+1) ys+ go _ _ = error "getIndexOf: invalid element"+ in + liftM (go 0) $ getElems p+{-# INLINE getIndexOf #-} -- | @setElem p i x@ sets the value of the @i@th element of the permutation -- @p@. The index @i@ must be in the range @0..(n-1)@, where @n@ is the
permutation.cabal view
@@ -1,5 +1,5 @@ name: permutation-version: 0.4+version: 0.4.1 homepage: http://stat.stanford.edu/~patperry/code/permutation synopsis: A library for permutations and combinations. description:@@ -57,8 +57,13 @@ Data.Permute.IOBase build-depends: base- extensions: MultiParamTypeClasses, FunctionalDependencies, - FlexibleContexts, Rank2Types, MagicHash, UnboxedTuples+ extensions: BangPatterns, + FlexibleContexts,+ FunctionalDependencies, + MagicHash,+ MultiParamTypeClasses, + Rank2Types,+ UnboxedTuples ghc-options: -Wall
tests/Permute.hs view
@@ -55,6 +55,10 @@ forAll arbitrary $ \(Index n i) -> forAll (Test.permute n) $ \p -> a p i == (elems p) !! i+prop_indexOf =+ forAll arbitrary $ \(Index n x) ->+ forAll (Test.permute n) $ \p ->+ at p (indexOf p x) == x prop_size_inverse (p :: Permute) = size (inverse p) == size p@@ -175,6 +179,7 @@ , ("elems . cyclesPermute" , mytest prop_elems_cyclesPermute) , ("at" , mytest prop_at) , ("unsafeAt" , mytest prop_unsafeAt)+ , ("indexOf" , mytest prop_indexOf) , ("size . inverse" , mytest prop_size_inverse) , ("elems . inverse" , mytest prop_elems_inverse) , ("swaps" , mytest prop_swaps)