Multisets with negative membership.

Latest on Hackage:0.4

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow to host generated Haddocks.

BSD3 licensed by Stefan Holdermans

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.


version 0.4:

* Removed the dependency on packages base >= 4.5.0 && < 4.7.

* Added a dependency on package base == 4.7.*.

* Removed the Data.Typeable.Typeable1 instance for
Data.SignedMultiset.SignedMultiset as the class Data.Typeable.Typeable no
longer exist.

* Added a Data.Typeable.Typeable instance for


* Asserted compatability with packages base-4.6.* and containers-0.5.*.

version 0.3:

* Removed the functions Data.SignedMultiset.isProperSubmapOf and
Data.SignedMultiset.difference as their semantics may be confusing.

* Added the function Data.SignedMultiset.root which returns the root set of a
signed multiset.

* Fixed a bug in Data.SignedMultiset.unitstep: objects with negative
multiplicities in the argument multiset are now correctly left out of the
returned multiset.

* Fixed a bug in Data.SignedMultiset.multiply: multiply 0 s correctly yields the
empty multiset now.

* Added the function Data.SignedMultiset.additiveMap. In case distinct elements
are mapped to the same new element, this function sets the multiplicity of the
new element to the sum of the multiplicities of the two original elements. In
contrast, selects the maximum of the nonzero
multiplicities of the original elements.


* Fixed a bug in the implementation of the function
Data.SignedMultiset.difference. Before the fix, it would incorrectly keep
copies of elements of the second argument multiset if these elements were not
members of the first argument multiset, rather than deleting them from the
returned multiset.

version 0.2:

* Added the functions Data.SignedMultiset.isPositive and
Data.SignedMultiset.isNegative, which return whether all elements in a
signed multiset have respectively nonnegative or nonpositive multiplicity.

* Added the functions Data.SignedMultiset.shadow, Data.SignedMultiset.modulus,
Data.SignedMultiset.signum, and Data.SignedMultiset.unitstep which return
respecitively the additive inverse, modulus, signum, and left-continuous unit
step of a signed multiset.

* Added the functions Data.SignedMultiset.filter, Data.SignedMultiset.partition,
and Data.SignedMultiset.split for filtering and partitioning signed

* Added the functions Data.SignedMultiset.foldr' and Data.SignedMultiset.foldl',
which are strict versions of Data.SignedMultiset.foldr and

* Changed the behaviour of both the function Data.SignedMultiset.fromList and
the Read instance of Data.SignedMultiset: it multiple element/multiplicity
pairs are provided for the same element, the multiplicity of the element in
the constructed multiset is now taken to be the sum of the provided
multiplicities (rather than the rightmost multiplicity).

* Added the functions Data.SignedMultiset.toLists and
Data.SignedMultiset.fromLists, which convert between signed multisets and
pairs of lists of elements with positive and negative multiplicity.

* Made the dependency on the base and containers packages more restrictive. The
dependency for base now carries the version constraint == 4.5.*, while the
dependency for containers now comes with the constraint >= 0.4.2 && < 0.5.

version 0.1:

* Initial release.
Depends on 2 packages:
Used by 1 package:
comments powered byDisqus