more-containers-0.2.0.0: A few more collections

Data.Multiset

Description

This modules provides a strict multiset implementation. To avoid collision with Prelude functions, it is recommended to import this module qualified:

import qualified Data.Multiset as Mset

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

Synopsis

# Documentation

data Multiset v Source #

A strict implementation of a multiset. It is backed by a Map and inherits several of its properties and operation's complexities. In particular, the number of elements in a multiset must not exceed maxBound :: Int.

Instances
 Source # Instance detailsDefined in Data.Multiset Methodsfold :: 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 # Ord v => IsList (Multiset v) Source # Instance detailsDefined in Data.Multiset Associated Typestype Item (Multiset v) :: Type # MethodsfromList :: [Item (Multiset v)] -> Multiset v #fromListN :: Int -> [Item (Multiset v)] -> Multiset v #toList :: Multiset v -> [Item (Multiset v)] # Eq v => Eq (Multiset v) Source # Instance detailsDefined in Data.Multiset Methods(==) :: Multiset v -> Multiset v -> Bool #(/=) :: Multiset v -> Multiset v -> Bool # Ord v => Ord (Multiset v) Source # Instance detailsDefined in Data.Multiset Methodscompare :: 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 # (Ord v, Read v) => Read (Multiset v) Source # Instance detailsDefined in Data.Multiset MethodsreadsPrec :: Int -> ReadS (Multiset v) # Show v => Show (Multiset v) Source # Instance detailsDefined in Data.Multiset MethodsshowsPrec :: Int -> Multiset v -> ShowS #show :: Multiset v -> String #showList :: [Multiset v] -> ShowS # Ord v => Semigroup (Multiset v) Source # Instance detailsDefined in Data.Multiset 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) Source # Instance detailsDefined in Data.Multiset Methodsmappend :: Multiset v -> Multiset v -> Multiset v #mconcat :: [Multiset v] -> Multiset v # type Item (Multiset v) Source # Instance detailsDefined in Data.Multiset type Item (Multiset v) = v

type Group v = (v, Int) Source #

A group of values of a given size.

# Construction

O(1) Returns an empty multiset.

singleton :: v -> Multiset v Source #

O(1) Returns a multiset with a single element.

replicate :: Int -> v -> Multiset v Source #

O(1) Returns a multiset with the same element repeated. If n is zero or negative, replicate returns an empty multiset.

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

O(n * log n) Builds a multiset from values.

fromGroupList :: Ord v => [Group v] -> Multiset v Source #

O(m * log m) Builds a multiset from a list of groups. Counts of duplicate groups are added together and elements with negative total count are omitted.

fromCountMap :: Ord v => Map v Int -> Multiset v Source #

O(m * log m) Builds a multiset from a map. Negative counts are ignored.

# Tests and accessors

null :: Multiset v -> Bool Source #

O(1) Checks whether a multiset is empty.

size :: Multiset v -> Int Source #

O(1) Returns the total number of elements in the multiset. Note that this isn't the number of distinct elements, see distinctSize for that.

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

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

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

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

O(log m) Checks whether the element is not present.

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

O(log m) Returns the number of times the element is present in the multiset, or 0 if absent.

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

O(log m) Infix version of count.

isSubsetOf :: Ord v => Multiset v -> Multiset v -> Bool Source #

O(m * log m) Checks whether the first subset is a subset of the second (potentially equal to it).

isProperSubsetOf :: Ord v => Multiset v -> Multiset v -> Bool Source #

O(m * log m) Checks whether the first subset is a strict subset of the second.

# Update

modify :: Ord v => (Int -> Int) -> v -> Multiset v -> Multiset v Source #

O(log m) Modifies the count of an element. If the resulting element's count is zero or negative, it will be removed.

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

O(log m) Inserts an element.

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

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

removeAll :: Ord v => v -> Multiset v -> Multiset v Source #

O(log m) Removes all occurrences of a given element.

# Maps and filters

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

Maps on the multiset's values.

mapGroups :: Ord v => (Group v -> Group v) -> Multiset v -> Multiset v Source #

Maps on the multiset's groups. Groups with resulting non-positive counts will be removed from the final multiset.

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

Filters a multiset by value.

filterGroups :: Ord v => (Group v -> Bool) -> Multiset v -> Multiset v Source #

Filters a multiset by group.

# Combination

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

Combines two multisets, returning the max count of each element.

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

Combines two multisets, returning the minimum count of each element (or omitting it if the element is present in only one of the two multisets).

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

O(m * log m) Returns the first set minus the second. Resulting negative counts are ignored.

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

Unions two multisets with a generic function. The combining function will be called with a count of 0 when an element is only present in one set.

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

Intersects two multisets with a generic function. The combining function is guaranteed to be called only with positive counts.

# Conversions

toSet :: Multiset v -> Set v Source #

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

toGroupList :: Multiset v -> [Group v] Source #

O(m) Converts the multiset to a list of values and associated counts. The groups are in undefined order; see toAscGroupList and toDescGroupList for sorted versions.

toGrowingGroupList :: Multiset v -> [Group v] Source #

O(m * log m) Converts the multiset into a list of values and counts, from least common to most.

toShrinkingGroupList :: Multiset v -> [Group v] Source #

O(m * log m) Converts the multiset into a list of values and counts, from most common to least.

O(1) Converts the multiset to a map of (positive) counts.

# Other

mostCommon :: Multiset v -> [(Int, [v])] Source #

O(m) Returns the multiset's elements grouped by count, most common first.