Portability | portable |
---|---|
Stability | provisional |
Maintainer | johan.tibell@gmail.com |
A map from hashable keys to values. A map cannot contain
duplicate keys; each key can map to at most one value. A HashMap
makes no guarantees as to the order of its elements.
This map is strict in the keys and lazy in the values; keys are evaluated to weak head normal form before they are added to the map.
The implementation is based on big-endian patricia trees, keyed
by a hash of the original key. A HashMap
is often faster than
other tree-based maps, especially when key comparison is expensive,
as in the case of strings.
Many operations have a worst-case complexity of O(min(n,W)).
This means that the operation can become linear in the number of
elements with a maximum of W -- the number of bits in an Int
(32 or 64).
- data HashMap k v
- empty :: HashMap k v
- singleton :: Hashable k => k -> v -> HashMap k v
- null :: HashMap k v -> Bool
- size :: HashMap k v -> Int
- lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
- insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
- delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
- insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
- map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
- foldl' :: (a -> v -> a) -> a -> HashMap k v -> a
- foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a
- foldr :: (v -> a -> a) -> a -> HashMap k v -> a
- foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a
- filter :: (v -> Bool) -> HashMap k v -> HashMap k v
- filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v
- elems :: HashMap k v -> [v]
- keys :: HashMap k v -> [k]
- toList :: HashMap k v -> [(k, v)]
- fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v
Documentation
A map from keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
Construction
Basic interface
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe vSource
O(min(n,W)) Return the value to which the specified key is
mapped, or Nothing
if this map contains no mapping for the key.
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k vSource
O(min(n,W)) Associate the specified value with the specified key in this map. If this map previously contained a mapping for the key, the old value is replaced.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k vSource
O(min(n,W)) Remove the mapping for the specified key from this map if present.
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k vSource
O(min(n,W)) Associate the value with the key in this map. If this map previously contained a mapping for the key, the old value is replaced by the result of applying the given function to the new and old value. Example:
insertWith f k v map where f new old = new + old
Transformations
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2Source
O(n) Transform this map by applying a function to every value.
Folds
foldl' :: (a -> v -> a) -> a -> HashMap k v -> aSource
O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the left-identity of the operator). Each application of the operator is evaluated before before using the result in the next application. This function is strict in the starting value.
foldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> aSource
O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the left-identity of the operator). Each application of the operator is evaluated before before using the result in the next application. This function is strict in the starting value.
foldr :: (v -> a -> a) -> a -> HashMap k v -> aSource
O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).
foldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> aSource
O(n) Reduce this map by applying a binary operator to all elements, using the given starting value (typically the right-identity of the operator).
Filter
filter :: (v -> Bool) -> HashMap k v -> HashMap k vSource
O(n) Filter this map by retaining only elements which values satisfy a predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k vSource
O(n) Filter this map by retaining only elements satisfying a predicate.
Conversions
elems :: HashMap k v -> [v]Source
O(n) Return a list of this map's values. The list is produced lazily.