-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Multisets with negative membership. -- -- Multisets (or bags) are sets in which elements may occur more than -- once. The number of times an element occurs in a multiset is called -- its multiplicity. -- -- This package provides an efficient implementation of so-called -- signed multisets (also known as hybrid sets or shadow sets), -- which generalise multisets by allowing for negative membership. -- That is, elements in a signed multiset can have negative -- multiplicities. -- -- See also: Wayne D. Blizard. Negative membership. Notre Dame Journal -- of Formal Logic, 31(3):346--368, 1990. @package signed-multiset @version 0.2 -- | An efficient implementation of signed multisets. -- -- A signed multiset is like a multiset (or bag), but additionally allows -- for negative membership. That is, in a signed multiset, an -- element can occur a negative number of times. -- -- For a theory of signed multisets, see -- -- -- -- Since many function names (but not the type name) clash with Prelude -- names, this module is usually imported qualified, e.g., -- -- 
--   import Data.SignedMultiset (SignedMultiset)
--   import qualified Data.SignedMultiset as SignedMultiset
--
-- -- Function comments contain the function's time complexity in so-called -- big-O notation, with n referring to the number of multiset -- members involved. module Data.SignedMultiset -- | A signed multiset with elements of type a. data SignedMultiset a -- | O(1). The empty signed multiset, i.e., the multiset in which -- every element has multiplicity zero. empty :: SignedMultiset a -- | O(1). Create a signed multiset that contains exactly one copy -- of the given element. singleton :: a -> SignedMultiset a -- | O(log n). Insert a new copy of the given element into a signed -- multiset, i.e., increment the multiplicity of the element by 1. insert :: Ord a => a -> SignedMultiset a -> SignedMultiset a -- | O(log n). Insert a specified number of new copies of the given -- element into a signed multiset, i.e., increment the multiplicity of -- the element by the specified number. If the specified number is -- negative, copies are deleted from the set. insertMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a -- | O(log n). Delete a copy of the given element from a signed -- multiset, i.e., decrement the multiplicity of the element by 1. delete :: Ord a => a -> SignedMultiset a -> SignedMultiset a -- | O(log n). Delete a specified number of copies of the given -- element from a signed multiset, i.e., decrement the multiplicity of -- the element by the specified number. If the specified number is -- negative, new copies of the element are inserted into the set. deleteMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a -- | O(log n). Delete all copies of the given element from a signed -- multiset, i.e., set the multiplicity of the element to zero. deleteAll :: Ord a => a -> SignedMultiset a -> SignedMultiset a -- | O(1). Return whether the signed multiset is empty, i.e., -- whether every element has multiplicity zero. null :: SignedMultiset a -> Bool -- | O(n). Return whether the signed multiset is a set, i.e., -- whether all elements have either multiplicity zero or else -- multiplicity 1. isSet :: SignedMultiset a -> Bool -- | O(n). Return whether all elements in the signed multiset have -- nonnegative multiplicities. isPositive :: SignedMultiset a -> Bool -- | O(n). Return whether all elements in the signed multiset have -- nonpositive multiplicities. isNegative :: SignedMultiset a -> Bool -- | O(1). Return the number of members of the signed multiset, -- i.e., the number of elements that have nonzero multiplicity. size :: SignedMultiset a -> Int -- | O(n). Return the cardinality of the signed multiset, i.e., the -- sum of the multiplicities of all elements. cardinality :: SignedMultiset a -> Int -- | O(log n). Return whether the given element is a member of the -- signed multiset, i.e., whether the element has nonzero multiplicity. member :: Ord a => a -> SignedMultiset a -> Bool -- | O(log n). Return whether the given element is not a -- member of the signed multiset, i.e., whether the element has -- multiplicity zero. notMember :: Ord a => a -> SignedMultiset a -> Bool -- | O(log n). Return the multiplicity of the given element in the -- signed multiset. multiplicity :: Ord a => a -> SignedMultiset a -> Int -- | O(n). Return whether the first signed multiset is a submultiset -- of the second, i.e., whether each element that has nonzero -- multiplicity m in the first multiset has nonzero multiplicity -- n with m <= n in the second. isSubmultisetOf :: Ord a => SignedMultiset a -> SignedMultiset a -> Bool -- | O(n). Return whether the first signed multiset is a proper -- submultiset of the second, i.e., whether each element that has nonzero -- multiplicity m in the first multiset has nonzero multiplicity -- n with m < n in the second. isProperSubmultisetOf :: Ord a => SignedMultiset a -> SignedMultiset a -> Bool -- | O(n). Return the union of two signed multisets. The -- multiplicity of an element in the returned multiset is the maximum of -- its nonzero multiplicites in the argument multisets. union :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a -- | O(n). Return the additive union of two signed multisets. The -- multiplicity of an element in the returned multiset is the sum of its -- multiplicities in the argument multisets. additiveUnion :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a -- | O(n). Return the intersection of two signed multisets. If an -- element has nonzero multiplicity in both argument multisets, its -- multiplicity in the returned multiset is the minimum of its -- multiplicites in the argument multisets; otherwise, its multiplicity -- in the returned multiset is zero. intersection :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a -- | O(n). Return the difference of two signed multisets. The -- multiplicity of an element in the returned multiset is the difference -- between its multiplicities in the first and second argument -- multiplicities. difference :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a -- | O(n). Return the shadow of the signed multiset. The -- multiplicity of an element in the returned multiset is the additive -- inverse of its multiplicity in the argument multiset. shadow :: SignedMultiset a -> SignedMultiset a -- | O(n). Return the modulus of the signed multiset. The -- multiplicity of an element in the returned multiset is the absolute -- value of its multiplicity in the argument multiset. modulus :: SignedMultiset a -> SignedMultiset a -- | O(n). Return the signum of the signed multiset. The -- multiplicity of an element in the returned multiset is -1 if it has -- negative multiplicity in the argument multiset, zero if its -- multiplicity in the argument multiset is zero, and 1 if it has -- positive multiplicity in the argument multiset. signum :: SignedMultiset a -> SignedMultiset a -- | O(n). Return the left-continuous unit step of the signed -- multiset. The multiplicity of an element in the returned multiset is -- zero if it has negative multiplicity in the argument multiset, and 1 -- otherwise. unitstep :: SignedMultiset a -> SignedMultiset a -- | O(n). Return the additive union of the given number of copies -- of the signed multiset. multiply :: Int -> SignedMultiset a -> SignedMultiset a -- | O(n * log n). Apply the given function to all elements of the -- signed multiset. map :: (Ord a, Ord b) => (a -> b) -> SignedMultiset a -> SignedMultiset b -- | O(n). Apply the given predicate to the members of the signed -- multiset and their multiplicities. The returned multiset contains the -- copies of the members that satisfy the predicate. filter :: Ord a => (a -> Int -> Bool) -> SignedMultiset a -> SignedMultiset a -- | O(n). Apply the given predicate to the members of the signed -- multiset and their multiplicity. The first returned multiset contains -- the copies of the members that satisfy the predicate, while the second -- returned multiset contains the copies of the members that do not -- satisfy the predicate. partition :: Ord a => (a -> Int -> Bool) -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a) -- | O(n). Split the signed multiset into a multiset containing the -- copies of the members with a multiplicity less than or equal to the -- given number and a multiset containing the copies of the members with -- a multiplicity greater than the given number. split :: Ord a => Int -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a) -- | O(n). Perform a right-associative fold on the members of the -- signed multiset and their multiplicities using the given operator and -- start value. foldr :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> b -- | O(n). Perform a strict right-associative fold on the members of -- the signed multiset and their multiplicities using the given operator -- and start value. foldr' :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> b -- | O(n). Perform a left-associative fold on the members of the -- signed multiset and their multiplicities using the given operator and -- start value. foldl :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> a -- | O(n). Perform a strict left-associative fold on the members of -- the signed multiset and their multiplicities using the given operator -- and start value. foldl' :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> a -- | O(n). Convert the signed multiset to a list that associates all -- members of the multiset with their multiplicity. toList :: SignedMultiset a -> [(a, Int)] -- | O(n + k) (with k the combined length of the returned -- lists). Return two lists, such that: for each element with a positive -- multiplicity m in the signed multiset, the first list -- contains m copies and the second list contains no copies of -- the element; for each element with a negative multiplicity - -- n, the first list contains no and the second list contains -- n copies of the element; and for each element with zero -- multiplicity, neither list contains a copy of the element. toLists :: SignedMultiset a -> ([a], [a]) -- | O(k * log n) (with k the length of the argument list). -- Construct a signed multiset from a list of element/multiplicity pairs. fromList :: Ord a => [(a, Int)] -> SignedMultiset a -- | O(k * log n) (with k the combined length of the argument -- lists). Construct a signed multiset by, starting from the empty -- multiset, inserting copies of elements from the first argument list -- and deleting copies of elements from the second argument list. fromLists :: Ord a => [a] -> [a] -> SignedMultiset a -- | An element of the free abelian group on a. newtype Additive a Additive :: SignedMultiset a -> Additive a getAdditive :: Additive a -> SignedMultiset a instance Ord a => Eq (Additive a) instance Ord a => Ord (Additive a) instance Show a => Show (Additive a) instance (Ord a, Read a) => Read (Additive a) instance Ord a => Monoid (Additive a) instance (Ord a, Data a) => Data (SignedMultiset a) instance Typeable1 SignedMultiset instance Ord a => Monoid (SignedMultiset a) instance (Ord a, Read a) => Read (SignedMultiset a) instance Show a => Show (SignedMultiset a) instance Ord a => Ord (SignedMultiset a) instance Ord a => Eq (SignedMultiset a)