Safe Haskell  None 

Language  Haskell2010 
WARNING
This module is considered internal.
The Package Versioning Policy does not apply.
The contents of this module may change in any way whatsoever and without any warning between minor versions of this package.
Authors importing this module are expected to track development closely.
Synopsis
 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
 (!?) :: (Eq k, Hashable k) => HashMap k v > k > Maybe v
 findWithDefault :: (Eq k, Hashable k) => v > k > HashMap k v > v
 lookupDefault :: (Eq k, Hashable k) => v > k > HashMap k v > v
 (!) :: (Eq k, Hashable k, HasCallStack) => 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
 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)
 isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v > HashMap k v > Bool
 isSubmapOfBy :: (Eq k, Hashable k) => (v1 > v2 > Bool) > HashMap k v1 > HashMap k v2 > Bool
 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
 compose :: (Eq b, Hashable b) => HashMap b c > HashMap a b > HashMap a c
 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)
 mapKeys :: (Eq k2, Hashable k2) => (k1 > k2) > HashMap k1 v > HashMap k2 v
 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
 intersectionWithKey# :: Eq k => (k > v1 > v2 > (# v3 #)) > HashMap k v1 > HashMap k v2 > HashMap k v3
 foldr' :: (v > a > a) > a > HashMap k v > a
 foldl' :: (a > v > a) > a > HashMap k v > a
 foldrWithKey' :: (k > v > a > 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
 foldl :: (a > v > a) > a > HashMap k v > a
 foldrWithKey :: (k > v > a > a) > a > HashMap k v > a
 foldlWithKey :: (a > k > v > a) > a > HashMap k v > a
 foldMapWithKey :: Monoid m => (k > v > m) > HashMap k v > m
 mapMaybe :: (v1 > Maybe v2) > HashMap k v1 > HashMap k v2
 mapMaybeWithKey :: (k > v1 > Maybe v2) > HashMap k v1 > HashMap k v2
 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
 fromListWithKey :: (Eq k, Hashable k) => (k > v > v > v) > [(k, v)] > HashMap k v
 type Hash = Word
 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 :: Hash > Shift > Bitmap
 index :: Hash > Shift > Int
 bitsPerSubkey :: Int
 fullNodeMask :: Bitmap
 sparseIndex :: Bitmap > Bitmap > Int
 two :: Shift > Hash > k > v > Hash > HashMap k v > ST s (HashMap k v)
 unionArrayBy :: (a > a > a) > Bitmap > Bitmap > Array a > Array a > Array a
 update32 :: Array e > Int > e > Array e
 update32M :: Array e > Int > e > ST s (Array e)
 update32With' :: Array e > Int > (e > e) > Array e
 updateOrConcatWithKey :: Eq k => (k > v > v > (# v #)) > Array (Leaf k v) > Array (Leaf k v) > Array (Leaf k v)
 filterMapAux :: forall k v1 v2. (HashMap k v1 > Maybe (HashMap k v2)) > (Leaf k v1 > Maybe (Leaf k v2)) > HashMap k v1 > HashMap k v2
 equalKeys :: Eq k => HashMap k v > HashMap k v' > Bool
 equalKeys1 :: (k > k' > Bool) > HashMap k v > HashMap k' v' > Bool
 lookupRecordCollision :: Eq k => Hash > k > HashMap k v > LookupRes v
 data LookupRes a
 insert' :: Eq k => Hash > k > v > HashMap k v > HashMap k v
 delete' :: Eq k => Hash > k > HashMap k v > HashMap k v
 lookup' :: Eq k => Hash > k > HashMap k v > Maybe v
 insertNewKey :: Hash > k > v > HashMap k v > HashMap k v
 insertKeyExists :: Int > Hash > k > v > HashMap k v > HashMap k v
 deleteKeyExists :: Int > Hash > k > HashMap k v > HashMap k v
 insertModifying :: (Eq k, Hashable k) => v > (v > (# v #)) > k > HashMap k v > HashMap k v
 ptrEq :: a > a > Bool
 adjust# :: (Eq k, Hashable k) => (v > (# v #)) > k > HashMap k v > HashMap k v
Documentation
A map from keys to values. A map cannot contain duplicate keys; each key can map to at most one value.
Empty  
BitmapIndexed !Bitmap !(Array (HashMap k v))  
Leaf !Hash !(Leaf k v)  
Full !(Array (HashMap k v))  
Collision !Hash !(Array (Leaf k v)) 
Instances
Bifoldable HashMap Source #  Since: 0.2.11 
Eq2 HashMap Source #  
Ord2 HashMap Source #  
Defined in Data.HashMap.Internal  
Show2 HashMap Source #  
NFData2 HashMap Source #  Since: 0.2.14.0 
Defined in Data.HashMap.Internal  
Hashable2 HashMap Source #  
Defined in Data.HashMap.Internal  
(Lift k, Lift v) => Lift (HashMap k v :: Type) Source #  Since: 0.2.17.0 
Functor (HashMap k) Source #  
Foldable (HashMap k) Source #  
Defined in Data.HashMap.Internal fold :: Monoid m => HashMap k m > m # foldMap :: Monoid m => (a > m) > HashMap k a > m # foldMap' :: Monoid m => (a > m) > HashMap k a > m # foldr :: (a > b > b) > b > HashMap k a > b # foldr' :: (a > b > b) > b > HashMap k a > b # foldl :: (b > a > b) > b > HashMap k a > b # foldl' :: (b > a > b) > b > HashMap k a > b # foldr1 :: (a > a > a) > HashMap k a > a # foldl1 :: (a > a > a) > HashMap k a > a # toList :: HashMap k a > [a] # length :: HashMap k a > Int # elem :: Eq a => a > HashMap k a > Bool # maximum :: Ord a => HashMap k a > a # minimum :: Ord a => HashMap k a > a #  
Traversable (HashMap k) Source #  
Eq k => Eq1 (HashMap k) Source #  
Ord k => Ord1 (HashMap k) Source #  
Defined in Data.HashMap.Internal  
(Eq k, Hashable k, Read k) => Read1 (HashMap k) Source #  
Defined in Data.HashMap.Internal  
Show k => Show1 (HashMap k) Source #  
NFData k => NFData1 (HashMap k) Source #  Since: 0.2.14.0 
Defined in Data.HashMap.Internal  
Hashable k => Hashable1 (HashMap k) Source #  
Defined in Data.HashMap.Internal  
(Eq k, Hashable k) => IsList (HashMap k v) Source #  
(Eq k, Eq v) => Eq (HashMap k v) Source #  Note that, in the presence of hash collisions, equal
In general, the lack of substitutivity can be observed with any function that depends on the key ordering, such as folds and traversals. 
(Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) Source #  
Defined in Data.HashMap.Internal gfoldl :: (forall d b. Data d => c (d > b) > d > c b) > (forall g. g > c g) > HashMap k v > c (HashMap k v) # gunfold :: (forall b r. Data b => c (b > r) > c r) > (forall r. r > c r) > Constr > c (HashMap k v) # toConstr :: HashMap k v > Constr # dataTypeOf :: HashMap k v > DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) > Maybe (c (HashMap k v)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) > Maybe (c (HashMap k v)) # gmapT :: (forall b. Data b => b > b) > HashMap k v > HashMap k v # gmapQl :: (r > r' > r) > r > (forall d. Data d => d > r') > HashMap k v > r # gmapQr :: forall r r'. (r' > r > r) > r > (forall d. Data d => d > r') > HashMap k v > r # gmapQ :: (forall d. Data d => d > u) > HashMap k v > [u] # gmapQi :: Int > (forall d. Data d => d > u) > HashMap k v > u # gmapM :: Monad m => (forall d. Data d => d > m d) > HashMap k v > m (HashMap k v) # gmapMp :: MonadPlus m => (forall d. Data d => d > m d) > HashMap k v > m (HashMap k v) # gmapMo :: MonadPlus m => (forall d. Data d => d > m d) > HashMap k v > m (HashMap k v) #  
(Ord k, Ord v) => Ord (HashMap k v) Source #  The ordering is total and consistent with the 
Defined in Data.HashMap.Internal  
(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 #  If a key occurs in both maps, the mapping from the first will be the mapping in the result. Examples

(Eq k, Hashable k) => Monoid (HashMap k v) Source #  If a key occurs in both maps, the mapping from the first will be the mapping in the result. Examples

(NFData k, NFData v) => NFData (HashMap k v) Source #  
Defined in Data.HashMap.Internal  
(Hashable k, Hashable v) => Hashable (HashMap k v) Source #  
Defined in Data.HashMap.Internal  
type Item (HashMap k v) Source #  
Defined in Data.HashMap.Internal 
L !k v 
Instances
NFData2 Leaf Source #  Since: 0.2.14.0 
Defined in Data.HashMap.Internal  
(Lift k, Lift v) => Lift (Leaf k v :: Type) Source #  Since: 0.2.17.0 
NFData k => NFData1 (Leaf k) Source #  Since: 0.2.14.0 
Defined in Data.HashMap.Internal  
(Eq k, Eq v) => Eq (Leaf k v) Source #  
(NFData k, NFData v) => NFData (Leaf k v) Source #  
Defined in Data.HashMap.Internal 
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.
Since: 0.2.11
\(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.
DEPRECATED: lookupDefault is deprecated as of version 0.2.11, replaced
by findWithDefault
.
(!) :: (Eq k, Hashable k, HasCallStack) => 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
unsafeInsert :: (Eq k, Hashable k) => k > v > HashMap k v > HashMap k v Source #
Inplace update version of insert
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 map)x
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.10
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v > HashMap k v > Bool Source #
\(O(n \log m)\) Inclusion of maps. A map is included in another map if the keys are subsets and the corresponding values are equal:
isSubmapOf m1 m2 = keys m1 `isSubsetOf` keys m2 && and [ v1 == v2  (k1,v1) < toList m1; let v2 = m2 ! k1 ]
Examples
>>>
fromList [(1,'a')] `isSubmapOf` fromList [(1,'a'),(2,'b')]
True
>>>
fromList [(1,'a'),(2,'b')] `isSubmapOf` fromList [(1,'a')]
False
Since: 0.2.12
isSubmapOfBy :: (Eq k, Hashable k) => (v1 > v2 > Bool) > HashMap k v1 > HashMap k v2 > Bool Source #
\(O(n \log m)\) Inclusion of maps with value comparison. A map is included in another map if the keys are subsets and if the comparison function is true for the corresponding values:
isSubmapOfBy cmpV m1 m2 = keys m1 `isSubsetOf` keys m2 && and [ v1 `cmpV` v2  (k1,v1) < toList m1; let v2 = m2 ! k1 ]
Examples
>>>
isSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
True
>>>
isSubmapOfBy (<=) (fromList [(1,'b')]) (fromList [(1,'a'),(2,'c')])
False
Since: 0.2.12
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.
Examples
>>>
union (fromList [(1,'a'),(2,'b')]) (fromList [(2,'c'),(3,'d')])
fromList [(1,'a'),(2,'b'),(3,'d')]
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.
Compose
compose :: (Eq b, Hashable b) => HashMap b c > HashMap a b > HashMap a c Source #
Relate the keys of one map to the values of the other, by using the values of the former as keys for lookups in the latter.
Complexity: \( O (n * \log(m)) \), where \(m\) is the size of the first argument
>>>
compose (fromList [('a', "A"), ('b', "B")]) (fromList [(1,'a'),(2,'b'),(3,'z')])
fromList [(1,"A"),(2,"B")]
(compose
bc ab!?
) = (bc!?
) <=< (ab!?
)
Since: 0.2.13.0
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.
mapKeys :: (Eq k2, Hashable k2) => (k1 > k2) > HashMap k1 v > HashMap k2 v Source #
\(O(n)\).
is the map obtained by applying mapKeys
f sf
to each key of s
.
The size of the result may be smaller if f
maps two or more distinct
keys to the same new key. In this case there is no guarantee which of the
associated values is chosen for the conflicting key.
>>>
mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])
fromList [(4,"b"),(6,"a")]>>>
mapKeys (\ _ > 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(1,"c")]>>>
mapKeys (\ _ > 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
fromList [(3,"c")]
Since: 0.2.14.0
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 \log 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 \log 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 => (k > v1 > v2 > (# v3 #)) > HashMap k v1 > HashMap k v2 > HashMap k v3 Source #
Folds
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). Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.
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.
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). 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).
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).
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).
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).
foldMapWithKey :: Monoid m => (k > v > m) > HashMap k v > m Source #
\(O(n)\) Reduce the map by applying a function to each element and combining the results with a monoid operation.
Filter
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.
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. 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 f
to merge duplicate entries with
(f newVal oldVal)
.
Examples
Given a list xs
, create a map with the number of occurrences of each
element in xs
:
let xs = ['a', 'b', 'a'] in fromListWith (+) [ (x, 1)  x < xs ] = fromList [('a', 2), ('b', 1)]
Given a list of keyvalue pairs xs :: [(k, v)]
, group all values by their
keys and return a HashMap k [v]
.
let xs = [('a', 1), ('b', 2), ('a', 3)] in fromListWith (++) [ (k, [v])  (k, v) < xs ] = fromList [('a', [3, 1]), ('b', [2])]
Note that the lists in the resulting map contain elements in reverse order from their occurences in the original list.
More generally, duplicate entries are accumulated as follows;
this matters when f
is not commutative or not associative.
fromListWith f [(k, a), (k, b), (k, c), (k, d)] = fromList [(k, f d (f c (f b a)))]
fromListWithKey :: (Eq k, Hashable k) => (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.
Examples
Given a list of keyvalue pairs where the keys are of different flavours, e.g:
data Key = Div  Sub
and the values need to be combined differently when there are duplicates, depending on the key:
combine Div = div combine Sub = ()
then fromListWithKey
can be used as follows:
fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)] = fromList [(Div, 3), (Sub, 1)]
More generally, duplicate entries are accumulated as follows;
fromListWith f [(k, a), (k, b), (k, c), (k, d)] = fromList [(k, f k d (f k c (f k b a)))]
Since: 0.2.11
A bitmap as contained by a BitmapIndexed
node, or a fullNodeMask
corresponding to a Full
node.
Only the lower maxChildren
bits are used. The remaining bits must be zeros.
bitmapIndexedOrFull :: Bitmap > Array (HashMap k v) > HashMap k v Source #
Create a BitmapIndexed
or Full
node.
hash :: Hashable a => a > Hash Source #
A set of values. A set cannot contain duplicate values.
Convenience function. Compute a hash value for the given value.
mask :: Hash > Shift > Bitmap Source #
Given a Hash
and a Shift
that indicates the level in the tree, compute
the bitmap that contains only the index
of the hash at this level.
The result can be used for constructing oneelement BitmapIndexed
nodes or
to check whether a BitmapIndexed
node may possibly contain the given Hash
.
>>>
mask 0b0010_0010 0
0b0100
index :: Hash > Shift > Int Source #
Given a Hash
and a Shift
that indicates the level in the tree, compute
the index into a Full
node or into the bitmap of a BitmapIndexed
node.
>>>
index 0b0010_0010 0
0b0000_0010
bitsPerSubkey :: Int Source #
Number of bits that are inspected at each level of the hash tree.
This constant is named t in the original Ideal Hash Trees paper.
fullNodeMask :: Bitmap Source #
A bitmap with the maxChildren
least significant bits set, i.e.
0xFF_FF_FF_FF
.
:: Bitmap  Bitmap of a 
> Bitmap  
> Int  Index into the array of the 
This array index is computed by counting the number of bits below the
index
represented by the mask.
>>>
sparseIndex 0b0110_0110 0b0010_0000
2
two :: Shift > Hash > k > v > Hash > HashMap k v > ST s (HashMap k v) Source #
Create a map from two keyvalue pairs which hashes don't collide. To enhance sharing, the second keyvalue pair is represented by the hash of its key and a singleton HashMap pairing its key with its value.
Note: to avoid silly thunks, this function must be strict in the key. See issue #232. We don't need to force the HashMap argument because it's already in WHNF (having just been matched) and we just put it directly in an array.
unionArrayBy :: (a > a > a) > Bitmap > Bitmap > Array a > Array a > Array a Source #
Strict in the result of f
.
update32 :: Array e > Int > e > Array e Source #
\(O(n)\) Update the element at the given position in this array.
update32M :: Array e > Int > e > ST s (Array e) Source #
\(O(n)\) Update the element at the given position in this array.
update32With' :: Array e > Int > (e > e) > Array e Source #
\(O(n)\) Update the element at the given position in this array, by applying a function to it.
updateOrConcatWithKey :: Eq k => (k > v > v > (# v #)) > Array (Leaf k v) > Array (Leaf k v) > Array (Leaf k v) Source #
filterMapAux :: forall k v1 v2. (HashMap k v1 > Maybe (HashMap k v2)) > (Leaf k v1 > Maybe (Leaf k v2)) > HashMap k v1 > HashMap k v2 Source #
Common implementation for filterWithKey
and mapMaybeWithKey
,
allowing the former to former to reuse terms.
lookup' :: Eq k => Hash > k > HashMap k v > Maybe v Source #
lookup' is a version of lookup that takes the hash separately. It is used to implement alterF.
deleteKeyExists :: Int > Hash > k > HashMap k v > HashMap k v Source #
Delete optimized for the case when we know the key is in the map.
It is only valid to call this when the key exists in the map and you know the
hash collision position if there was one. This information can be obtained
from lookupRecordCollision
. If there is no collision pass (1) as collPos.
We can skip:  the key equality check on the leaf, if we reach a leaf it must be the key
insertModifying :: (Eq k, Hashable k) => v > (v > (# v #)) > k > HashMap k v > HashMap k v Source #
insertModifying
is a lot like insertWith; we use it to implement alterF.
It takes a value to insert when the key is absent and a function
to apply to calculate a new value when the key is present. Thanks
to the unboxed unary tuple, we avoid introducing any unnecessary
thunks in the tree.