Safe Haskell | Safe-Infered |
---|
Data.HashMap.Base
Contents
- data HashMap k v
- data Leaf k v = L !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
- unsafeInsert :: (Eq k, Hashable k) => 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
- 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
- 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 :: (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
- type Bitmap = Word
- bitmapIndexedOrFull :: Bitmap -> Array (HashMap k v) -> HashMap k v
- collision :: Hash -> Leaf k v -> Leaf k v -> HashMap k v
- hash :: Hashable a => a -> Hash
- mask :: Word -> Shift -> Bitmap
- index :: Hash -> Shift -> Int
- bitsPerSubkey :: Int
- fullNodeMask :: Bitmap
- sparseIndex :: Bitmap -> Bitmap -> Int
- two :: Shift -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)
- unionArrayBy :: (a -> a -> a) -> Bitmap -> Bitmap -> Array a -> Array a -> Array a
- update16 :: Array e -> Int -> e -> Array e
- update16' :: Array e -> Int -> e -> ST s (Array e)
- update16With :: Array e -> Int -> (e -> e) -> Array e
- updateOrConcatWith :: Eq k => (v -> v -> v) -> Array (Leaf k v) -> Array (Leaf k v) -> Array (Leaf k v)
Documentation
A map from keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
Construction
Basic interface
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe vSource
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 -> vSource
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 vSource
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 vSource
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
unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k vSource
In-place update version of insert
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k vSource
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 vSource
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 vSource
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 vSource
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 vSource
Construct a set containing all elements from a list of sets.
Transformations
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2Source
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 vSource
O(n+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 vSource
O(n+m) Intersection of two maps. Return elements of the first map for keys existing in the second.
Folds
foldl' :: (a -> v -> a) -> a -> HashMap k v -> aSource
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 -> aSource
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 -> aSource
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 -> aSource
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 vSource
O(n) Filter this map by retaining only elements which values satisfy a predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k vSource
O(n) Filter this map by retaining only elements satisfying a predicate.
Conversions
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 vSource
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 vSource
O(n*log n) Construct a map from a list of elements. Uses the provided function to merge duplicate entries.
bitmapIndexedOrFull :: Bitmap -> Array (HashMap k v) -> HashMap k vSource
Create a BitmapIndexed
or Full
node.
hash :: Hashable a => a -> HashSource
Convenience function. Compute a hash value for the given value.
index :: Hash -> Shift -> IntSource
Mask out the bitsPerSubkey
bits used for indexing at this level
of the tree.
A bitmask with the bitsPerSubkey
least significant bits set.
sparseIndex :: Bitmap -> Bitmap -> IntSource
two :: Shift -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)Source
Create a map from two key-value pairs which hashes don't collide.
unionArrayBy :: (a -> a -> a) -> Bitmap -> Bitmap -> Array a -> Array a -> Array aSource
Strict in the result of f
.
update16 :: Array e -> Int -> e -> Array eSource
O(n) Update the element at the given position in this array.
update16' :: Array e -> Int -> e -> ST s (Array e)Source
O(n) Update the element at the given position in this array.
update16With :: Array e -> Int -> (e -> e) -> Array eSource
O(n) Update the element at the given position in this array, by applying a function to it.