# signed-multiset

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 stackage.org to host generated Haddocks.

**Stefan Holdermans**

**stefan@vectorfabrics.com**

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.

## Changes

* 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

Data.SignedMultiset.SignedMultiset.

version 0.3.0.1:

* 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, Data.SignedMultiset.map selects the maximum of the nonzero

multiplicities of the original elements.

version 0.2.0.1:

* 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

multisets.

* Added the functions Data.SignedMultiset.foldr' and Data.SignedMultiset.foldl',

which are strict versions of Data.SignedMultiset.foldr and

Data.SignedMultiset.foldl.

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