Data.HashMap.Lazy

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

Documentation

data HashMap k v

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

Instances

Functor (HashMap k)

Foldable (HashMap k)

Traversable (HashMap k)

(Eq k, Eq v) => Eq (HashMap k v)

(Show k, Show v) => Show (HashMap k v)

(NFData k, NFData v) => NFData (HashMap k v)

Construction

empty :: HashMap k v

O(1) Construct an empty map.

singleton :: Hashable k => k -> v -> HashMap k v

O(1) Construct a map with a single element.

Basic interface

null :: HashMap k v -> Bool

O(1) Return True if this map is empty, False otherwise.

size :: HashMap k v -> Int

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

lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v

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.

lookupDefault

Arguments

:: (Eq k, Hashable k)

=> v

Default value to return.

-> k

-> HashMap k v

-> v

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

insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

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 v

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 v

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

adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v

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

Transformations

map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2

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

traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)

O(n) Transform this map by accumulating an Applicative result from every value.

Folds

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

foldr :: (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).

foldrWithKey :: (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).

Filter

filter :: (v -> Bool) -> HashMap k v -> HashMap k v

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

filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v

O(n) Filter this map by retaining only elements satisfying a predicate.

Conversions

elems :: HashMap k v -> [v]

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

keys :: HashMap k v -> [k]

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

Lists

toList :: HashMap k v -> [(k, v)]

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

fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v

O(n*min(W, n)) Construct a map from a list of elements.