Module Data.HashMap

A HashMap implementation based on a Hash Array Mapped Trie

The hash array mapped trie achieves almost hash table-like speed while using memory much more economically. Also, a hash table may have to be periodically resized, an expensive operation, whereas HAMTs grow and shrink dynamically.

Comparison with Data.TreeMap

Advantages of the HashMap

The hash map can be used with key types that do not have a Ord instance.
It is less affected by slow implementations of the (Eq.==) operation on keys.
There is less aggregated memory overhead per key/value pair.

Disadvantages of the HashMap

Performance is severely affected when the hashing function tends to produce many collisions.
It does not support getting the minimum/maximum key in logarithmic time, nor processing in key order in linear time.

Creating Hash Maps

Get an empty map with Monoid.mempty or ListEmpty.empty, make a singleton one with singleton or turn an association list into a HashMap with fromList. The more general function fromListWith allows custom handling of associations with duplicate keys.

Add, Change or Remove Associations

Use insert, delete, adjust and replace. The more general form of insert is insertWith which accepts a function to combine the given value with an already existing one.

Lookups

The basic function is lookup, of which member and lookupDefault are variants. The operator (!!) may be used when the existence of the keys looked for is out of the question.

Set operations

There is union, difference and intersection. More general functions unionWith and intersectionWith allow combination of the affected values.

Folds

Left folds as well as right folds are provided by foldValues and foldrValues. Variants foldWithKey and foldrWithKey allow examination not only of the value, but also of the key.

Frequently needed functions such as values, keys, each and size are just predefined folds for your convenience.

Filtering

Create a subset of an existing map with filterValues or filterWithKey.

Transformations

mapValues, mapWithKey and traverseWithKey should cover any need to transform an existing map.

Naming Conventions

Functions whose name have the With suffix take a custom function to combine two values and are thus more general than the ones without that suffix. Most often it is the case that

 xxx = xxxWith const

Functions whose name have the Values suffix operate on the values of the mappings contained in the map and take an appropriate custom function as argument. The Values suffix also serves to avoid conflicts with Prelude functions (i.e. map, filter, Foldable.fold, Foldable.foldr).

The companions of the Values functions have the suffix WithKey and accept functions that take an extra argument for the key. The key portion of a mapping or association is always passed first, followed by the associated value.

Imports

import Data.Bits as Bits
import Data.Foldable as Foldable
import Data.JSON as JSON
import Data.List as List
import Data.Monoid as Monoid
import frege.Prelude as Prelude
import Prelude.PreludeArrays as PreludeArrays
import Prelude.PreludeBase as PreludeBase
import Prelude.PreludeDecimal as PreludeDecimal
import Prelude.PreludeIO as PreludeIO
import Prelude.PreludeList as PreludeList
import Prelude.PreludeMonad as PreludeMonad
import Prelude.PreludeText as PreludeText
import Java.util.Regex as Regexp
import Data.Traversable as Traversable

Table of Content

Definitions

data HashMap k v

singleton ∷ Eq k ⇒ k → v → HashMap k v

size ∷ HashMap k v → Int

values ∷ HashMap k v → [v]

keys ∷ HashMap k v → [k]

each ∷ HashMap k v → [(k, v)]

insert ∷ Eq k ⇒ k → v → HashMap k v → HashMap k v

insertWith ∷ Eq k ⇒ (v → v → v) → k → v → HashMap k v → HashMap k v

delete ∷ Eq k ⇒ k → HashMap k v → HashMap k v

lookup ∷ Eq k ⇒ k → HashMap k v → Maybe v

member ∷ Eq k ⇒ k → HashMap k v → Bool

lookupDefault ∷ Eq k ⇒ v → k → HashMap k v → v

!! ∷ Eq k ⇒ HashMap k v → k → v

adjust ∷ Eq k ⇒ (v → v) → k → HashMap k v → HashMap k v

replace ∷ Eq k ⇒ k → v → HashMap k v → HashMap k v

unionWith ∷ Eq k ⇒ (v → v → v) → HashMap k v → HashMap k v → HashMap k v

union ∷ Eq k ⇒ HashMap k v → HashMap k v → HashMap k v

unions ∷ Eq k ⇒ [HashMap k v] → HashMap k v

foldWithKey ∷ (a → k → v → a) → a → HashMap k v → a

foldValues ∷ (a → v → a) → a → HashMap k v → a

foldrValues ∷ (v → a → a) → a → HashMap k v → a

foldrWithKey ∷ (k → v → a → a) → a → HashMap k v → a

mapValues ∷ (v → u) → HashMap k v → HashMap k u

mapWithKey ∷ (k → v → u) → HashMap k v → HashMap k u

traverseWithKey ∷ Applicative a ⇒ (k → v → a u) → HashMap k v → a (HashMap k u)

filterWithKey ∷ (k → v → Bool) → HashMap k v → HashMap k v

filterValues ∷ (v → Bool) → HashMap k v → HashMap k v

difference ∷ Eq k ⇒ HashMap k v → HashMap k u → HashMap k v

intersection ∷ Eq k ⇒ HashMap k v → HashMap k u → HashMap k v

intersectionWith ∷ Eq k ⇒ (v → u → w) → HashMap k v → HashMap k u → HashMap k w

fromList ∷ Eq k ⇒ [(k, v)] → HashMap k v

fromListWith ∷ Eq k ⇒ (v → v → v) → [(k, v)] → HashMap k v
Instances

instance ArrayElement (HashMap k v)

instance (Eq k, Eq v) ⇒ Eq (HashMap k v)

instance Foldable (HashMap k)

instance Functor (HashMap k)

instance ListEmpty (HashMap k)

instance Eq k ⇒ ListMonoid (HashMap k)

instance ListSource (HashMap k)

instance Eq k ⇒ Monoid (HashMap k v)

instance (ToJSON k, ToJSON v) ⇒ Show (HashMap k v)

instance (ToJSON k, ToJSON v) ⇒ ToJSON (HashMap k v)

instance Traversable (HashMap k)
Functions and Values by Type

Definitions

singleton ∷ Eq k ⇒ k → v → HashMap k v

O(1) Create a singleton map

size ∷ HashMap k v → Int

O(n) Compute the size of the map

values ∷ HashMap k v → [v]

O(n) Retrieve a list of the values in the map

keys ∷ HashMap k v → [k]

O(n) Retrieve a list of the keys in the map

each ∷ HashMap k v → [(k, v)]

O(n) Retrieve a list of the associations in the map

insert ∷ Eq k ⇒ k → v → HashMap k v → HashMap k v

O(log n)

 insert k v m

is a HashMap h such that

 lookup k h = Just v

and lookup for any other key o

 lookup o h = lookup o m

Less formally said, k is associated with v in the resulting map, updating a previously existing association of k if it exists, while all other associations are left untouched.

In the case of an update, the new value will get forced, see insertWith for details.

insertWith ∷ Eq k ⇒ (v → v → v) → k → v → HashMap k v → HashMap k v

O(log n)

 insertWith f k v m

If m does not contain k, this works like insert. Otherwise, the existing association of k with some value v' is replaced by an association of k with the result of evaluating

 f v v'

in the resulting map.

Strict evaluation is necessary to prevent building up of large thunks of the form

 f v3 (f v2 (f v1 v0))

Note that

 insert = insertWith const

and that this will evaluate the new value in case of an update. If you want to prevent this, use

 replace k v = insert k v . delete k

The replaced value will be evaluated only if the given function is strict in the second argument. Since const is lazy in the second argument, the following will be fine:

 insert "foo" 7 (insert "foo" undefined (delete "foo" m))

That is, the value that is inserted for a given key first is not evaluated on insertion, and only evaluated on update if the update function demands it, which is not the case for a plain insert.

delete ∷ Eq k ⇒ k → HashMap k v → HashMap k v

O(log n)

 delete k m

is a HashMap h such that

 lookup k h = Nothing

and for any other key o

 lookup o h = lookup o m

Less formally, the association of k with some value, if any, is removed in the result, while all other associations are retained.

If m didn't contain k in the first place,

 delete k m = m

lookup ∷ Eq k ⇒ k → HashMap k v → Maybe v

O(log n)

 lookup k m

If k is associated with some value v in map m, it returns

 Just v

and otherwise

 Nothing

member ∷ Eq k ⇒ k → HashMap k v → Bool

O(log n)

Checks whether the key is present in the map

lookupDefault ∷ Eq k ⇒ v → k → HashMap k v → 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.

!! ∷ Eq k ⇒ HashMap k v → k → v

O(log n)

Return the value associated with the given key in the map. Fails with error if the key is not present.

adjust ∷ Eq 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.

replace ∷ Eq k ⇒ k → v → HashMap k v → HashMap k v

O(log n)

 replace k v m = insert k v . delete k $ m

Insert or update the association of k with v in m but avoid evaluation of v even if m already contains k.

See also notes concerning updates on function insertWith.

unionWith ∷ Eq k ⇒ (v → v → v) → HashMap k v → HashMap k v → HashMap k v

O(m*log n)

Computes the union of two hash maps.

If a key occurs in both maps, the function provided in the first argument will be used to compute the result in the same way as insertWith would do it, that is, the value from the left hash map will be evaluated while the value from the right map may be evaluated only if the function demands it. However, values associated with keys that are member of only one map are left alone.

union ∷ Eq k ⇒ HashMap k v → HashMap k v → HashMap k v

O(m*log n)

Computes the union of two hash maps.

If a key occurs in both maps, the value from the left map will be evaluated and taken over to the new map.

Because

 union  =  unionWith const

the considerations concerning strictness apply for union in the same way as for unionWith.

unions ∷ Eq k ⇒ [HashMap k v] → HashMap k v

The union of all HashMaps in a list.

foldWithKey ∷ (a → k → v → a) → a → HashMap k v → a

O(n)

Reduce this map by applying a function to all associations, using the given starting value (typically the left-identity of the operator). Each application of the function is evaluated before using the result in the next application.

This function is strict in the starting value.

foldValues ∷ (a → v → a) → a → HashMap k v → a

O(n)

Reduce this map by applying a binary operator to all values, 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.

foldrValues ∷ (v → a → a) → a → HashMap k v → a

O(n)

Reduce this map by applying a binary operator to all values, using the given starting value (typically the right-identity of the operator).

Warning: this function exists for Haskell compatibility only. Please be aware that right folds suffer from the danger of stack overflows, while left folds don't and are also faster because of tail recursion. Since the order of values is arbitrary anyway, there is often no good reason to insist on a right fold, so please use foldValues instead.

foldrWithKey ∷ (k → v → a → a) → a → HashMap k v → a

O(n)

Reduce this map by applying a binary operator to all mappings, using the given starting value (typically the right-identity of the operator).

mapValues ∷ (v → u) → HashMap k v → HashMap k u

O(n)

Transform a map by applying a function to every value.

mapWithKey ∷ (k → v → u) → HashMap k v → HashMap k u

O(n)

Transform a map by applying a function to every key and its associated value.

traverseWithKey ∷ Applicative a ⇒ (k → v → a u) → HashMap k v → a (HashMap k u)

O(n)

Transform a map by applying an applicative functor to every key and its associated value.

filterWithKey ∷ (k → v → Bool) → HashMap k v → HashMap k v

O(n)

Filter a map, retaining only mappings whose key and value satisfy a given predicate.

filterValues ∷ (v → Bool) → HashMap k v → HashMap k v

O(n)

Filter a map, retaining only mappings whose value satisfies a given predicate.

difference ∷ Eq k ⇒ HashMap k v → HashMap k u → HashMap k v

O(n*log m)

Computes the difference of two maps.

Returns a map that contains the mappings of the first map whose keys do not exist in the second.

intersection ∷ Eq k ⇒ HashMap k v → HashMap k u → HashMap k v

O(n*log m)

Computes the intersection of two maps.

Return a map that contains the mappings of the first map for keys that also exist in the second.

intersectionWith ∷ Eq k ⇒ (v → u → w) → HashMap k v → HashMap k u → HashMap k w

O(n*log m)

Computes the intersection of two maps, combining the values with a given function.

fromList ∷ Eq k ⇒ [(k, v)] → HashMap k v

O(n)

Build a map from an association list. If the list contains duplicate mappings, the later mappings take precedence.

fromListWith ∷ Eq k ⇒ (v → v → v) → [(k, v)] → HashMap k v

O(n)

Build a map from an association list. Uses the provided function to merge values associated with duplicate keys.

data HashMap k v

A map from hashable keys to values based on a Hash Mapped Array Trie.

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.

A node of the HashMap is either

a key/value pair
a list of key/value tuples with pair-wise different keys, where the hash code for all keys is identical (collisions). In the (hopefully) unlikely case of such collisions, the performance of operations using the affected keys degrades to that of similar operations on lists. However, collision lists should be short, if occurring at all.
a bitmapped node with a bitmap of size 32 to indicate absence or presence of sub-nodes, followed by an array of up to 32 (sub)nodes.

This implementation of a persistent hash array mapped trie uses 32 bit hash values as provided by Java and the Frege Eq type class.

To find a value, the search starts with the root node. If the node is a key/value pair, the node's key is compared to the search key. When the keys are equal, the value is returned, otherwise the key is not in the map.

If the node is a bitmapped node, the hash code of the lookup key is computed and the presence of the index provided by the last five bits is checked in the bitmap. If it is there, the search continues with the corresponding node from the node array, otherwise the key is not in the map. With every recursion, the next five bits of the hash code will be used for indexing.

It remains the case that the node is a collision list. The searched key's hashcode either is the same as the one of the keys in the collision list, in which case the search degrades to a sequential search in that list, or it is different, and in the latter case we know that the key is not in the map without even touching the list.

Hence, the worst case in searching must do the following:

1 time: compute the hash code of the key
7 times: find the next node through the sub-node array. This is in essence computation of an index with bit operations, followed by a memory read. The reason this is done at max 7 times is that it consumes 5 bits of the hash code every time. With 32 bit hash codes, we have 6 5-bit quantities that can range from 0 to 31, while the last 5-bit quantity has only 2 significant bits, the other ones are always zero. The hashmapped nodes at the 7th level of the map will consequently have at most 4 sub-nodes. (Note that this is an intrinsic limit that is determined by the hash code bit size, not by the algorithm. Should later Java versions choose to provide Long bitcodes, for example, this code will still work with marginal adjustments, just that there would be 13 levels of bitmapped nodes instead of 7.)
n times: comparison with the keys in the collision list, where n is the number of elements of the collision list, or comparison with the key of a key/value node (this is equivalent to a collision list of length 1).

It turns out that - absent hash collisions - lookups will be done almost in constant time. And so will be inserts and deletes, although with a slightly larger constant factor due to the house-keeping necessary for a persistent data structure. However, even this are in the worst case 7 array copies, where 6 of them may be of size 32 and one of size 4. Assuming that the pointers are 4 bytes long, this amounts to copying at most 196*4 bytes of memory.

The map can have at most 2^32 non-bitmapped nodes maintained in 1+32+1024+32768+1048576+33554432+1073741824 bitmapped nodes. But because collision lists can be arbitrary long, the total number of key/value pairs is not limited.

Constructors

private BM {subnodes ∷ JArray (HashMap k v), bitmap ∷ Int}

Bitmapped node. It has a bitmap of 32 bits that indicate presence or absence of a sub node for a given index which is in the range [0..31], and an array of sub nodes. The size of the array is equal to the number of 1-bits in the bitmap. An index is mapped to an actual array index like so: If the corresponding Bits.bit is set in the bitmap, the number of less significant 1-bits in the bitmap is counted with Bits.bitCount and this is then the index in the array. Otherwise there is no sub node for that index.

Invariant 1: The length of subnodes equals the number of set bits in bitmap.
Invariant 2: There is no null pointer in subnodes.
Invariant 3: No subnode is the empty node.

private CO {hash ∷ Int, list ∷ [(k, v)]}

Collision node, holding a list of key/value tuples as well as the Eq.hashCode all keys have in common. This helps us avoid touching the list when the sought key has a different hash code.

Invariant 1: length of list is at least 2.
Invariant 2: all keys in list are different.

private KV {hash ∷ Int, key ∷ k, value ∷ v}

Singleton node holding a key with a value. Also caches the Eq.hashCode of the key to avoid possibly expensive recomputation.

Member Functions

bitmap ∷ HashMap α β → Int

access field bitmap

collisions ∷ HashMap β α → (Int, Int, [[β]])

O(n) Compute a 3-tuple of

the number of collision nodes
the total number of keys that have a collision
a list of lists of colliding keys

delete ∷ Eq k ⇒ HashMap k v → k → HashMap k v

O(log n)

 hm.delete k

Variant of delete that is better suited for left folds and supports dot-notation.

hash ∷ HashMap α β → Int

access field hash

indexMap ∷ Int → Int → Int → Int

transform an index into an actual array index

 indexMap bmap nodes inx

bmap is the bitmap

nodes is the number of actual subnodes

inx is a hash code or part of a hash code, whose least significant 5 bits are the index

returns a number in the range 0..nodes, where nodes means "no corresponding node"

insert ∷ Eq k ⇒ HashMap k v → k → v → HashMap k v

O(log n)

 hm.insert k v

Variant of insert that is better suited for left folds and supports dot-notation.

invariants ∷ Eq k ⇒ HashMap k v → Bool

this checks the invariants for a node

key ∷ HashMap α β → α

access field key

list ∷ HashMap α β → [(α, β)]

access field list

lookup ∷ Eq k ⇒ HashMap k v → k → Maybe v

O(log n)

 hm.lookup k

Variant of lookup that supports dot-notation.

subnodes ∷ HashMap α β → JArray (HashMap α β)

access field subnodes

value ∷ HashMap β α → α

access field value

Instances

instance ArrayElement (HashMap k v)

Member Functions

arrayFromIndexList ∷ [(Int, HashMap β α)] → JArray (HashMap β α): inherited from ArrayElement.arrayFromIndexList
arrayFromIndexListST ∷ [(Int, HashMap β α)] → STMutable γ (JArray (HashMap β α)): inherited from ArrayElement.arrayFromIndexListST
arrayFromList ∷ [HashMap β α] → JArray (HashMap β α): inherited from ArrayElement.arrayFromList
arrayFromListST ∷ [HashMap β α] → STMutable γ (JArray (HashMap β α)): inherited from ArrayElement.arrayFromListST
arrayFromMaybeList ∷ [Maybe (HashMap β α)] → JArray (HashMap β α): inherited from ArrayElement.arrayFromMaybeList
arrayFromMaybeListST ∷ [Maybe (HashMap β α)] → STMutable γ (JArray (HashMap β α)): inherited from ArrayElement.arrayFromMaybeListST
arrayLength ∷ JArray (HashMap β α) → Int
pure native .length: inherited from ArrayElement.arrayLength
elemAt ∷ JArray (HashMap β α) → Int → HashMap β α
pure native [i]: inherited from ArrayElement.elemAt
getAt ∷ ArrayOf γ (HashMap β α) → Int → ST γ (Maybe (HashMap β α))
native [i]: inherited from ArrayElement.getAt
getElemAt ∷ ArrayOf γ (HashMap β α) → Int → ST γ (HashMap β α)
native [i]: inherited from ArrayElement.getElemAt
itemAt ∷ JArray (HashMap β α) → Int → Maybe (HashMap β α)
pure native [i]: inherited from ArrayElement.itemAt
javaClass ∷ Class (HashMap β α)
pure native THashMap.class
listFromArray ∷ JArray (HashMap β α) → [HashMap β α]: inherited from ArrayElement.listFromArray
maybeListFromArray ∷ JArray (HashMap β α) → [Maybe (HashMap β α)]: inherited from ArrayElement.maybeListFromArray
modifyAt ∷ (HashMap β α → HashMap β α) → ArrayOf γ (HashMap β α) → Int → ST γ (): inherited from ArrayElement.modifyAt
modifyElemAt ∷ (HashMap β α → HashMap β α) → ArrayOf γ (HashMap β α) → Int → ST γ (): inherited from ArrayElement.modifyElemAt
newArray ∷ Int → STMutable γ (JArray (HashMap β α))
native new[]: inherited from ArrayElement.newArray
setAt ∷ ArrayOf γ (HashMap β α) → Int → Maybe (HashMap β α) → ST γ ()
native []=: inherited from ArrayElement.setAt
setElemAt ∷ ArrayOf γ (HashMap β α) → Int → HashMap β α → ST γ ()
native []=: inherited from ArrayElement.setElemAt

instance (Eq k, Eq v) ⇒ Eq (HashMap k v)

Member Functions

!= ∷ (Eq β, Eq α) ⇒ HashMap β α → HashMap β α → Bool
infix 7: inherited from Eq.!=
== ∷ (Eq β, Eq α) ⇒ HashMap β α → HashMap β α → Bool
infix 7
hashCode ∷ (Eq β, Eq α) ⇒ HashMap β α → Int

instance Foldable (HashMap k)

Member Functions

fold ∷ Monoid β ⇒ HashMap α β → β: inherited from Foldable.fold
fold1 ∷ Semigroup β ⇒ HashMap α β → β: inherited from Foldable.fold1
foldMap ∷ Monoid γ ⇒ (β → γ) → HashMap α β → γ: inherited from Foldable.foldMap
foldMap1 ∷ Semigroup γ ⇒ (β → γ) → HashMap α β → γ: inherited from Foldable.foldMap1
foldl ∷ (β → γ → β) → β → HashMap α γ → β
foldl1 ∷ (β → β → β) → HashMap α β → β: inherited from Foldable.foldl1
foldr ∷ (β → γ → γ) → γ → HashMap α β → γ
foldr1 ∷ (β → β → β) → HashMap α β → β: inherited from Foldable.foldr1

instance Functor (HashMap k)

Member Functions

fmap ∷ (β → γ) → HashMap α β → HashMap α γ
infixl 4

instance ListEmpty (HashMap k)

Member Functions

empty ∷ HashMap α β

O(1)

The empty HashMap, represented by a bitmapped node with a bitmap that is 0.

null ∷ HashMap α β → Bool

O(1)

true if and only if the argument is the empty HashMap, otherwise false

instance Eq k ⇒ ListMonoid (HashMap k)

Member Functions

++ ∷ Eq α ⇒ HashMap α β → HashMap α β → HashMap α β
infixr 13
concat ∷ Eq α ⇒ [HashMap α β] → HashMap α β: inherited from ListMonoid.concat

instance ListSource (HashMap k)

Member Functions

toList ∷ HashMap α β → [β]

Return the list of values in a HashMap.

Note that this is not symmetric with fromList!

instance Eq k ⇒ Monoid (HashMap k v)

Member Functions

mappend ∷ Eq β ⇒ HashMap β α → HashMap β α → HashMap β α
infixr 13: builds the union of two HashMaps
mconcat ∷ Eq β ⇒ [HashMap β α] → HashMap β α: inherited from Monoid.mconcat
mempty ∷ Eq β ⇒ HashMap β α: The empty HashMap.
mtimes ∷ Eq β ⇒ Int → HashMap β α → HashMap β α: inherited from Monoid.mtimes
sconcat ∷ Eq β ⇒ [HashMap β α] → HashMap β α: inherited from Semigroup.sconcat
stimes ∷ Eq β ⇒ Int → HashMap β α → HashMap β α: inherited from Semigroup.stimes

instance (ToJSON k, ToJSON v) ⇒ Show (HashMap k v)

Member Functions

display ∷ (ToJSON β, ToJSON α) ⇒ HashMap β α → String: inherited from Show.display
show ∷ (ToJSON β, ToJSON α) ⇒ HashMap β α → String
showChars ∷ (ToJSON β, ToJSON α) ⇒ HashMap β α → [Char]: inherited from Show.showChars
showList ∷ (ToJSON β, ToJSON α) ⇒ [HashMap β α] → String → String: inherited from Show.showList
showsPrec ∷ (ToJSON β, ToJSON α) ⇒ Int → HashMap β α → String → String: inherited from Show.showsPrec
showsub ∷ (ToJSON β, ToJSON α) ⇒ HashMap β α → String: inherited from Show.showsub

instance (ToJSON k, ToJSON v) ⇒ ToJSON (HashMap k v)

Member Functions

toJSON ∷ (ToJSON β, ToJSON α) ⇒ HashMap β α → Value

instance Traversable (HashMap k)

Member Functions

mapM ∷ Monad δ ⇒ (β → δ γ) → HashMap α β → δ (HashMap α γ): inherited from Traversable.mapM
sequence ∷ Monad γ ⇒ HashMap α (γ β) → γ (HashMap α β): inherited from Traversable.sequence
sequenceA ∷ Applicative γ ⇒ HashMap α (γ β) → γ (HashMap α β): inherited from Traversable.sequenceA
traverse ∷ Applicative δ ⇒ (β → δ γ) → HashMap α β → δ (HashMap α γ)

Functions and Values by Type

Int → Int → Int → Int: HashMap.indexMap
(k → v → Bool) → HashMap k v → HashMap k v: filterWithKey
(v → Bool) → HashMap k v → HashMap k v: filterValues
(β → β → β) → HashMap α β → β: Foldable_HashMap.foldr1, Foldable_HashMap.foldl1
HashMap k v → [(k, v)]: each
HashMap k v → [k]: keys
HashMap k v → [v]: values
HashMap k v → Int: size
HashMap α β → (Int→Int) → HashMap α β: HashMap.chg$bitmap, HashMap.chg$hash
HashMap α β → Int → HashMap α β: HashMap.upd$hash, HashMap.upd$bitmap
HashMap α β → JArray (HashMap α β): HashMap.subnodes
HashMap α β → [(α, β)]: HashMap.list
HashMap α β → [β]: ListSource_HashMap.toList
HashMap α β → Bool: ListEmpty_HashMap.null, HashMap.has$subnodes, HashMap.has$key, HashMap.has$list, HashMap.has$value, HashMap.has$bitmap, HashMap.has$hash
HashMap α β → Int: HashMap.hash, HashMap.bitmap
HashMap α β → α: HashMap.key
HashMap β α → (Int, Int, [[β]]): HashMap.collisions
HashMap β α → α: HashMap.value
JArray (HashMap k v) → Int → HashMap k v: HashMap.BM
JArray (HashMap β α) → Int → HashMap β α: ArrayElement_HashMap.elemAt
JArray (HashMap β α) → Int → Maybe (HashMap β α): ArrayElement_HashMap.itemAt
JArray (HashMap β α) → [HashMap β α]: ArrayElement_HashMap.listFromArray
JArray (HashMap β α) → [Maybe (HashMap β α)]: ArrayElement_HashMap.maybeListFromArray
JArray (HashMap β α) → Int: ArrayElement_HashMap.arrayLength
[HashMap β α] → JArray (HashMap β α): ArrayElement_HashMap.arrayFromList
[(Int, HashMap β α)] → JArray (HashMap β α): ArrayElement_HashMap.arrayFromIndexList
[Maybe (HashMap β α)] → JArray (HashMap β α): ArrayElement_HashMap.arrayFromMaybeList
Int → [(k, v)] → HashMap k v: HashMap.CO
Int → k → v → HashMap k v: HashMap.KV
(ToJSON β, ToJSON α) ⇒ HashMap β α → String: Show_HashMap.showsub, Show_HashMap.display, Show_HashMap.show
(ToJSON β, ToJSON α) ⇒ HashMap β α → [Char]: Show_HashMap.showChars
(ToJSON β, ToJSON α) ⇒ HashMap β α → Value: ToJSON_HashMap.toJSON
(ToJSON β, ToJSON α) ⇒ [HashMap β α] → String → String: Show_HashMap.showList
(ToJSON β, ToJSON α) ⇒ Int → HashMap β α → String → String: Show_HashMap.showsPrec
Monoid β ⇒ HashMap α β → β: Foldable_HashMap.fold
Semigroup β ⇒ HashMap α β → β: Foldable_HashMap.fold1
Eq k ⇒ (v → v → v) → HashMap k v → HashMap k v → HashMap k v: unionWith
Eq k ⇒ (v → v → v) → [(k, v)] → HashMap k v: fromListWith
Eq k ⇒ (v → v → v) → k → v → HashMap k v → HashMap k v: insertWith
Eq k ⇒ (v → v) → k → HashMap k v → HashMap k v: adjust
Eq k ⇒ HashMap k v → HashMap k v → HashMap k v: union
Eq k ⇒ HashMap k v → k → v → HashMap k v: HashMap.insert
Eq k ⇒ HashMap k v → k → HashMap k v: HashMap.delete
Eq k ⇒ HashMap k v → k → Maybe v: HashMap.lookup
Eq k ⇒ HashMap k v → k → v: !!
Eq k ⇒ HashMap k v → Bool: HashMap.invariants
Eq k ⇒ [HashMap k v] → HashMap k v: unions
Eq k ⇒ [(k, v)] → HashMap k v: fromList
Eq k ⇒ k → HashMap k v → HashMap k v: delete
Eq k ⇒ k → HashMap k v → Maybe v: lookup
Eq k ⇒ k → HashMap k v → Bool: member
Eq k ⇒ k → v → HashMap k v → HashMap k v: insert, replace
Eq k ⇒ k → v → HashMap k v: singleton
Eq k ⇒ v → k → HashMap k v → v: lookupDefault
Eq α ⇒ HashMap α β → HashMap α β → HashMap α β: ListMonoid_HashMap.++
Eq α ⇒ [HashMap α β] → HashMap α β: ListMonoid_HashMap.concat
Eq β ⇒ HashMap β α → HashMap β α → HashMap β α: Monoid_HashMap.mappend
Eq β ⇒ [HashMap β α] → HashMap β α: Monoid_HashMap.sconcat, Monoid_HashMap.mconcat
Eq β ⇒ Int → HashMap β α → HashMap β α: Monoid_HashMap.stimes, Monoid_HashMap.mtimes
(Eq β, Eq α) ⇒ HashMap β α → HashMap β α → Bool: Eq_HashMap.!=, Eq_HashMap.==
(Eq β, Eq α) ⇒ HashMap β α → Int: Eq_HashMap.hashCode
HashMap α β: ListEmpty_HashMap.empty
Class (HashMap β α): ArrayElement_HashMap.javaClass
Eq β ⇒ HashMap β α: Monoid_HashMap.mempty
(HashMap β α → HashMap β α) → ArrayOf γ (HashMap β α) → Int → ST γ (): ArrayElement_HashMap.modifyElemAt, ArrayElement_HashMap.modifyAt
(a → k → v → a) → a → HashMap k v → a: foldWithKey
(a → v → a) → a → HashMap k v → a: foldValues
(k → v → a → a) → a → HashMap k v → a: foldrWithKey
(k → v → u) → HashMap k v → HashMap k u: mapWithKey
(v → a → a) → a → HashMap k v → a: foldrValues
(v → u) → HashMap k v → HashMap k u: mapValues
(β → γ → β) → β → HashMap α γ → β: Foldable_HashMap.foldl
(β → γ → γ) → γ → HashMap α β → γ: Foldable_HashMap.foldr
(β → γ) → HashMap α β → HashMap α γ: Functor_HashMap.fmap
HashMap α γ → (γ→β) → HashMap α β: HashMap.chg$value
HashMap α γ → β → HashMap β γ: HashMap.upd$key
HashMap β α → γ → HashMap β γ: HashMap.upd$value
HashMap γ β → (γ→α) → HashMap α β: HashMap.chg$key
ArrayOf γ (HashMap β α) → Int → HashMap β α → ST γ (): ArrayElement_HashMap.setElemAt
ArrayOf γ (HashMap β α) → Int → Maybe (HashMap β α) → ST γ (): ArrayElement_HashMap.setAt
ArrayOf γ (HashMap β α) → Int → ST γ (HashMap β α): ArrayElement_HashMap.getElemAt
ArrayOf γ (HashMap β α) → Int → ST γ (Maybe (HashMap β α)): ArrayElement_HashMap.getAt
[HashMap β α] → STMutable γ (JArray (HashMap β α)): ArrayElement_HashMap.arrayFromListST
[(Int, HashMap β α)] → STMutable γ (JArray (HashMap β α)): ArrayElement_HashMap.arrayFromIndexListST
[Maybe (HashMap β α)] → STMutable γ (JArray (HashMap β α)): ArrayElement_HashMap.arrayFromMaybeListST
Int → STMutable γ (JArray (HashMap β α)): ArrayElement_HashMap.newArray
Monoid γ ⇒ (β → γ) → HashMap α β → γ: Foldable_HashMap.foldMap
Semigroup γ ⇒ (β → γ) → HashMap α β → γ: Foldable_HashMap.foldMap1
Eq k ⇒ HashMap k v → HashMap k u → HashMap k v: difference, intersection
Applicative γ ⇒ HashMap α (γ β) → γ (HashMap α β): Traversable_HashMap.sequenceA
Monad γ ⇒ HashMap α (γ β) → γ (HashMap α β): Traversable_HashMap.sequence
HashMap α β → (JArray (HashMap α β)→JArray (HashMap γ δ)) → HashMap γ δ: HashMap.chg$subnodes
HashMap α β → ([(α, β)]→[(γ, δ)]) → HashMap γ δ: HashMap.chg$list
HashMap α β → JArray (HashMap γ δ) → HashMap γ δ: HashMap.upd$subnodes
HashMap α β → [(γ, δ)] → HashMap γ δ: HashMap.upd$list
Eq k ⇒ (v → u → w) → HashMap k v → HashMap k u → HashMap k w: intersectionWith
Applicative a ⇒ (k → v → a u) → HashMap k v → a (HashMap k u): traverseWithKey
Applicative δ ⇒ (β → δ γ) → HashMap α β → δ (HashMap α γ): Traversable_HashMap.traverse
Monad δ ⇒ (β → δ γ) → HashMap α β → δ (HashMap α γ): Traversable_HashMap.mapM