-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A library for representing and applying permutations. -- -- This library includes data types for storing permutations. It -- implements pure and impure types, the latter which can be modified -- in-place. The main utility of the library is converting between the -- linear representation of a permutation to a sequence of swaps. This -- allows, for instance, applying a permutation or its inverse to an -- array with O(1) memory use. -- -- Much of the interface for the library is based on the permutation -- functions in the GNU Scientific Library (GSL). @package permutation @version 0.2 -- | An overloaded interface to mutable permutations. For permutation types -- which can be used with this interface, see Data.Permute.IO and -- Data.Permute.ST. module Data.Permute.MPermute -- | Class for representing a mutable permutation. The type is -- parameterized over the type of the monad, m, in which the -- mutable permutation will be manipulated. class (Monad m) => MPermute p m | p -> m, m -> p getSize :: (MPermute p m) => p -> m Int newPermute :: (MPermute p m) => Int -> m p newPermute_ :: (MPermute p m) => Int -> m p unsafeGetElem :: (MPermute p m) => p -> Int -> m Int unsafeSetElem :: (MPermute p m) => p -> Int -> Int -> m () unsafeSwapElems :: (MPermute p m) => p -> Int -> Int -> m () getElems :: (MPermute p m) => p -> m [Int] setElems :: (MPermute p m) => p -> [Int] -> m () unsafeFreeze :: (MPermute p m) => p -> m Permute unsafeThaw :: (MPermute p m) => Permute -> m p -- | Construct a permutation from a list of elements. newListPermute n -- is creates a permuation of size n with the ith -- element equal to is !! i. For the permutation to be valid, -- the list is must have length n and contain the -- indices 0..(n-1) exactly once each. newListPermute :: (MPermute p m) => Int -> [Int] -> m p -- | Construct a permutation from a list of swaps. newSwapsPermute n -- ss creates a permuation of size n given a sequence of -- swaps. If ss is [(i0,j0), (i1,j1), ..., (ik,jk)], -- the sequence of swaps is i0 <-> j0, then i1 -- <-> j1, and so on until ik <-> jk. newSwapsPermute :: (MPermute p m) => Int -> [(Int, Int)] -> m p -- | Construct a new permutation by copying another. newCopyPermute :: (MPermute p m) => p -> m p -- | copyPermute dst src copies the elements of the permutation -- src into the permtuation dst. The two permutations -- must have the same size. copyPermute :: (MPermute p m) => p -> p -> m () -- | Set a permutation to the identity. setIdentity :: (MPermute p m) => p -> m () -- | getElem p i gets the value of the ith element of the -- permutation p. The index i must be in the range -- 0..(n-1), where n is the size of the permutation. getElem :: (MPermute p m) => p -> Int -> m Int -- | setElem p i x sets the value of the ith element of -- the permutation p. The index i must be in the range -- 0..(n-1), where n is the size of the permutation. setElem :: (MPermute p m) => p -> Int -> Int -> m () -- | swapElems p i j exchanges the ith and jth -- elements of the permutation p. swapElems :: (MPermute p m) => p -> Int -> Int -> m () -- | Returns whether or not the permutation is valid. For it to be valid, -- the numbers 0,...,(n-1) must all appear exactly once in the -- stored values p[0],...,p[n-1]. isValid :: (MPermute p m) => p -> m Bool -- | Compute the inverse of a permutation. getInverse :: (MPermute p m) => p -> m p -- | Set one permutation to be the inverse of another. copyInverse inv -- p computes the inverse of p and stores it in -- inv. The two permutations must have the same size. copyInverse :: (MPermute p m) => p -> p -> m () -- | Advance a permutation to the next permutation in lexicogrphic order -- and return True. If no further permutaitons are available, -- return False and leave the permutation unmodified. Starting -- with the idendity permutation and repeatedly calling setNext -- will iterate through all permutations of a given size. setNext :: (MPermute p m) => p -> m Bool -- | Step backwards to the previous permutation in lexicographic order and -- return True. If there is no previous permutation, return -- False and leave the permutation unmodified. setPrev :: (MPermute p m) => p -> m Bool -- | Get a lazy list of swaps equivalent to the permutation. A result of -- [ (i0,j0), (i1,j1), ..., (ik,jk) ] means swap i0 -- <-> j0, then i1 <-> j1, and so on until -- ik <-> jk. The laziness makes this function slightly -- dangerous if you are modifying the permutation. getSwaps :: (MPermute p m) => p -> m [(Int, Int)] -- | Get a lazy list of swaps equivalent to the inverse of a permutation. getInvSwaps :: (MPermute p m) => p -> m [(Int, Int)] -- | getSort n xs sorts the first n elements of -- xs and returns a permutation which transforms xs -- into sorted order. The results are undefined if n is greater -- than the length of xs. This is a special case of -- getSortBy. getSort :: (Ord a, MPermute p m) => Int -> [a] -> m ([a], p) getSortBy :: (MPermute p m) => (a -> a -> Ordering) -> Int -> [a] -> m ([a], p) -- | getOrder n xs returns a permutation which rearranges the -- first n elements of xs into ascending order. The -- results are undefined if n is greater than the length of -- xs. This is a special case of getOrderBy. getOrder :: (Ord a, MPermute p m) => Int -> [a] -> m p getOrderBy :: (MPermute p m) => (a -> a -> Ordering) -> Int -> [a] -> m p -- | getRank n xs eturns a permutation, the inverse of which -- rearranges the first n elements of xs into ascending -- order. The returned permutation, p, has the property that -- p[i] is the rank of the ith element of xs. -- The results are undefined if n is greater than the length of -- xs. This is a special case of getRankBy. getRank :: (Ord a, MPermute p m) => Int -> [a] -> m p getRankBy :: (MPermute p m) => (a -> a -> Ordering) -> Int -> [a] -> m p -- | Convert a mutable permutation to an immutable one. freeze :: (MPermute p m) => p -> m Permute -- | Convert an immutable permutation to a mutable one. thaw :: (MPermute p m) => Permute -> m p unsafeNewListPermute :: (MPermute p m) => Int -> [Int] -> m p unsafeNewSwapsPermute :: (MPermute p m) => Int -> [(Int, Int)] -> m p instance MPermute IOPermute IO instance MPermute (STPermute s) (ST s) -- | Mutable permutations in the ST monad. module Data.Permute.ST -- | A mutable permutation that can be manipulated in the ST monad. -- The type argument s is the state variable argument for the -- ST type. data STPermute s -- | A safe way to create and work with a mutable permutation before -- returning an immutable permutation for later perusal. This function -- avoids copying the permutation before returning it - it uses -- unsafeFreeze internally, but this wrapper is a safe interface to that -- function. runSTPermute :: (forall s. ST s (STPermute s)) -> Permute -- | Mutable permutations in the IO monad. module Data.Permute.IO -- | A mutable permutation that can be manipulated in the IO monad. -- The type argument s is the state variable argument for the -- IO type. data IOPermute -- | Immutable permutations. module Data.Permute -- | The immutable permutation data type. Internally, a permutation of size -- n is stored as an 0-based array of n -- Ints. The permutation represents a reordering of the integers -- 0, ..., (n-1). The ith element of the array stores -- the value p[i]. data Permute -- | Construct an identity permutation of the given size. permute :: Int -> Permute -- | Construct a permutation from a list of elements. listPermute n -- is creates a permuation of size n with the ith -- element equal to is !! i. For the permutation to be valid, -- the list is must have length n and contain the -- indices 0..(n-1) exactly once each. listPermute :: Int -> [Int] -> Permute -- | Construct a permutation from a list of swaps. swapsPermute n -- ss creats a permuation of size n given by a sequence of -- swaps. If ss is [(i0,j0), (i1,j1), ..., (ik,jk)], -- the sequence of swaps is i0 <-> j0, then i1 -- <-> j1, and so on until ik <-> jk. swapsPermute :: Int -> [(Int, Int)] -> Permute -- | apply p i gets the value of the ith element of the -- permutation p. The index i must be in the range -- 0..(n-1), where n is the size of the permutation. apply :: Permute -> Int -> Int unsafeApply :: Permute -> Int -> Int -- | Get the size of the permutation. size :: Permute -> Int -- | Get a list of the permutation elements. elems :: Permute -> [Int] -- | Get the inverse of a permutation inverse :: Permute -> Permute -- | Return the next permutation in lexicographic order, or -- Nothing if there are no further permutations. Starting with -- the identity permutation and repeatedly calling this function will -- iterate through all permutations of a given order. next :: Permute -> Maybe Permute -- | Return the previous permutation in lexicographic order, or -- Nothing if there is no such permutation. prev :: Permute -> Maybe Permute -- | Get a list of swaps equivalent to the permutation. A result of [ -- (i0,j0), (i1,j1), ..., (ik,jk) ] means swap i0 <-> -- j0, then i1 <-> j1, and so on until ik -- <-> jk. swaps :: Permute -> [(Int, Int)] -- | Get a list of swaps equivalent to the inverse of permutation. invSwaps :: Permute -> [(Int, Int)] -- | sort n xs sorts the first n elements of xs -- and returns a permutation which transforms xs into sorted -- order. The results are undefined if n is greater than the -- length of xs. This is a special case of sortBy. sort :: (Ord a) => Int -> [a] -> ([a], Permute) sortBy :: (a -> a -> Ordering) -> Int -> [a] -> ([a], Permute) -- | order n xs returns a permutation which rearranges the first -- n elements of xs into ascending order. The results -- are undefined if n is greater than the length of xs. -- This is a special case of orderBy. order :: (Ord a) => Int -> [a] -> Permute orderBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute -- | rank n xs eturns a permutation, the inverse of which -- rearranges the first n elements of xs into ascending -- order. The returned permutation, p, has the property that -- p[i] is the rank of the ith element of xs. -- The results are undefined if n is greater than the length of -- xs. This is a special case of rankBy. rank :: (Ord a) => Int -> [a] -> Permute rankBy :: (a -> a -> Ordering) -> Int -> [a] -> Permute