-- 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.5 -- | Parsing utilities for signed multisets. module Data.SignedMultiset.Read readsMembers :: Read a => Int -> ReadS [(a, Int)] mapReadS :: (a -> b) -> ReadS a -> ReadS b -- | Pretty-print utilities for signed multisets. module Data.SignedMultiset.Show showsMembers :: Show a => [(a, Int)] -> ShowS -- | 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 -- object 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. -- -- Signed-multiset types are constructed by the type constructor -- SignedMultiset. The number of times an object appears in a -- signed multiset is called its multiplicity. An object is said -- to be a member of a signed multiset if it has a nonzero -- multiplicity. The number of members of a signed multiset is referred -- to as its size, while the cardinality of a signed -- multiset is the sum of the multiplicities of its members. A signed -- multiset is empty if it is without members. -- -- Textually, signed multisets are represented by listing their members -- and, in parentheses, their multiplicities between curly brackets. For -- instance, the signed multiset that contains -1 copies of 2, 2 copies -- of 3, and -4 copies of 5 is denoted by "{2(-1),3(2),5(-4)}". module Data.SignedMultiset -- | A signed multiset over objects of type a. data SignedMultiset a -- | O(1). The empty signed multiset, i.e., the multiset in which -- every object has multiplicity zero. empty :: SignedMultiset a -- | O(1). Create a signed multiset that contains exactly one copy -- of the given object. singleton :: a -> SignedMultiset a -- | O(log n). Insert a new copy of the given object into a signed -- multiset, i.e., increment the multiplicity of the object by 1. insert :: Ord a => a -> SignedMultiset a -> SignedMultiset a -- | O(log n). Insert a specified number of new copies of the given -- object into a signed multiset, i.e., increment the multiplicity of the -- object 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 object from a signed -- multiset, i.e., decrement the multiplicity of the object by 1. delete :: Ord a => a -> SignedMultiset a -> SignedMultiset a -- | O(log n). Delete a specified number of copies of the given -- object from a signed multiset, i.e., decrement the multiplicity of the -- object by the specified number. If the specified number is negative, -- new copies of the object are inserted into the set. deleteMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a -- | O(log n). Delete all copies of the given object from a signed -- multiset, i.e., set the multiplicity of the object to zero. deleteAll :: Ord a => a -> SignedMultiset a -> SignedMultiset a -- | O(1). Return whether the signed multiset is empty, i.e., -- whether every object has multiplicity zero. null :: SignedMultiset a -> Bool -- | O(n). Return whether the signed multiset is a set, i.e., -- whether all object have either multiplicity zero or else multiplicity -- 1. isSet :: SignedMultiset a -> Bool -- | O(n). Return whether all objects in the signed multiset have -- nonnegative multiplicities. isPositive :: SignedMultiset a -> Bool -- | O(n). Return whether all objects 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 objects 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 objects. cardinality :: SignedMultiset a -> Int -- | O(log n). Return whether the given object is a member of the -- signed multiset, i.e., whether the object has nonzero multiplicity. member :: Ord a => a -> SignedMultiset a -> Bool -- | O(log n). Return whether the given object is not a -- member of the signed multiset, i.e., whether the object has -- multiplicity zero. notMember :: Ord a => a -> SignedMultiset a -> Bool -- | O(log n). Return the multiplicity of the given object 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 object 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 the union of two signed multisets. The -- multiplicity of an object in the returned multiset is the maximum of -- its nonzero multiplicities 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 object 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 -- object has nonzero multiplicity in both argument multisets, its -- multiplicity in the returned multiset is the minimum of its -- multiplicities 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 root of the signed multiset. The multiplicity -- of an object in the returned multiset is zero if its multiplicity in -- the argument multiset is zero and 1 otherwise. root :: SignedMultiset a -> SignedMultiset a -- | O(n). Return the shadow of the signed multiset. The -- multiplicity of an object 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 object 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 object 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 object 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 objects of the -- signed multiset. If the the function maps distinct objects to the same -- new object, the multiplicity of the new object is the maximum of the -- nonzero multiplicities of the two original objects. map :: Ord b => (a -> b) -> SignedMultiset a -> SignedMultiset b -- | O(n * log n). Apply the given function to all objects of the -- signed multiset. If the the function maps distinct objects to the same -- new object, the multiplicity of the new object is the sum of the -- multiplicities of the two original objects. additiveMap :: 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 :: (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 :: (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 :: 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 object with a positive -- multiplicity m in the signed multiset, the first list -- contains m copies and the second list contains no copies of -- the object; for each object with a negative multiplicity -n, -- the first list contains no and the second list contains n -- copies of the object; and for each object with zero multiplicity, -- neither list contains a copy of the object. 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 object/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 objects from the first argument list and -- deleting copies of objects 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 (GHC.Classes.Ord a, GHC.Read.Read a) => GHC.Read.Read (Data.SignedMultiset.Additive a) instance GHC.Show.Show a => GHC.Show.Show (Data.SignedMultiset.Additive a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.SignedMultiset.Additive a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Data.SignedMultiset.Additive a) instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.SignedMultiset.Additive a) instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.SignedMultiset.Additive a) instance GHC.Classes.Ord a => GHC.Classes.Eq (Data.SignedMultiset.SignedMultiset a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.SignedMultiset.SignedMultiset a) instance GHC.Show.Show a => GHC.Show.Show (Data.SignedMultiset.SignedMultiset a) instance (GHC.Classes.Ord a, GHC.Read.Read a) => GHC.Read.Read (Data.SignedMultiset.SignedMultiset a) instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.SignedMultiset.SignedMultiset a) instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.SignedMultiset.SignedMultiset a) instance (GHC.Classes.Ord a, Data.Data.Data a) => Data.Data.Data (Data.SignedMultiset.SignedMultiset a)