Portability | portable |
---|---|

Stability | provisional |

Maintainer | stefan@vectorfabrics.com |

Safe Haskell | Safe-Infered |

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

- Wayne D. Blizard. Negative membership.
*Notre Dame Journal of Formal Logic*, 31(3):346--368, 1990.

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.

- data SignedMultiset a
- empty :: SignedMultiset a
- singleton :: a -> SignedMultiset a
- insert :: Ord a => a -> SignedMultiset a -> SignedMultiset a
- insertMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
- delete :: Ord a => a -> SignedMultiset a -> SignedMultiset a
- deleteMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset a
- deleteAll :: Ord a => a -> SignedMultiset a -> SignedMultiset a
- null :: SignedMultiset a -> Bool
- isSet :: SignedMultiset a -> Bool
- size :: SignedMultiset a -> Int
- cardinality :: SignedMultiset a -> Int
- member :: Ord a => a -> SignedMultiset a -> Bool
- notMember :: Ord a => a -> SignedMultiset a -> Bool
- multiplicity :: Ord a => a -> SignedMultiset a -> Int
- isSubmultisetOf :: Ord a => SignedMultiset a -> SignedMultiset a -> Bool
- isProperSubmultisetOf :: Ord a => SignedMultiset a -> SignedMultiset a -> Bool
- union :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a
- additiveUnion :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a
- intersection :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a
- difference :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset a
- multiply :: Int -> SignedMultiset a -> SignedMultiset a
- map :: (Ord a, Ord b) => (a -> b) -> SignedMultiset a -> SignedMultiset b
- foldr :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
- foldl :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> a
- toList :: SignedMultiset a -> [(a, Int)]
- fromList :: Ord a => [(a, Int)] -> SignedMultiset a
- newtype Additive a = Additive {}

# Type

data SignedMultiset a Source

A signed multiset with elements of type `a`

.

Typeable1 SignedMultiset | |

Ord a => Eq (SignedMultiset a) | |

(Ord a, Data a) => Data (SignedMultiset a) | |

Ord a => Ord (SignedMultiset a) | |

(Ord a, Read a) => Read (SignedMultiset a) | |

Show a => Show (SignedMultiset a) | |

Ord a => Monoid (SignedMultiset a) | Monoid under |

# Construction

empty :: SignedMultiset aSource

*O(1)*. The empty signed multiset, i.e., the multiset in which every
element has multiplicity zero.

singleton :: a -> SignedMultiset aSource

*O(1)*. Create a signed multiset that contains exactly one copy of the
given element.

insert :: Ord a => a -> SignedMultiset a -> SignedMultiset aSource

*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.

insertMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset aSource

*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.

delete :: Ord a => a -> SignedMultiset a -> SignedMultiset aSource

*O(log n)*. Delete a copy of the given element from a signed multiset,
i.e., decrement the multiplicity of the element by 1.

deleteMany :: Ord a => a -> Int -> SignedMultiset a -> SignedMultiset aSource

*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.

deleteAll :: Ord a => a -> SignedMultiset a -> SignedMultiset aSource

*O(log n)*. Delete all copies of the given element from a signed multiset,
i.e., set the multiplicity of the element to zero.

# Queries

null :: SignedMultiset a -> BoolSource

*O(1)*. Return whether the signed multiset is empty, i.e., whether every
element has multiplicity zero.

isSet :: SignedMultiset a -> BoolSource

*O(n)*. Return whether the signed multiset is a set, i.e., whether all
elements have either multiplicity zero or else multiplicity 1.

size :: SignedMultiset a -> IntSource

*O(1)*. Return the number of members of the signed multiset, i.e., the
number of elements that have nonzero multiplicity.

cardinality :: SignedMultiset a -> IntSource

*O(n)*. Return the cardinality of the signed multiset, i.e., the sum of
the multiplicities of all elements.

member :: Ord a => a -> SignedMultiset a -> BoolSource

*O(log n)*. Return whether the given element is a member of the signed
multiset, i.e., whether the element has nonzero multiplicity.

notMember :: Ord a => a -> SignedMultiset a -> BoolSource

*O(log n)*. Return whether the given element is *not* a member of the
signed multiset, i.e., whether the element has multiplicity zero.

multiplicity :: Ord a => a -> SignedMultiset a -> IntSource

*O(log n)*. Return the multiplicity of the given element in the signed
multiset.

isSubmultisetOf :: Ord a => SignedMultiset a -> SignedMultiset a -> BoolSource

*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.

isProperSubmultisetOf :: Ord a => SignedMultiset a -> SignedMultiset a -> BoolSource

*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.

# Combining

union :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset aSource

*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.

additiveUnion :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset aSource

*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.

intersection :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset aSource

*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.

difference :: Ord a => SignedMultiset a -> SignedMultiset a -> SignedMultiset aSource

*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.

# Scalar multiplication

multiply :: Int -> SignedMultiset a -> SignedMultiset aSource

*O(n)*. Return the additive union of the given number of copies of the
signed multiset.

# Traversals

map :: (Ord a, Ord b) => (a -> b) -> SignedMultiset a -> SignedMultiset bSource

*O(n * log n)*. Apply the given function to all elements of the signed
multiset.

foldr :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> bSource

*O(n)*. Perform a right-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 -> aSource

*O(n)*. Perform a left-associative fold on the members and elements of
the signed multiset using the given operator and start value.

# Conversion

toList :: SignedMultiset a -> [(a, Int)]Source

*O(n)*. Convert the signed multiset to a list that associates all members
of the multiset with their multiplicity.

fromList :: Ord a => [(a, Int)] -> SignedMultiset aSource

*O(n * log n)*. Construct a signed multiset from a list of
element/multiplicity pairs.