Copyright  20102012 Johan Tibell 

License  BSDstyle 
Maintainer  johan.tibell@gmail.com 
Stability  provisional 
Portability  portable 
Safe Haskell  Trustworthy 
Language  Haskell2010 
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 treebased set types,
especially when key comparison is expensive, as in the case of
strings.
Many operations have a averagecase complexity of O(log n). The implementation uses a large base (i.e. 16) so in practice these operations are constant time.
Synopsis
 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
 update :: (Eq k, Hashable k) => (a > Maybe a) > k > HashMap k a > HashMap k a
 alter :: (Eq k, Hashable k) => (Maybe v > Maybe v) > k > HashMap k v > HashMap k v
 alterF :: (Functor f, Eq k, Hashable k) => (Maybe v > f (Maybe v)) > k > HashMap k v > f (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
 unionWithKey :: (Eq k, Hashable k) => (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
 differenceWith :: (Eq k, Hashable k) => (v > w > Maybe v) > 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
 intersectionWithKey :: (Eq k, Hashable k) => (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
 mapMaybe :: (v1 > Maybe v2) > HashMap k v1 > HashMap k v2
 mapMaybeWithKey :: (k > v1 > Maybe v2) > HashMap k v1 > HashMap k v2
 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
 keysSet :: HashMap k a > HashSet k
Strictness properties
This module satisfies the following strictness property:
 Key arguments are evaluated to WHNF
A map from keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
Instances
Eq2 HashMap Source #  
Ord2 HashMap Source #  
Defined in Data.HashMap.Base  
Show2 HashMap Source #  
Hashable2 HashMap Source #  
Defined in Data.HashMap.Base  
Functor (HashMap k) Source #  
Foldable (HashMap k) Source #  
Defined in Data.HashMap.Base fold :: Monoid m => HashMap k m > m Source # foldMap :: Monoid m => (a > m) > HashMap k a > m Source # foldr :: (a > b > b) > b > HashMap k a > b Source # foldr' :: (a > b > b) > b > HashMap k a > b Source # foldl :: (b > a > b) > b > HashMap k a > b Source # foldl' :: (b > a > b) > b > HashMap k a > b Source # foldr1 :: (a > a > a) > HashMap k a > a Source # foldl1 :: (a > a > a) > HashMap k a > a Source # toList :: HashMap k a > [a] Source # null :: HashMap k a > Bool Source # length :: HashMap k a > Int Source # elem :: Eq a => a > HashMap k a > Bool Source # maximum :: Ord a => HashMap k a > a Source # minimum :: Ord a => HashMap k a > a Source #  
Traversable (HashMap k) Source #  
Defined in Data.HashMap.Base  
Eq k => Eq1 (HashMap k) Source #  
Ord k => Ord1 (HashMap k) Source #  
Defined in Data.HashMap.Base  
(Eq k, Hashable k, Read k) => Read1 (HashMap k) Source #  
Defined in Data.HashMap.Base liftReadsPrec :: (Int > ReadS a) > ReadS [a] > Int > ReadS (HashMap k a) Source # liftReadList :: (Int > ReadS a) > ReadS [a] > ReadS [HashMap k a] Source # liftReadPrec :: ReadPrec a > ReadPrec [a] > ReadPrec (HashMap k a) Source # liftReadListPrec :: ReadPrec a > ReadPrec [a] > ReadPrec [HashMap k a] Source #  
Show k => Show1 (HashMap k) Source #  
Hashable k => Hashable1 (HashMap k) Source #  
Defined in Data.HashMap.Base  
(Eq k, Hashable k) => IsList (HashMap k v) Source #  
(Eq k, Eq v) => Eq (HashMap k v) Source #  
(Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) Source #  
Defined in Data.HashMap.Base gfoldl :: (forall d b. Data d => c (d > b) > d > c b) > (forall g. g > c g) > HashMap k v > c (HashMap k v) Source # gunfold :: (forall b r. Data b => c (b > r) > c r) > (forall r. r > c r) > Constr > c (HashMap k v) Source # toConstr :: HashMap k v > Constr Source # dataTypeOf :: HashMap k v > DataType Source # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) > Maybe (c (HashMap k v)) Source # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) > Maybe (c (HashMap k v)) Source # gmapT :: (forall b. Data b => b > b) > HashMap k v > HashMap k v Source # gmapQl :: (r > r' > r) > r > (forall d. Data d => d > r') > HashMap k v > r Source # gmapQr :: (r' > r > r) > r > (forall d. Data d => d > r') > HashMap k v > r Source # gmapQ :: (forall d. Data d => d > u) > HashMap k v > [u] Source # gmapQi :: Int > (forall d. Data d => d > u) > HashMap k v > u Source # gmapM :: Monad m => (forall d. Data d => d > m d) > HashMap k v > m (HashMap k v) Source # gmapMp :: MonadPlus m => (forall d. Data d => d > m d) > HashMap k v > m (HashMap k v) Source # gmapMo :: MonadPlus m => (forall d. Data d => d > m d) > HashMap k v > m (HashMap k v) Source #  
(Ord k, Ord v) => Ord (HashMap k v) Source #  The order is total. Note: Because the hash is not guaranteed to be stable across library
versions, OSes, or architectures, neither is an actual order of elements in

Defined in Data.HashMap.Base compare :: HashMap k v > HashMap k v > Ordering Source # (<) :: HashMap k v > HashMap k v > Bool Source # (<=) :: HashMap k v > HashMap k v > Bool Source # (>) :: HashMap k v > HashMap k v > Bool Source # (>=) :: HashMap k v > HashMap k v > Bool Source #  
(Eq k, Hashable k, Read k, Read e) => Read (HashMap k e) Source #  
(Show k, Show v) => Show (HashMap k v) Source #  
(Eq k, Hashable k) => Semigroup (HashMap k v) Source #  
(Eq k, Hashable k) => Monoid (HashMap k v) Source #  
(NFData k, NFData v) => NFData (HashMap k v) Source #  
Defined in Data.HashMap.Base  
(Hashable k, Hashable v) => Hashable (HashMap k v) Source #  
Defined in Data.HashMap.Base  
type Item (HashMap k v) Source #  
Defined in Data.HashMap.Base 
Construction
singleton :: Hashable k => k > v > HashMap k v Source #
O(1) Construct a map with a single element.
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.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v > f (Maybe v)) > k > HashMap k v > f (HashMap k v) Source #
O(log n) The expression (
) alters the value alterF
f k mapx
at
k
, or absence thereof. alterF
can be used to insert, delete, or update
a value in a map.
Note: alterF
is a flipped version of the at
combinator from
Control.Lens.At.
Since: 0.2.9
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.
unionWithKey :: (Eq k, Hashable k) => (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) Perform an Applicative
action for each keyvalue pair
in a HashMap
and produce a HashMap
of all the results.
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.
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.
differenceWith :: (Eq k, Hashable k) => (v > w > Maybe v) > HashMap k v > HashMap k w > HashMap k v Source #
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.
intersectionWithKey :: (Eq k, Hashable k) => (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 leftidentity 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.
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 leftidentity 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.
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 rightidentity 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 rightidentity 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.
mapMaybe :: (v1 > Maybe v2) > HashMap k v1 > HashMap k v2 Source #
O(n) Transform this map by applying a function to every value and retaining only some of them.
mapMaybeWithKey :: (k > v1 > Maybe v2) > HashMap k v1 > HashMap k v2 Source #
O(n) Transform this map by applying a function to every value and retaining only some of them.
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. The order of its elements is unspecified.
fromList :: (Eq k, Hashable k) => [(k, v)] > HashMap k v Source #
O(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.