more-containers-0.2.2.2: A few more collections

Data.Multimap

Description

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

import qualified Data.Multiset as Mmap

All complexities below use m for the number of distinct keys and n for the total number of entries in the multimap.

Synopsis

# Types

## Generic

data Multimap c k v Source #

A map where the same key can be present multiple times.

#### Instances

Instances details
 Functor c => Functor (Multimap c k) Source # Instance detailsDefined in Data.Multimap.Generic Methodsfmap :: (a -> b) -> Multimap c k a -> Multimap c k b #(<\$) :: a -> Multimap c k b -> Multimap c k a # Foldable c => Foldable (Multimap c k) Source # Instance detailsDefined in Data.Multimap.Generic Methodsfold :: Monoid m => Multimap c k m -> m #foldMap :: Monoid m => (a -> m) -> Multimap c k a -> m #foldMap' :: Monoid m => (a -> m) -> Multimap c k a -> m #foldr :: (a -> b -> b) -> b -> Multimap c k a -> b #foldr' :: (a -> b -> b) -> b -> Multimap c k a -> b #foldl :: (b -> a -> b) -> b -> Multimap c k a -> b #foldl' :: (b -> a -> b) -> b -> Multimap c k a -> b #foldr1 :: (a -> a -> a) -> Multimap c k a -> a #foldl1 :: (a -> a -> a) -> Multimap c k a -> a #toList :: Multimap c k a -> [a] #null :: Multimap c k a -> Bool #length :: Multimap c k a -> Int #elem :: Eq a => a -> Multimap c k a -> Bool #maximum :: Ord a => Multimap c k a -> a #minimum :: Ord a => Multimap c k a -> a #sum :: Num a => Multimap c k a -> a #product :: Num a => Multimap c k a -> a # Traversable c => Traversable (Multimap c k) Source # Instance detailsDefined in Data.Multimap.Generic Methodstraverse :: Applicative f => (a -> f b) -> Multimap c k a -> f (Multimap c k b) #sequenceA :: Applicative f => Multimap c k (f a) -> f (Multimap c k a) #mapM :: Monad m => (a -> m b) -> Multimap c k a -> m (Multimap c k b) #sequence :: Monad m => Multimap c k (m a) -> m (Multimap c k a) # (Collection c, IsList (c v), Item (c v) ~ v, Ord k) => IsList (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic Associated Typestype Item (Multimap c k v) # MethodsfromList :: [Item (Multimap c k v)] -> Multimap c k v #fromListN :: Int -> [Item (Multimap c k v)] -> Multimap c k v #toList :: Multimap c k v -> [Item (Multimap c k v)] # (Eq k, Eq (c v)) => Eq (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic Methods(==) :: Multimap c k v -> Multimap c k v -> Bool #(/=) :: Multimap c k v -> Multimap c k v -> Bool # (Typeable c, Typeable v, Data k, Data (c v), Ord k) => Data (Multimap c k v) Source # Since: 0.2.1.1 Instance detailsDefined in Data.Multimap.Generic Methodsgfoldl :: (forall d b. Data d => c0 (d -> b) -> d -> c0 b) -> (forall g. g -> c0 g) -> Multimap c k v -> c0 (Multimap c k v) #gunfold :: (forall b r. Data b => c0 (b -> r) -> c0 r) -> (forall r. r -> c0 r) -> Constr -> c0 (Multimap c k v) #toConstr :: Multimap c k v -> Constr #dataTypeOf :: Multimap c k v -> DataType #dataCast1 :: Typeable t => (forall d. Data d => c0 (t d)) -> Maybe (c0 (Multimap c k v)) #dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c0 (t d e)) -> Maybe (c0 (Multimap c k v)) #gmapT :: (forall b. Data b => b -> b) -> Multimap c k v -> Multimap c k v #gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Multimap c k v -> r #gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Multimap c k v -> r #gmapQ :: (forall d. Data d => d -> u) -> Multimap c k v -> [u] #gmapQi :: Int -> (forall d. Data d => d -> u) -> Multimap c k v -> u #gmapM :: Monad m => (forall d. Data d => d -> m d) -> Multimap c k v -> m (Multimap c k v) #gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Multimap c k v -> m (Multimap c k v) #gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Multimap c k v -> m (Multimap c k v) # (Ord k, Ord (c v)) => Ord (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic Methodscompare :: Multimap c k v -> Multimap c k v -> Ordering #(<) :: Multimap c k v -> Multimap c k v -> Bool #(<=) :: Multimap c k v -> Multimap c k v -> Bool #(>) :: Multimap c k v -> Multimap c k v -> Bool #(>=) :: Multimap c k v -> Multimap c k v -> Bool #max :: Multimap c k v -> Multimap c k v -> Multimap c k v #min :: Multimap c k v -> Multimap c k v -> Multimap c k v # (Ord k, Read k, Read (c v)) => Read (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic MethodsreadsPrec :: Int -> ReadS (Multimap c k v) #readList :: ReadS [Multimap c k v] #readPrec :: ReadPrec (Multimap c k v) #readListPrec :: ReadPrec [Multimap c k v] # (Show k, Show (c v)) => Show (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic MethodsshowsPrec :: Int -> Multimap c k v -> ShowS #show :: Multimap c k v -> String #showList :: [Multimap c k v] -> ShowS # (Ord k, Semigroup (c v)) => Semigroup (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic Methods(<>) :: Multimap c k v -> Multimap c k v -> Multimap c k v #sconcat :: NonEmpty (Multimap c k v) -> Multimap c k v #stimes :: Integral b => b -> Multimap c k v -> Multimap c k v # (Ord k, Monoid (c v)) => Monoid (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic Methodsmempty :: Multimap c k v #mappend :: Multimap c k v -> Multimap c k v -> Multimap c k v #mconcat :: [Multimap c k v] -> Multimap c k v # (Binary k, Binary (c v)) => Binary (Multimap c k v) Source # Since: 0.2.1.0 Instance detailsDefined in Data.Multimap.Generic Methodsput :: Multimap c k v -> Put #get :: Get (Multimap c k v) #putList :: [Multimap c k v] -> Put # type Item (Multimap c k v) Source # Instance detailsDefined in Data.Multimap.Generic type Item (Multimap c k v) = (k, v)

type Group k cv = (k, cv) Source #

A group of values.

## Specific

type ListMultimap = Multimap [] Source #

A multimap with list values. Note that lists do not support efficient appends or sizing, so several multimap operations will have higher complexity than for other collections. If performance is a concern, consider using a SeqMultimap instead.

See Data.Multimap.List for operations specific to this type.

A multimap with Seq values.

See Data.Multimap.Seq for operations specific to this type.

A multimap with Set values. This multimap implementation will automatically deduplicate values per key. For example:

let mm = fromList [('a', 1), ('a', 1)] :: SetMultimap Char Int
size mm == 1 -- True

See Data.Multimap.Set for operations specific to this type.

# Construction

empty :: Multimap c k v Source #

O(1) Creates an empty multimap.

singleton :: Collection c => k -> v -> Multimap c k v Source #

O(1) Creates a multimap with a single entry.

fromList :: (Collection c, IsList (c v), Item (c v) ~ v, Ord k) => [(k, v)] -> Multimap c k v Source #

O(n * log n) Builds a multimap from a list of key, value tuples. The values are in the same order as in the original list.

fromListWith :: Ord k => ([v] -> c v) -> [(k, v)] -> Multimap c k v Source #

O(n * log n) Transforms a list of entries into a multimap, combining the values for each key into the chosen collection. The values are in the same order as in the original list.

fromGroupList :: (Collection c, Monoid (c v), Ord k) => [Group k (c v)] -> Multimap c k v Source #

O(m) Builds a multimap from already grouped collections.

fromMap :: Collection c => Map k (c v) -> Multimap c k v Source #

O(m * C) Transforms a map of collections into a multimap.

# Tests and accessors

null :: Multimap c k v -> Bool Source #

O(1) Checks whether the multimap is empty.

size :: Collection c => Multimap c k v -> Int Source #

O(m * C) Returns the size of the multimap.

distinctSize :: Multimap c k v -> Int Source #

O(1) Returns the number of distinct keys in the multimap.

member :: Ord k => k -> Multimap c k v -> Bool Source #

O(log m) Checks whether a key is present at least once in a multimap.

notMember :: Ord k => k -> Multimap c k v -> Bool Source #

O(log m) Checks whether a key is absent from a multimap.

find :: (Monoid (c v), Ord k) => k -> Multimap c k v -> c v Source #

O(log m) Returns the collection of values associated with a key.

(!) :: (Monoid (c v), Ord k) => Multimap c k v -> k -> c v Source #

O(log m) Infix version of find.

# Modification

prepend :: (Collection c, Monoid (c v), Ord k) => k -> v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Prepends a value to a key's collection.

prependMany :: (Collection c, Monoid (c v), Ord k) => k -> c v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Prepends a collection of values to a key's collection.

append :: (Collection c, Monoid (c v), Ord k) => k -> v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Appends a value to a key's collection.

appendMany :: (Collection c, Monoid (c v), Ord k) => k -> c v -> Multimap c k v -> Multimap c k v Source #

O(log m * C) Appends a collection of values to a key's collection.

deleteMany :: Ord k => k -> Multimap c k v -> Multimap c k v Source #

O(log m) Removes all entries for the given key.

modifyMany :: (Collection c, Monoid (c v), Ord k) => (c v -> c v) -> k -> Multimap c k v -> Multimap c k v Source #

Modifies a key's collection using an arbitrary function. More specifically, this function lifts an operation over a collection of values into a multimap operation.

Sample use to filter even values from a SetMultimap:

   let ms = fromList [('a', 1), ('a', 2)] :: SetMultimap Char Int
modifyMany (Set.filter even) 'a' ms == fromList [('a', 1)]


modifyManyF :: (Collection c, Monoid (c v), Ord k, Functor f) => (c v -> f (c v)) -> k -> Multimap c k v -> f (Multimap c k v) Source #

Modifies a key's collection using an arbitrary function. This is the applicative version of modifyMany.

# Maps and filters

mapGroups :: (Collection c2, Monoid (c2 v2), Ord k2) => (Group k1 (c1 v1) -> Group k2 (c2 v2)) -> Multimap c1 k1 v1 -> Multimap c2 k2 v2 Source #

Maps over the multimap's groups. This method can be used to convert between specific multimaps, for example:

let m1 = fromList [('a', 1), ('a', 1)] :: ListMultimap Char Int
let m2 = mapGroups (fmap Set.fromList) m1 :: SetMultimap Char Int

filter :: (Collection c, Monoid (c v), Ord k) => (v -> Bool) -> Multimap c k v -> Multimap c k v Source #

O(n) Filters multimap entries by value.

filterGroups :: (Collection c, Monoid (c v), Ord k) => (Group k (c v) -> Bool) -> Multimap c k v -> Multimap c k v Source #

O(m) Filters multimap groups. This enables filtering by key and collection.

# Conversion

toList :: Collection c => Multimap c k v -> [(k, v)] Source #

O(n) Converts a multimap into its list of entries. Note that this is different from toList which returns the multimap's values (similar to Data.Map).

toGroupList :: Multimap c k v -> [Group k (c v)] Source #

O(m) Converts a multimap into its list of collections.

toMap :: Multimap c k v -> Map k (c v) Source #

O(1) Converts a multimap into a map of collections.

# Other

keys :: Collection c => Multimap c k v -> [k] Source #

O(m) Returns a list of the multimap's keys. Each key will be repeated as many times as it is present in the multimap.

keysSet :: Multimap c k v -> Set k Source #

O(m) Returns a set of the multimap's (distinct) keys.

keysMultiset :: (Collection c, Ord k) => Multimap c k v -> Multiset k Source #

O(m * C) Returns a multiset of the map's keys with matching multiplicities.

inverse :: (Collection c, IsList (c k), Item (c k) ~ k, Ord k, Ord v) => Multimap c k v -> Multimap c v k Source #

O(n) Inverts keys and values inside a multimap.

inverseWith :: (Collection c1, Ord k, Ord v) => ([k] -> c2 k) -> Multimap c1 k v -> Multimap c2 v k Source #

O(n) Inverts keys and values inside a multimap, potentially changing the collection type.

maxViewWith :: (Collection c, Ord k) => (c v -> Maybe (v, c v)) -> Multimap c k v -> Maybe ((k, v), Multimap c k v) Source #

Returns the multimap's maximum key and value. The input function is guaranteed to be called with a non-empty collection.

Since: 0.2.1.2

minViewWith :: (Collection c, Ord k) => (c v -> Maybe (v, c v)) -> Multimap c k v -> Maybe ((k, v), Multimap c k v) Source #

Returns the multimap's minimum key and value. The input function is guaranteed to be called with a non-empty collection.

Since: 0.2.1.2