Data.Multiset

A simple multiset implementation

All complexities below use m for the number of distinct elements and n for the total number of elements.

Documentation

data Multiset v

A multiset

Instances

Foldable Multiset

Methods

fold :: Monoid m => Multiset m -> m

foldMap :: Monoid m => (a -> m) -> Multiset a -> m

foldr :: (a -> b -> b) -> b -> Multiset a -> b

foldr' :: (a -> b -> b) -> b -> Multiset a -> b

foldl :: (b -> a -> b) -> b -> Multiset a -> b

foldl' :: (b -> a -> b) -> b -> Multiset a -> b

foldr1 :: (a -> a -> a) -> Multiset a -> a

foldl1 :: (a -> a -> a) -> Multiset a -> a

toList :: Multiset a -> [a]

null :: Multiset a -> Bool

length :: Multiset a -> Int

elem :: Eq a => a -> Multiset a -> Bool

maximum :: Ord a => Multiset a -> a

minimum :: Ord a => Multiset a -> a

sum :: Num a => Multiset a -> a

product :: Num a => Multiset a -> a

Eq v => Eq (Multiset v)

Methods

(==) :: Multiset v -> Multiset v -> Bool

(/=) :: Multiset v -> Multiset v -> Bool

Ord v => Ord (Multiset v)

Methods

compare :: Multiset v -> Multiset v -> Ordering

(<) :: Multiset v -> Multiset v -> Bool

(<=) :: Multiset v -> Multiset v -> Bool

(>) :: Multiset v -> Multiset v -> Bool

(>=) :: Multiset v -> Multiset v -> Bool

max :: Multiset v -> Multiset v -> Multiset v

min :: Multiset v -> Multiset v -> Multiset v

(Read v, Ord v) => Read (Multiset v)

Methods

readsPrec :: Int -> ReadS (Multiset v)

readList :: ReadS [Multiset v]

readPrec :: ReadPrec (Multiset v)

readListPrec :: ReadPrec [Multiset v]

Show v => Show (Multiset v)

Methods

showsPrec :: Int -> Multiset v -> ShowS

show :: Multiset v -> String

showList :: [Multiset v] -> ShowS

Ord v => Semigroup (Multiset v)

Methods

(<>) :: Multiset v -> Multiset v -> Multiset v

sconcat :: NonEmpty (Multiset v) -> Multiset v

stimes :: Integral b => b -> Multiset v -> Multiset v

Ord v => Monoid (Multiset v)

Methods

mempty :: Multiset v

mappend :: Multiset v -> Multiset v -> Multiset v

mconcat :: [Multiset v] -> Multiset v

Tests

null :: Multiset v -> Bool

O(1) Whether a multiset is empty.

size :: Multiset v -> Int

The total number of elements in the multiset.

O(m) Note that this isn't the number of distinct elements, distinctSize provides it.

distinctSize :: Multiset v -> Int

O(1) The number of distinct elements in the multiset.

Construction

empty :: Multiset v

O(1) The empty multiset.

singleton :: Ord v => v -> Multiset v

O(1) A multiset with a single element.

fromMap :: (Integral a, Ord v) => Map v a -> Multiset v

O(m * log m) Build a multiset from a map.

Negative counts are ignored; see fromMap' for a stricter version.

fromMap' :: (Integral a, Ord v) => Map v a -> Maybe (Multiset v)

O(m * log m) Build a multiset from a map.

If at least one of the counts is negative, this method will return Nothing.

fromList :: Ord v => [v] -> Multiset v

O(n * log n) Build a multiset from a list.

fromCountsList :: (Integral a, Ord v) => [(v, a)] -> Multiset v

O(m * log m) Build a multiset from a list of counts.

Counts of duplicate entries are added together.

fromCountsList' :: (Integral a, Ord v) => [(v, a)] -> Maybe (Multiset v)

O(m * log m) Build a multiset from a list of counts.

Counts of duplicate entries are added together. Returns Nothing if the total count for any element is negative.

Accessors

member :: Ord v => v -> Multiset v -> Bool

O(log m) Whether the element is present at least once.

notMember :: Ord v => v -> Multiset v -> Bool

O(log m) Whether the element is not present.

(!) :: Ord v => Multiset v -> v -> Int

O(1) Infix version of count.

count :: Ord v => v -> Multiset v -> Int

O(1) The number of times the element is present in the multiset.

0 if absent.

Update

incr :: Ord v => Int -> v -> Multiset v -> Multiset v

O(log m) Increment the count of element.

The increment can be negative (removing elements). Resulting negative counts are considered 0 (see incr' for a stricter implementation)..

incr' :: Ord v => Int -> v -> Multiset v -> Maybe (Multiset v)

O(log m) Increment the count of element.

Resulting negative counts are considered 0.

insert :: Ord v => v -> Multiset v -> Multiset v

O(log m) Insert a single element.

remove :: Ord v => v -> Multiset v -> Multiset v

O(log m) Remove a single element. Does nothing if the element isn't present.

remove' :: Ord v => v -> Multiset v -> Maybe (Multiset v)

Remove a single element. Returns Nothing if the element wasn't already in.

filter :: Ord v => (v -> Bool) -> Multiset v -> Multiset v

Standard value filter.

map :: (Ord v1, Ord v2) => (v1 -> v2) -> Multiset v1 -> Multiset v2

Map on the multiset's values.

mapCounts :: Ord v => (Int -> Int) -> Multiset v -> Multiset v

Map on the multiset's counts.

Combination

max :: Ord v => Multiset v -> Multiset v -> Multiset v

Convenience methods to get the max of two multisets.

min :: Ord v => Multiset v -> Multiset v -> Multiset v

Convenience methods to get the min of two multisets.

sum :: Ord v => Multiset v -> Multiset v -> Multiset v

Convenience methods to get the sum of two multisets.

unionWith :: Ord v => (Int -> Int -> Int) -> Multiset v -> Multiset v -> Multiset v

Generic union method.

difference :: Ord v => Multiset v -> Multiset v -> Multiset v

The first set minus the second. Resulting negative counts are ignored.

intersectionWith :: Ord v => (Int -> Int -> Int) -> Multiset v -> Multiset v -> Multiset v

Generic intersection method.

toList :: Multiset v -> [v]

Convert the multiset to a list; elements will be repeated according to their count.

toCountsList :: Multiset v -> [(v, Int)]

toAscCountsList :: Multiset v -> [(v, Int)]

toDescCountsList :: Multiset v -> [(v, Int)]

Other

elems :: Multiset v -> Set v

O(m) The Set of all elements in the multiset.