-- 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, 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.1 -- | 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(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 n in the first multiset has nonzero multiplicity -- m with n <= m 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 n in the first multiset has nonzero multiplicity -- m with n < m 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 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). Perform a right-associative fold on the members and -- elements of the signed multiset 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 and -- elements of the signed multiset 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 * log n). Construct a signed multiset from a list of -- element/multiplicity pairs. fromList :: Ord a => [(a, Int)] -> SignedMultiset a -- | Monoid under additiveUnion. 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)