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

Stability | provisional |

Maintainer | stefan@vectorfabrics.com |

Safe Haskell | None |

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

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

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)}"`

.

- 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
- isPositive :: SignedMultiset a -> Bool
- isNegative :: 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
- 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
- root :: SignedMultiset a -> SignedMultiset a
- shadow :: SignedMultiset a -> SignedMultiset a
- modulus :: SignedMultiset a -> SignedMultiset a
- signum :: SignedMultiset a -> SignedMultiset a
- unitstep :: Ord a => SignedMultiset a -> SignedMultiset a
- multiply :: Ord a => Int -> SignedMultiset a -> SignedMultiset a
- map :: (Ord a, Ord b) => (a -> b) -> SignedMultiset a -> SignedMultiset b
- additiveMap :: (Ord a, Ord b) => (a -> b) -> SignedMultiset a -> SignedMultiset b
- filter :: Ord a => (a -> Int -> Bool) -> SignedMultiset a -> SignedMultiset a
- partition :: Ord a => (a -> Int -> Bool) -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)
- split :: Ord a => Int -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)
- foldr :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
- foldr' :: (a -> Int -> b -> b) -> b -> SignedMultiset a -> b
- foldl :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> a
- foldl' :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> a
- toList :: SignedMultiset a -> [(a, Int)]
- toLists :: SignedMultiset a -> ([a], [a])
- fromList :: Ord a => [(a, Int)] -> SignedMultiset a
- fromLists :: Ord a => [a] -> [a] -> SignedMultiset a
- newtype Additive a = Additive {}

# Type

data SignedMultiset a Source

A signed multiset over objects 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 object
has multiplicity zero.

singleton :: a -> SignedMultiset aSource

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

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

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

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

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

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

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

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

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

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

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

# Queries

null :: SignedMultiset a -> BoolSource

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

isSet :: SignedMultiset a -> BoolSource

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

isPositive :: SignedMultiset a -> BoolSource

*O(n)*. Return whether all objects in the signed multiset have nonnegative
multiplicities.

isNegative :: SignedMultiset a -> BoolSource

*O(n)*. Return whether all objects in the signed multiset have nonpositive
multiplicities.

size :: SignedMultiset a -> IntSource

*O(1)*. Return the number of members of the signed multiset, i.e., the
number of objects 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 objects.

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

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

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

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

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

*O(log n)*. Return the multiplicity of the given object 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 object that has nonzero multiplicity `m`

in the
first multiset has nonzero multiplicity `n`

with `m <= n`

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
object in the returned multiset is the maximum of its nonzero multiplicities
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 object 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 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.

# Memberwise operations

root :: SignedMultiset a -> SignedMultiset aSource

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

shadow :: SignedMultiset a -> SignedMultiset aSource

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

modulus :: SignedMultiset a -> SignedMultiset aSource

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

signum :: SignedMultiset a -> SignedMultiset aSource

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

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

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

multiply :: Ord a => 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 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.

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

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

filter :: Ord a => (a -> Int -> Bool) -> SignedMultiset a -> SignedMultiset aSource

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

partition :: Ord a => (a -> Int -> Bool) -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)Source

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

split :: Ord a => Int -> SignedMultiset a -> (SignedMultiset a, SignedMultiset a)Source

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

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

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

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

foldl :: (a -> b -> Int -> a) -> a -> SignedMultiset b -> aSource

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

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

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

toLists :: SignedMultiset a -> ([a], [a])Source

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

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

*O(k * log n)* (with *k* the length of the argument list). Construct a
signed multiset from a list of object/multiplicity pairs.

fromLists :: Ord a => [a] -> [a] -> SignedMultiset aSource

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