HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Moduleunordered-containers-0.2.21Haskell2010

Data.HashMap.Strict

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.

The implementation is based on hash array mapped tries. A HashMap is often faster than other tree-based set types, especially when key comparison is expensive, as in the case of strings.

Many operations have a average-case complexity of O(\log n). The implementation uses a large base (i.e. 16 or 32) so in practice these operations are constant time.

  • 1 type
  • 56 values

Strictness properties

1 declaration

This module satisfies the following strictness properties:

  1. Key arguments are evaluated to WHNF;

  2. Keys and values are evaluated to WHNF before they are stored in the map.

datadata HashMap k v
#

A map from keys to values. A map cannot contain duplicate keys; each key can map to at most one value.

Instances27Bifoldable, Eq2, Ord2, Show2, NFData2, Hashable2, …
  • Bifoldable HashMapDefined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Eq2 HashMapDefined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Ord2 HashMapDefined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Show2 HashMapDefined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • NFData2 HashMapDefined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Hashable2 HashMapDefined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • (Lift k, Lift v) => Lift (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Functor (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Foldable (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Traversable (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Eq k => Eq1 (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Ord k => Ord1 (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • (Hashable k, Read k) => Read1 (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Show k => Show1 (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • NFData k => NFData1 (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Hashable k => Hashable1 (HashMap k)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Hashable k => IsList (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • (Eq k, Eq v) => Eq (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal

    Note that, in the presence of hash collisions, equal HashMaps may behave differently, i.e. extensionality may be violated:

    Example2 expressions
    data D = A | B deriving (Eq, Show)instance Hashable D where hashWithSalt salt _d = salt
    Example2 expressions
    x = fromList [(A,1), (B,2)]y = fromList [(B,2), (A,1)]
    Example3 expressions
    x == yTruetoList x[(A,1),(B,2)]toList y[(B,2),(A,1)]

    In general, the lack of extensionality can be observed with any function that depends on the key ordering, such as folds and traversals.

  • (Data k, Data v, Hashable k) => Data (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • (Ord k, Ord v) => Ord (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal

    The ordering is total and consistent with the Eq instance. However, nothing else about the ordering is specified, and it may change from version to version of either this package or of hashable.

  • (Hashable k, Read k, Read e) => Read (HashMap k e)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • (Show k, Show v) => Show (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • Hashable k => Semigroup (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal

    <> = union

    If a key occurs in both maps, the mapping from the first will be the mapping in the result.

    Examples
    Example1 expression
    fromList [(1,'a'),(2,'b')] <> fromList [(2,'c'),(3,'d')]fromList [(1,'a'),(2,'b'),(3,'d')]
  • Hashable k => Monoid (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal

    mempty = empty

    mappend = union

    If a key occurs in both maps, the mapping from the first will be the mapping in the result.

    Examples
    Example1 expression
    mappend (fromList [(1,'a'),(2,'b')]) (fromList [(2,'c'),(3,'d')])fromList [(1,'a'),(2,'b'),(3,'d')]
  • (NFData k, NFData v) => NFData (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • (Hashable k, Hashable v) => Hashable (HashMap k v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal
  • type Item (HashMap k v) = (k, v)Defined in unordered-containers-0.2.21 · Data.HashMap.Internal

Construction

2 declarations

Basic interface

18 declarations
valuesize :: HashMap k v -> Int
#

O(n) Return the number of key-value mappings in this map.

valuelookup :: Hashable k => k -> HashMap k v -> Maybe v
#

O(\log n) Return the value to which the specified key is mapped, or Nothing if this map contains no mapping for the key.

value(!?) :: Hashable k => HashMap k v -> k -> Maybe v
#

O(\log n) Return the value to which the specified key is mapped, or Nothing if this map contains no mapping for the key.

This is a flipped version of lookup.

valuefindWithDefault
  1. :: Hashable k
  2. => v

    Default value to return.

  3. -> k
  4. -> HashMap k v
  5. -> v
#

O(\log n) Return the value to which the specified key is mapped, or the default value if this map contains no mapping for the key.

valuelookupDefault
  1. :: Hashable k
  2. => v

    Default value to return.

  3. -> k
  4. -> HashMap k v
  5. -> v
#

O(\log n) Return the value to which the specified key is mapped, or the default value if this map contains no mapping for the key.

DEPRECATED: lookupDefault is deprecated as of version 0.2.11, replaced by findWithDefault.

value(!) :: (Hashable k, HasCallStack) => HashMap k v -> k -> v
#

O(\log n) Return the value to which the specified key is mapped. Calls error if this map contains no mapping for the key.

valuelookupKey :: Hashable k => k -> HashMap k v -> Maybe k
#

O(\log n) For a given key, return the equal key stored in the map, if present, otherwise return Nothing.

This function can be used for interning, i.e. to reduce memory usage.

valueinsert :: Hashable k => k -> v -> HashMap k v -> HashMap k v
#

O(\log n) 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.

valueinsertWith
  1. :: Hashable k
  2. => v -> v -> v
  3. -> k
  4. -> v
  5. -> HashMap k v
  6. -> HashMap k v
#

O(\log n) 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
valueadjust :: Hashable k => (v -> v) -> k -> HashMap k v -> HashMap k v
#

O(\log n) Adjust the value tied to a given key in this map only if it is present. Otherwise, leave the map alone.

valueupdate :: Hashable k => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a
#

O(\log n) The expression (update f k map) updates the value x at k (if it is in the map). If (f x) is Nothing, the element is deleted. If it is (Just y), the key k is bound to the new value y.

valuealter
  1. :: Hashable k
  2. => Maybe v -> Maybe v
  3. -> k
  4. -> HashMap k v
  5. -> HashMap k v
#

O(\log n) The expression (alter f k map) alters the value x at k, or absence thereof.

alter can be used to insert, delete, or update a value in a map. In short:

lookup k (alter f k m) = f (lookup k m)
valueisSubmapOf :: (Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool
#

O(n \log m) Inclusion of maps. A map is included in another map if the keys are subsets and the corresponding values are equal:

isSubmapOf m1 m2 = keys m1 `isSubsetOf` keys m2 &&
                   and [ v1 == v2 | (k1,v1) <- toList m1; let v2 = m2 ! k1 ]
Examples
Example1 expression
fromList [(1,'a')] `isSubmapOf` fromList [(1,'a'),(2,'b')]True
Example1 expression
fromList [(1,'a'),(2,'b')] `isSubmapOf` fromList [(1,'a')]False
valueisSubmapOfBy
  1. :: Hashable k
  2. => v1 -> v2 -> Bool
  3. -> HashMap k v1
  4. -> HashMap k v2
  5. -> Bool
#

O(n \log m) Inclusion of maps with value comparison. A map is included in another map if the keys are subsets and if the comparison function is true for the corresponding values:

isSubmapOfBy cmpV m1 m2 = keys m1 `isSubsetOf` keys m2 &&
                          and [ v1 `cmpV` v2 | (k1,v1) <- toList m1; let v2 = m2 ! k1 ]
Examples
Example1 expression
isSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])True
Example1 expression
isSubmapOfBy (<=) (fromList [(1,'b')]) (fromList [(1,'a'),(2,'c')])False

Combine

0 declarations

Union

valueunion :: Eq k => HashMap k v -> HashMap k v -> HashMap k v
#

O(n+m) The union of two maps. If a key occurs in both maps, the mapping from the first will be the mapping in the result.

Examples
Example1 expression
union (fromList [(1,'a'),(2,'b')]) (fromList [(2,'c'),(3,'d')])fromList [(1,'a'),(2,'b'),(3,'d')]
valueunionWith
  1. :: Eq k
  2. => v -> v -> v
  3. -> HashMap k v
  4. -> HashMap k v
  5. -> HashMap k v
#

O(n+m) The union of two maps. If a key occurs in both maps, the provided function (first argument) will be used to compute the result.

valueunionWithKey
  1. :: Eq k
  2. => k -> v -> v -> v
  3. -> HashMap k v
  4. -> HashMap k v
  5. -> HashMap k v
#

O(n+m) The union of two maps. If a key occurs in both maps, the provided function (first argument) will be used to compute the result.

valueunions :: Eq k => [HashMap k v] -> HashMap k v
#

Construct a set containing all elements from a list of sets.

Compose

valuecompose :: Hashable b => HashMap b c -> HashMap a b -> HashMap a c
#

Given maps bc and ab, relate the keys of ab to the values of bc, by using the values of ab as keys for lookups in bc.

Complexity: O (n * \log(m)) , where m is the size of the first argument

Example1 expression
compose (fromList [('a', "A"), ('b', "B")]) (fromList [(1,'a'),(2,'b'),(3,'z')])fromList [(1,"A"),(2,"B")]
(compose bc ab !?) = (bc !?) <=< (ab !?)

Transformations

4 declarations
valuemap :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
#

O(n) Transform this map by applying a function to every value.

valuemapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
#

O(n) Transform this map by applying a function to every value.

valuetraverseWithKey
  1. :: Applicative f
  2. => k -> v1 -> f v2
  3. -> HashMap k v1
  4. -> f (HashMap k v2)
#

O(n) Perform an Applicative action for each key-value pair in a HashMap and produce a HashMap of all the results. Each HashMap will be strict in all its values.

traverseWithKey f = fmap (map id) . Data.HashMap.Lazy.traverseWithKey f

Note: the order in which the actions occur is unspecified. In particular, when the map contains hash collisions, the order in which the actions associated with the keys involved will depend in an unspecified way on their insertion order.

valuemapKeys :: Hashable k2 => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v
#

O(n). mapKeys f s is the map obtained by applying f to each key of s.

The size of the result may be smaller if f maps two or more distinct keys to the same new key. In this case there is no guarantee which of the associated values is chosen for the conflicting key.

Example3 expressions
mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])fromList [(4,"b"),(6,"a")]mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])fromList [(1,"c")]mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])fromList [(3,"c")]

Difference and intersection

7 declarations
valuedifferenceWith
  1. :: Hashable k
  2. => v -> w -> Maybe v
  3. -> HashMap k v
  4. -> HashMap k w
  5. -> HashMap k v
#

O(n \log m) Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.

valuedifferenceWithKey
  1. :: Eq k
  2. => k -> v -> w -> Maybe v
  3. -> HashMap k v
  4. -> HashMap k w
  5. -> HashMap k v
#

O(n \log m) Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.

valueintersectionWith
  1. :: Eq k
  2. => v1 -> v2 -> v3
  3. -> HashMap k v1
  4. -> HashMap k v2
  5. -> HashMap k v3
#

O(n+m) Intersection of two maps. If a key occurs in both maps the provided function is used to combine the values from the two maps.

valueintersectionWithKey
  1. :: Eq k
  2. => k -> v1 -> v2 -> v3
  3. -> HashMap k v1
  4. -> HashMap k v2
  5. -> HashMap k v3
#

O(n+m) Intersection of two maps. If a key occurs in both maps the provided function is used to combine the values from the two maps.

valuedisjoint :: Eq k => HashMap k a -> HashMap k b -> Bool
#

O(n \log m) Check whether the key sets of two maps are disjoint (i.e., their intersection is empty).

xs `disjoint` ys = null (xs `intersection` ys)

Folds

9 declarations
valuefoldMapWithKey :: Monoid m => (k -> v -> m) -> HashMap k v -> m
#

O(n) Reduce the map by applying a function to each element and combining the results with a monoid operation.

valuefoldr :: (v -> a -> a) -> a -> HashMap k v -> a
#

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

valuefoldl :: (a -> v -> a) -> a -> HashMap k v -> a
#

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

valuefoldr' :: (v -> a -> a) -> a -> HashMap k v -> a
#

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). Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

valuefoldl' :: (a -> v -> a) -> a -> HashMap k v -> a
#

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 using the result in the next application. This function is strict in the starting value.

valuefoldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a
#

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). Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.

valuefoldlWithKey' :: (a -> k -> v -> a) -> a -> HashMap k v -> a
#

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 using the result in the next application. This function is strict in the starting value.

valuefoldrWithKey :: (k -> v -> a -> a) -> a -> HashMap k v -> a
#

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

valuefoldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a
#

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

Filter

4 declarations
valuefilter :: (v -> Bool) -> HashMap k v -> HashMap k v
#

O(n) Filter this map by retaining only elements which values satisfy a predicate.

valuemapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
#

O(n) Transform this map by applying a function to every value and retaining only some of them.

valuemapMaybeWithKey :: (k -> v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2
#

O(n) Transform this map by applying a function to every value and retaining only some of them.

Conversions

2 declarations
valuekeys :: HashMap k v -> [k]
#

O(n) Return a list of this map's keys. The list is produced lazily.

valueelems :: HashMap k v -> [v]
#

O(n) Return a list of this map's values. The list is produced lazily.

Lists

valuetoList :: HashMap k v -> [(k, v)]
#

O(n) Return a list of this map's elements. The list is produced lazily. The order of its elements is unspecified, and it may change from version to version of either this package or of hashable.

valuefromList :: Hashable k => [(k, v)] -> HashMap k v
#

O(n \log n) Construct a map with the supplied mappings. If the list contains duplicate mappings, the later mappings take precedence.

valuefromListWith :: Hashable k => (v -> v -> v) -> [(k, v)] -> HashMap k v
#

O(n \log n) Construct a map from a list of elements. Uses the provided function f to merge duplicate entries with (f newVal oldVal).

Examples

Given a list xs, create a map with the number of occurrences of each element in xs:

let xs = ['a', 'b', 'a']
in fromListWith (+) [ (x, 1) | x <- xs ]

= fromList [('a', 2), ('b', 1)]

Given a list of key-value pairs xs :: [(k, v)], group all values by their keys and return a HashMap k [v].

let xs = ('a', 1), ('b', 2), ('a', 3)]
in fromListWith (++) [ (k, [v]) | (k, v) <- xs ]

= fromList [('a', [3, 1]), ('b', [2])]

Note that the lists in the resulting map contain elements in reverse order from their occurrences in the original list.

More generally, duplicate entries are accumulated as follows; this matters when f is not commutative or not associative.

fromListWith f [(k, a), (k, b), (k, c), (k, d)]
= fromList [(k, f d (f c (f b a)))]
valuefromListWithKey
  1. :: Hashable k
  2. => k -> v -> v -> v
  3. -> [(k, v)]
  4. -> HashMap k v
#

O(n \log n) Construct a map from a list of elements. Uses the provided function to merge duplicate entries.

Examples

Given a list of key-value pairs where the keys are of different flavours, e.g:

data Key = Div | Sub

and the values need to be combined differently when there are duplicates, depending on the key:

combine Div = div
combine Sub = (-)

then fromListWithKey can be used as follows:

fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)]
= fromList [(Div, 3), (Sub, 1)]

More generally, duplicate entries are accumulated as follows;

fromListWith f [(k, a), (k, b), (k, c), (k, d)]
= fromList [(k, f k d (f k c (f k b a)))]

HashSets

valuekeysSet :: HashMap k a -> HashSet k
#

O(n) Produce a HashSet of all the keys in the given HashMap.

Example1 expression
HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")]fromList [1,2]