Data.Multimap

A very simple Multimap, based on Map from the containers package.

Multimap type

data Multimap k v

A Multimap with keys k and values v.

A key can have multiple values (but not zero). The same value can be added multiple times (thus no constraints are ever imposed on v).

Internally this is simply a Map k [v]. See toMap for accessing the underlying Map.

Query

null :: Multimap k a -> Bool

O(1). Check whether the multimap is empty or not.

size :: Multimap k a -> Int

O(1). The number of elements in the multimap.

numKeys :: Multimap k a -> Word32

O(1). The number of keys in the multimap.

As this is a multimap, the number of keys is not necessarily equal to the number of values.

numValues :: Multimap k a -> Word32

O(1). The number of values in the multimap.

As this is a multimap, the number of keys is not necessarily equal to the number of values.

member :: Ord k => Multimap k a -> k -> Bool

O(log n). Is the key a member of the multimap?

notMember :: Ord k => Multimap k a -> k -> Bool

O(log n). Is the key not a member of the multimap?

lookup :: Ord k => k -> Multimap k a -> [a]

O(log n). Lookup the value at a key in the map.

The function will return the corrsponding values as a List, or the empty list if no values are associated witht the given key.

Operators

(!) :: Ord k => Multimap k a -> k -> [a]

As flip lookup

Construction

empty :: Multimap k a

O(1). The empty multimap.

Insertion

insert :: Ord k => k -> a -> Multimap k a -> Multimap k a

O(log n). Insert a new key and value in the map.

Delete

delete :: Ord k => k -> a -> Multimap k a -> Multimap k a

O(log n). Delete a key and all its values from the map.

Traversal

map :: (a -> b) -> Multimap k a -> Multimap k b

Map a function over all values in the map.

mapKeys :: Ord k2 => (k1 -> k2) -> Multimap k1 a -> Multimap k2 a

mapKeys f s is the multimap obtained by applying f to each key of s.

mapWithKey :: (k -> a -> b) -> Multimap k a -> Multimap k b

Map a function over all key/value pairs in the map.

Folds

foldr :: (a -> b -> b) -> b -> Multimap k a -> b

Fold the values in the map using the given right-associative binary operator.

foldl :: (a -> b -> a) -> a -> Multimap k b -> a

Fold the values in the map using the given left-associative binary operator.

foldrWithKey :: (k -> a -> b -> b) -> b -> Multimap k a -> b

O(n). Fold the keys and values in the map using the given right-associative binary operator, taking into account not only the value but also the key.

foldlWithKey :: (a -> k -> b -> a) -> a -> Multimap k b -> a

O(n). Fold the keys and values in the map using the given left-associative binary operator, taking into account not only the value but also the key.

Conversion

elems :: Multimap k a -> [[a]]

O(n). Return all elements of the multimap in the ascending order of their keys.

A list of lists is returned since a key can have multiple values. Use concat to flatten.

keys :: Multimap k a -> [k]

O(n). Return all keys of the multimap in ascending order.

keysSet :: Multimap k a -> Set k

O(n). The set of all keys of the multimap.

assocs :: Multimap k a -> [(k, [a])]

O(n). Return all key/value pairs in the multimap in ascending key order.

toMap :: Multimap k a -> Map k [a]

O(1). Return the map of lists.

toMapOfSets :: Ord a => Multimap k a -> Map k (Set a)

/O(k*m*log m) where k is the number of keys and m the maximum number of elements associated with a single key/

toList :: Multimap k a -> [(k, a)]

Return a flattened list of key/value pairs.

fromList :: Ord k => [(k, a)] -> Multimap k a

O(n*log n) Create a multimap from a list of key/value pairs.

 fromList xs == foldr (uncurry insert) empty

fromMap :: Map k [a] -> Multimap k a

Turns a map of lists into a multimap.

Min/Max

findMin :: Multimap k a -> Maybe k

O(log n) Find the minimal key of the multimap.

findMax :: Multimap k a -> Maybe k

O(log n) Find the maximal key of the multimap.

findMinWithValues :: Multimap k a -> Maybe (k, [a])

O(log n) Find the minimal key and the values associated with it.

findMaxWithValues :: Multimap k a -> Maybe (k, [a])

O(log n) Find the maximal key and the values associated with it.