Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell2010 |

A very simple MultiMap, based on `Map`

from the containers package.

- data MultiMap k v
- null :: MultiMap k a -> Bool
- size :: MultiMap k a -> Int
- numKeys :: MultiMap k a -> Word32
- numValues :: MultiMap k a -> Word32
- member :: Ord k => MultiMap k a -> k -> Bool
- notMember :: Ord k => MultiMap k a -> k -> Bool
- lookup :: Ord k => k -> MultiMap k a -> [a]
- (!) :: Ord k => MultiMap k a -> k -> [a]
- empty :: MultiMap k a
- insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a
- delete :: Ord k => k -> MultiMap k a -> MultiMap k a
- map :: (a -> b) -> MultiMap k a -> MultiMap k b
- mapKeys :: Ord k2 => (k1 -> k2) -> MultiMap k1 a -> MultiMap k2 a
- mapWithKey :: (k -> a -> b) -> MultiMap k a -> MultiMap k b
- foldr :: (a -> b -> b) -> b -> MultiMap k a -> b
- foldl :: (a -> b -> a) -> a -> MultiMap k b -> a
- foldrWithKey :: (k -> a -> b -> b) -> b -> MultiMap k a -> b
- foldlWithKey :: (a -> k -> b -> a) -> a -> MultiMap k b -> a
- elems :: MultiMap k a -> [[a]]
- keys :: MultiMap k a -> [k]
- keysSet :: MultiMap k a -> Set k
- assocs :: MultiMap k a -> [(k, [a])]
- toMap :: MultiMap k a -> Map k [a]
- toMapOfSets :: Ord a => MultiMap k a -> Map k (Set a)
- toList :: MultiMap k a -> [(k, a)]
- fromList :: Ord k => [(k, a)] -> MultiMap k a
- fromMap :: Map k [a] -> MultiMap k a
- findMin :: MultiMap k a -> Maybe k
- findMax :: MultiMap k a -> Maybe k
- findMinWithValues :: MultiMap k a -> Maybe (k, [a])
- findMaxWithValues :: MultiMap k a -> Maybe (k, [a])

# MultiMap type

# Query

numKeys :: MultiMap k a -> Word32 Source

*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 Source

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

notMember :: Ord k => MultiMap k a -> k -> Bool Source

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

lookup :: Ord k => k -> MultiMap k a -> [a] Source

*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

# Construction

## Insertion

insert :: Ord k => k -> a -> MultiMap k a -> MultiMap k a Source

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

## Delete

delete :: Ord k => k -> MultiMap k a -> MultiMap k a Source

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

# Traversal

mapKeys :: Ord k2 => (k1 -> k2) -> MultiMap k1 a -> MultiMap k2 a Source

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 Source

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

# Folds

foldr :: (a -> b -> b) -> b -> MultiMap k a -> b Source

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

foldl :: (a -> b -> a) -> a -> MultiMap k b -> a Source

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

foldrWithKey :: (k -> a -> b -> b) -> b -> MultiMap k a -> b Source

*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 Source

*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]] Source

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

assocs :: MultiMap k a -> [(k, [a])] Source

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

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

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

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

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

fromList xs == foldr (uncurry insert) empty

# Min/Max

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

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

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

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