Copyright | 2010-2012 Johan Tibell |
---|---|

License | BSD-style |

Maintainer | johan.tibell@gmail.com |

Stability | provisional |

Portability | portable |

Safe Haskell | Trustworthy |

Language | Haskell98 |

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) so in practice these
operations are constant time.

- 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
- member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool
- lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v
- lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v
- (!) :: (Eq k, Hashable k) => HashMap k v -> k -> v
- insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v
- insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v
- delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v
- adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v
- union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v
- unionWith :: (Eq k, Hashable k) => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v
- unions :: (Eq k, Hashable k) => [HashMap k v] -> HashMap k v
- map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2
- mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2
- traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)
- difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v
- intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v
- intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3
- 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 :: forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v
- keys :: HashMap k v -> [k]
- elems :: HashMap k v -> [v]
- toList :: HashMap k v -> [(k, v)]
- fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v
- fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

# Strictness properties

This module satisfies the following strictness properties:

- Key arguments are evaluated to WHNF;
- Keys and values are evaluated to WHNF before they are stored in the map.

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

Functor (HashMap k) | |

Foldable (HashMap k) | |

Traversable (HashMap k) | |

(Eq k, Hashable k) => IsList (HashMap k v) | |

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

(Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) | |

(Eq k, Hashable k, Read k, Read e) => Read (HashMap k e) | |

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

(Eq k, Hashable k) => Monoid (HashMap k v) | |

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

Typeable (* -> * -> *) HashMap | |

type Item (HashMap k v) = (k, v) |

# Construction

# Basic interface

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

*O(log n)* Return the value to which the specified key is mapped,
or `Nothing`

if this map contains no mapping for the key.

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

(!) :: (Eq k, Hashable k) => HashMap k v -> k -> v infixl 9 Source

*O(log n)* Return the value to which the specified key is mapped.
Calls `error`

if this map contains no mapping for the key.

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

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

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

*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

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

*O(log n)* Remove the mapping for the specified key from this map
if present.

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

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

# Combine

## Union

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

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

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

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

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

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

# Transformations

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

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

mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2 Source

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

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

# Difference and intersection

difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v Source

*O(n*log m)* Difference of two maps. Return elements of the first map
not existing in the second.

intersection :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v Source

*O(n*log m)* Intersection of two maps. Return elements of the first
map for keys existing in the second.

intersectionWith :: (Eq k, Hashable k) => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3 Source

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

# Folds

foldl' :: (a -> v -> a) -> a -> HashMap k v -> a Source

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

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

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

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

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

filterWithKey :: forall k v. (k -> v -> Bool) -> HashMap k v -> HashMap k v Source

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

# Conversions

keys :: HashMap k v -> [k] Source

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

elems :: HashMap k v -> [v] Source

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

## Lists

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

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

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

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

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