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

A group of values.

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.

O(1) Creates an empty multimap.

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

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.

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.

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

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

O(1) Checks whether the multimap is empty.

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

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

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

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

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

O(log m) Infix version of find.

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

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

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

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

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

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)]

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

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

O(n) Filters multimap entries by value.

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

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

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

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

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.

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

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

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

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