-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Efficient hashing-based container types
--   
--   Efficient hashing-based container types. The containers have been
--   optimized for performance critical use, both in terms of large data
--   quantities and high speed.
--   
--   The declared cost of each operation is either worst-case or amortized,
--   but remains valid even if structures are shared.
--   
--   Security
--   
--   This package currently provides no defenses against hash collision
--   attacks such as HashDoS. Users who need to store input from untrusted
--   sources are advised to use Data.Map or Data.Set from
--   the containers package instead.
@package unordered-containers
@version 0.2.20.1

-- | 
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.
--   
--   
Description
--   
--   Zero based arrays.
--   
--   Note that no bounds checking are performed.
module Data.HashMap.Internal.Array
data Array a
Array :: !SmallArray# a -> Array a
[unArray] :: Array a -> !SmallArray# a
data MArray s a
MArray :: !SmallMutableArray# s a -> MArray s a
[unMArray] :: MArray s a -> !SmallMutableArray# s a

-- | Create a new mutable array of specified size, in the specified state
--   thread, with each element containing the specified initial value.
new :: Int -> a -> ST s (MArray s a)
new_ :: Int -> ST s (MArray s a)
singleton :: a -> Array a
singletonM :: a -> ST s (Array a)
snoc :: Array a -> a -> Array a
pair :: a -> a -> Array a
length :: Array a -> Int
lengthM :: MArray s a -> Int
read :: MArray s a -> Int -> ST s a
write :: MArray s a -> Int -> a -> ST s ()
index :: Array a -> Int -> a
indexM :: Array a -> Int -> ST s a
index# :: Array a -> Int -> (# a #)

-- | <math> Update the element at the given position in this array.
update :: Array e -> Int -> e -> Array e

-- | <math> Update the element at the given position in this array,
--   by applying a function to it. Evaluates the element to WHNF before
--   inserting it into the array.
updateWith' :: Array e -> Int -> (e -> e) -> Array e

-- | <math> Update the element at the given position in this array,
--   without copying.
unsafeUpdateM :: Array e -> Int -> e -> ST s ()

-- | <math> Insert an element at the given position in this array,
--   increasing its size by one.
insert :: Array e -> Int -> e -> Array e

-- | <math> Insert an element at the given position in this array,
--   increasing its size by one.
insertM :: Array e -> Int -> e -> ST s (Array e)

-- | <math> Delete an element at the given position in this array,
--   decreasing its size by one.
delete :: Array e -> Int -> Array e
sameArray1 :: (a -> b -> Bool) -> Array a -> Array b -> Bool
unsafeFreeze :: MArray s a -> ST s (Array a)
unsafeThaw :: Array a -> ST s (MArray s a)
unsafeSameArray :: Array a -> Array b -> Bool
run :: (forall s. () => ST s (MArray s e)) -> Array e

-- | Unsafely copy the elements of an array. Array bounds are not checked.
copy :: Array e -> Int -> MArray s e -> Int -> Int -> ST s ()

-- | Unsafely copy the elements of an array. Array bounds are not checked.
copyM :: MArray s e -> Int -> MArray s e -> Int -> Int -> ST s ()
cloneM :: MArray s a -> Int -> Int -> ST s (MArray s a)
foldl :: (b -> a -> b) -> b -> Array a -> b
foldl' :: (b -> a -> b) -> b -> Array a -> b
foldr :: (a -> b -> b) -> b -> Array a -> b
foldr' :: (a -> b -> b) -> b -> Array a -> b
foldMap :: Monoid m => (a -> m) -> Array a -> m

-- | Verifies that a predicate holds for all elements of an array.
all :: (a -> Bool) -> Array a -> Bool
thaw :: Array e -> Int -> Int -> ST s (MArray s e)
map :: (a -> b) -> Array a -> Array b

-- | Strict version of map.
map' :: (a -> b) -> Array a -> Array b
traverse :: Applicative f => (a -> f b) -> Array a -> f (Array b)
traverse' :: Applicative f => (a -> f b) -> Array a -> f (Array b)
toList :: Array a -> [a]
fromList :: Int -> [a] -> Array a
fromList' :: Int -> [a] -> Array a

-- | When shrinkSmallMutableArray# is available, the returned array
--   is the same as the array given, as it is shrunk in place. Otherwise a
--   copy is made.
shrink :: MArray s a -> Int -> ST s (MArray s a)
instance Language.Haskell.TH.Syntax.Lift a => Language.Haskell.TH.Syntax.Lift (Data.HashMap.Internal.Array.Array a)
instance Control.DeepSeq.NFData1 Data.HashMap.Internal.Array.Array
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.HashMap.Internal.Array.Array a)
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.HashMap.Internal.Array.Array a)

-- | 
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.
--   
--   
Description
--   
--   Extra list functions
--   
--   In separate module to aid testing.
module Data.HashMap.Internal.List
isPermutationBy :: (a -> b -> Bool) -> [a] -> [b] -> Bool
deleteBy :: (a -> b -> Bool) -> a -> [b] -> Maybe [b]
unorderedCompare :: (a -> b -> Ordering) -> [a] -> [b] -> Ordering

-- | 
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.
module Data.HashMap.Internal

-- | A map from keys to values. A map cannot contain duplicate keys; each
--   key can map to at most one value.
data HashMap k v

-- | Invariants:
--   
--   
--   
- Empty is not a valid sub-node. It can only appear at the
--   root. (INV1)
--   
Empty :: HashMap k v

-- | Invariants:
--   
--   
--   
- Only the lower maxChildren bits of the Bitmap may
--   be set. The remaining upper bits must be 0. (INV2)
--   
- The array of a BitmapIndexed node stores at least 1 and at
--   most maxChildren - 1 sub-nodes. (INV3)
--   
- The number of sub-nodes is equal to the number of 1-bits in its
--   Bitmap. (INV4)
--   
- If a BitmapIndexed node has only one sub-node, this
--   sub-node must be a BitmapIndexed or a Full node.
--   (INV5)
--   
BitmapIndexed :: !Bitmap -> !Array (HashMap k v) -> HashMap k v

-- | Invariants:
--   
--   
--   
- The location of a Leaf or Collision node in the tree
--   must be compatible with its Hash. (INV6) (TODO: Document this
--   properly (#425))
--   
- The Hash of a Leaf node must be the hash of
--   its key. (INV7)
--   
Leaf :: !Hash -> !Leaf k v -> HashMap k v

-- | Invariants:
--   
--   
--   
- The array of a Full node stores exactly maxChildren
--   sub-nodes. (INV8)
--   
Full :: !Array (HashMap k v) -> HashMap k v

-- | Invariants:
--   
--   
--   
- The location of a Leaf or Collision node in the tree
--   must be compatible with its Hash. (INV6) (TODO: Document this
--   properly (#425))
--   
- The array of a Collision node must contain at least two
--   sub-nodes. (INV9)
--   
- The hash of each key in a Collision node must be the
--   one stored in the node. (INV7)
--   
- No two keys stored in a Collision can be equal according to
--   their Eq instance. (INV10)
--   
Collision :: !Hash -> !Array (Leaf k v) -> HashMap k v
data Leaf k v
L :: !k -> v -> Leaf k v

-- | <math> Construct an empty map.
empty :: HashMap k v

-- | <math> Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | <math> Return True if this map is empty, False
--   otherwise.
null :: HashMap k v -> Bool

-- | <math> Return the number of key-value mappings in this map.
size :: HashMap k v -> Int

-- | <math> Return True if the specified key is present in the
--   map, False otherwise.
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
--   
--   This is a flipped version of lookup.
(!?) :: (Eq k, Hashable k) => HashMap k v -> k -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   the default value if this map contains no mapping for the key.
findWithDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> 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.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> Return the value to which the specified key is mapped.
--   Calls error if this map contains no mapping for the key.
(!) :: (Eq k, Hashable k, HasCallStack) => HashMap k v -> k -> v
infixl 9 !

-- | <math> 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.
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

-- | <math> 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
--   
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

-- | In-place update version of insert
unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

-- | <math> Remove the mapping for the specified key from this map if
--   present.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v

-- | <math> Adjust the value tied to a given key in this map only if
--   it is present. Otherwise, leave the map alone.
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (update f k map) updates
--   the value x at k (if it is in the map). If (f
--   x) is Nothing, the element is deleted. If it is
--   (Just y), the key k is bound to the new value
--   y.
update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a

-- | <math> The expression (alter f k map) alters the
--   value x at k, or absence thereof.
--   
--   alter can be used to insert, delete, or update a value in a
--   map. In short:
--   
--   
--   lookup k (alter f k m) = f (lookup k m)
--   
alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (alterF f k map) alters
--   the value 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.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | <math> 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
--   
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | <math> 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
--   
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | <math> 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')]
--   
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | <math> The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWith :: Eq k => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | <math> 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 => (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | Construct a set containing all elements from a list of sets.
unions :: Eq k => [HashMap k v] -> HashMap k v

-- | Given maps bc and ab, relate the keys of ab
--   to the values of bc, by using the values of ab as
--   keys for lookups in bc.
--   
--   Complexity: <math>, where <math> 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 !?)
--   
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

-- | <math> Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Perform an Applicative action for each key-value
--   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.
traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)

-- | <math>. mapKeys f s is the map obtained by
--   applying f 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")]
--   
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | <math> Difference of two maps. Return elements of the first map
--   not existing in the second.
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Difference with a combining function. When two equal keys
--   are encountered, the combining function is applied to the values of
--   these keys. If it returns Nothing, the element is discarded
--   (proper set difference). If it returns (Just y), the
--   element is updated with a new value y.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. Return elements of the first
--   map for keys existing in the second.
intersection :: Eq k => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. If a key occurs in both maps
--   the provided function is used to combine the values from the two maps.
intersectionWith :: Eq k => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

-- | <math> 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
intersectionWithKey# :: Eq k => (k -> v1 -> v2 -> (# v3 #)) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldr' :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   using the result in the next application. This function is strict in
--   the starting value.
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   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

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldl :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> 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

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a

-- | <math> Reduce the map by applying a function to each element and
--   combining the results with a monoid operation.
foldMapWithKey :: Monoid m => (k -> v -> m) -> HashMap k v -> m

-- | <math> Transform this map by applying a function to every value
--   and retaining only some of them.
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2

-- | <math> 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

-- | <math> Filter this map by retaining only elements which values
--   satisfy a predicate.
filter :: (v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Filter this map by retaining only elements satisfying a
--   predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Return a list of this map's keys. The list is produced
--   lazily.
keys :: HashMap k v -> [k]

-- | <math> Return a list of this map's values. The list is produced
--   lazily.
elems :: HashMap k v -> [v]

-- | <math> Return a list of this map's elements. The list is
--   produced lazily. The order of its elements is unspecified, and it may
--   change from version to version of either this package or of
--   hashable.
toList :: HashMap k v -> [(k, v)]

-- | <math> Construct a map with the supplied mappings. If the list
--   contains duplicate mappings, the later mappings take precedence.
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v

-- | <math> 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 key-value 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 occurrences 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)))]
--   
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | <math> Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   
Examples
--   
--   Given a list of key-value 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)))]
--   
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v

-- | This type is used to store the hash of a key, as produced with
--   hash.
type Hash = Word

-- | A bitmap as contained by a BitmapIndexed node, or a
--   fullBitmap corresponding to a Full node.
--   
--   Only the lower maxChildren bits are used. The remaining bits
--   must be zeros.
type Bitmap = Word

-- | Shift values correspond to the level of the tree that we're
--   currently operating at. At the root level the Shift is
--   0. For the subsequent levels the Shift values are
--   bitsPerSubkey, 2*bitsPerSubkey etc.
--   
--   Valid values are non-negative and less than bitSize (0 ::
--   Word).
type Shift = Int

-- | Create a BitmapIndexed or Full node.
bitmapIndexedOrFull :: Bitmap -> Array (HashMap k v) -> HashMap k v

-- | Create a Collision value with two Leaf values.
collision :: Hash -> Leaf k v -> Leaf k v -> HashMap k v

-- | Convenience function. Compute a hash value for the given value.
hash :: Hashable a => a -> Hash

-- | 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 one-element
--   BitmapIndexed nodes or to check whether a BitmapIndexed
--   node may possibly contain the given Hash.
--   
--   
--   >>> mask 0b0010_0010 0
--   0b0100
--   
mask :: Hash -> Shift -> Bitmap

-- | 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
--   
index :: Hash -> Shift -> Int

-- | 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.
--   
--   Note that this constant is platform-dependent. On 32-bit platforms we
--   use '4', because bitmaps using '2^5' bits turned out to be prone to
--   integer overflow bugs. See #491 for instance.
bitsPerSubkey :: Int

-- | The size of a Full node, i.e. 2 ^
--   bitsPerSubkey.
maxChildren :: Int

-- | Helper function to detect Leafs and Collisions.
isLeafOrCollision :: HashMap k v -> Bool

-- | A bitmap with the maxChildren least significant bits set, i.e.
--   0xFF_FF_FF_FF.
fullBitmap :: Bitmap

-- | Bit mask with the lowest bitsPerSubkey bits set, i.e.
--   0b11111.
subkeyMask :: Word

-- | Increment a Shift for use at the next deeper level.
nextShift :: Shift -> Shift

-- | This array index is computed by counting the number of 1-bits below
--   the index represented by the mask.
--   
--   
--   >>> sparseIndex 0b0110_0110 0b0010_0000
--   2
--   
sparseIndex :: Bitmap -> Bitmap -> Int

-- | Create a map from two key-value pairs which hashes don't collide. To
--   enhance sharing, the second key-value 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.
two :: Shift -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)

-- | Strict in the result of f.
unionArrayBy :: (a -> a -> a) -> Bitmap -> Bitmap -> Array a -> Array a -> Array a

-- | <math> Update the element at the given position in this array.
updateFullArray :: Array e -> Int -> e -> Array e

-- | <math> Update the element at the given position in this array.
updateFullArrayM :: Array e -> Int -> e -> ST s (Array e)

-- | <math> Update the element at the given position in this array,
--   by applying a function to it.
updateFullArrayWith' :: 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)

-- | Common implementation for filterWithKey and
--   mapMaybeWithKey, allowing the former to former to reuse terms.
filterMapAux :: (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
Absent :: LookupRes a
Present :: a -> !Int -> LookupRes a
lookupResToMaybe :: LookupRes a -> Maybe 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' is a version of lookup that takes the hash separately. It is
--   used to implement alterF.
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

-- | 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.
deleteKeyExists :: Int -> Hash -> k -> HashMap k v -> HashMap k v

-- | 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.
insertModifying :: (Eq k, Hashable k) => v -> (v -> (# v #)) -> k -> HashMap k v -> HashMap k v

-- | Check if two the two arguments are the same value. N.B. This function
--   might give false negatives (due to GC moving objects.)
ptrEq :: a -> a -> Bool

-- | Much like adjust, but not inherently leaky.
adjust# :: (Eq k, Hashable k) => (v -> (# v #)) -> k -> HashMap k v -> HashMap k v
instance Data.Bifoldable.Bifoldable Data.HashMap.Internal.HashMap
instance (GHC.Internal.Data.Data.Data k, GHC.Internal.Data.Data.Data v, GHC.Classes.Eq k, Data.Hashable.Class.Hashable k) => GHC.Internal.Data.Data.Data (Data.HashMap.Internal.HashMap k v)
instance GHC.Classes.Eq k => Data.Functor.Classes.Eq1 (Data.HashMap.Internal.HashMap k)
instance Data.Functor.Classes.Eq2 Data.HashMap.Internal.HashMap
instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.HashMap.Internal.HashMap k v)
instance (GHC.Classes.Eq k, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.HashMap.Internal.Leaf k v)
instance GHC.Internal.Data.Foldable.Foldable (Data.HashMap.Internal.HashMap k)
instance GHC.Internal.Base.Functor (Data.HashMap.Internal.HashMap k)
instance Data.Hashable.Class.Hashable k => Data.Hashable.Class.Hashable1 (Data.HashMap.Internal.HashMap k)
instance Data.Hashable.Class.Hashable2 Data.HashMap.Internal.HashMap
instance (Data.Hashable.Class.Hashable k, Data.Hashable.Class.Hashable v) => Data.Hashable.Class.Hashable (Data.HashMap.Internal.HashMap k v)
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k) => GHC.Internal.IsList.IsList (Data.HashMap.Internal.HashMap k v)
instance (Language.Haskell.TH.Syntax.Lift k, Language.Haskell.TH.Syntax.Lift v) => Language.Haskell.TH.Syntax.Lift (Data.HashMap.Internal.HashMap k v)
instance (Language.Haskell.TH.Syntax.Lift k, Language.Haskell.TH.Syntax.Lift v) => Language.Haskell.TH.Syntax.Lift (Data.HashMap.Internal.Leaf k v)
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k) => GHC.Internal.Base.Monoid (Data.HashMap.Internal.HashMap k v)
instance Control.DeepSeq.NFData k => Control.DeepSeq.NFData1 (Data.HashMap.Internal.HashMap k)
instance Control.DeepSeq.NFData k => Control.DeepSeq.NFData1 (Data.HashMap.Internal.Leaf k)
instance Control.DeepSeq.NFData2 Data.HashMap.Internal.HashMap
instance Control.DeepSeq.NFData2 Data.HashMap.Internal.Leaf
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.HashMap.Internal.HashMap k v)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.HashMap.Internal.Leaf k v)
instance GHC.Classes.Ord k => Data.Functor.Classes.Ord1 (Data.HashMap.Internal.HashMap k)
instance Data.Functor.Classes.Ord2 Data.HashMap.Internal.HashMap
instance (GHC.Classes.Ord k, GHC.Classes.Ord v) => GHC.Classes.Ord (Data.HashMap.Internal.HashMap k v)
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k, GHC.Internal.Read.Read k) => Data.Functor.Classes.Read1 (Data.HashMap.Internal.HashMap k)
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k, GHC.Internal.Read.Read k, GHC.Internal.Read.Read e) => GHC.Internal.Read.Read (Data.HashMap.Internal.HashMap k e)
instance (GHC.Classes.Eq k, Data.Hashable.Class.Hashable k) => GHC.Internal.Base.Semigroup (Data.HashMap.Internal.HashMap k v)
instance GHC.Internal.Show.Show k => Data.Functor.Classes.Show1 (Data.HashMap.Internal.HashMap k)
instance Data.Functor.Classes.Show2 Data.HashMap.Internal.HashMap
instance (GHC.Internal.Show.Show k, GHC.Internal.Show.Show v) => GHC.Internal.Show.Show (Data.HashMap.Internal.HashMap k v)
instance GHC.Internal.Data.Traversable.Traversable (Data.HashMap.Internal.HashMap k)

-- | 
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.
--   
--   
Description
--   
--   Debugging utilities for HashMaps.
module Data.HashMap.Internal.Debug
valid :: Hashable k => HashMap k v -> Validity k
data Validity k
Invalid :: Error k -> SubHashPath -> Validity k
Valid :: Validity k

-- | An error corresponding to a broken invariant.
--   
--   See HashMap for the documentation of the invariants.
data Error k
INV1_internal_Empty :: Error k
INV2_Bitmap_unexpected_1_bits :: !Bitmap -> Error k
INV3_bad_BitmapIndexed_size :: !Int -> Error k
INV4_bitmap_array_size_mismatch :: !Bitmap -> !Int -> Error k
INV5_BitmapIndexed_invalid_single_subtree :: Error k
INV6_misplaced_hash :: !Hash -> Error k
INV7_key_hash_mismatch :: k -> !Hash -> Error k
INV8_bad_Full_size :: !Int -> Error k
INV9_Collision_size :: !Int -> Error k
INV10_Collision_duplicate_key :: k -> !Hash -> Error k

-- | A part of a Hash with bitsPerSubkey bits.
type SubHash = Word
data SubHashPath
instance GHC.Classes.Eq k => GHC.Classes.Eq (Data.HashMap.Internal.Debug.Error k)
instance GHC.Classes.Eq Data.HashMap.Internal.Debug.SubHashPath
instance GHC.Classes.Eq k => GHC.Classes.Eq (Data.HashMap.Internal.Debug.Validity k)
instance GHC.Internal.Base.Monoid (Data.HashMap.Internal.Debug.Validity k)
instance GHC.Internal.Base.Semigroup (Data.HashMap.Internal.Debug.Validity k)
instance GHC.Internal.Show.Show k => GHC.Internal.Show.Show (Data.HashMap.Internal.Debug.Error k)
instance GHC.Internal.Show.Show Data.HashMap.Internal.Debug.SubHashPath
instance GHC.Internal.Show.Show k => GHC.Internal.Show.Show (Data.HashMap.Internal.Debug.Validity k)

-- | 
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.
--   
--   
Description
--   
--   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 <math>. The
--   implementation uses a large base (i.e. 16 or 32) so in practice these
--   operations are constant time.
module Data.HashMap.Internal.Strict

-- | A map from keys to values. A map cannot contain duplicate keys; each
--   key can map to at most one value.
data HashMap k v

-- | <math> Construct an empty map.
empty :: HashMap k v

-- | <math> Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | <math> Return True if this map is empty, False
--   otherwise.
null :: HashMap k v -> Bool

-- | <math> Return the number of key-value mappings in this map.
size :: HashMap k v -> Int

-- | <math> Return True if the specified key is present in the
--   map, False otherwise.
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
--   
--   This is a flipped version of lookup.
(!?) :: (Eq k, Hashable k) => HashMap k v -> k -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   the default value if this map contains no mapping for the key.
findWithDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> 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.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> Return the value to which the specified key is mapped.
--   Calls error if this map contains no mapping for the key.
(!) :: (Eq k, Hashable k, HasCallStack) => HashMap k v -> k -> v
infixl 9 !

-- | <math> 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.
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

-- | <math> 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
--   
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

-- | <math> Remove the mapping for the specified key from this map if
--   present.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v

-- | <math> Adjust the value tied to a given key in this map only if
--   it is present. Otherwise, leave the map alone.
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (update f k map) updates
--   the value x at k (if it is in the map). If (f
--   x) is Nothing, the element is deleted. If it is
--   (Just y), the key k is bound to the new value
--   y.
update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a

-- | <math> The expression (alter f k map) alters the
--   value x at k, or absence thereof.
--   
--   alter can be used to insert, delete, or update a value in a
--   map. In short:
--   
--   
--   lookup k (alter f k m) = f (lookup k m)
--   
alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (alterF f k map) alters
--   the value 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.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | <math> 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
--   
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | <math> 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
--   
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | <math> 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')]
--   
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | <math> The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWith :: Eq k => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | <math> 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 => (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | Construct a set containing all elements from a list of sets.
unions :: Eq k => [HashMap k v] -> HashMap k v

-- | Given maps bc and ab, relate the keys of ab
--   to the values of bc, by using the values of ab as
--   keys for lookups in bc.
--   
--   Complexity: <math>, where <math> 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 !?)
--   
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

-- | <math> Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Perform an Applicative action for each key-value
--   pair in a HashMap and produce a HashMap of all the
--   results. Each HashMap will be strict in all its values.
--   
--   
--   traverseWithKey f = fmap (map id) . Data.HashMap.Lazy.traverseWithKey f
--   
--   
--   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.
traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)

-- | <math>. mapKeys f s is the map obtained by
--   applying f 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")]
--   
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | <math> Difference of two maps. Return elements of the first map
--   not existing in the second.
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Difference with a combining function. When two equal keys
--   are encountered, the combining function is applied to the values of
--   these keys. If it returns Nothing, the element is discarded
--   (proper set difference). If it returns (Just y), the
--   element is updated with a new value y.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. Return elements of the first
--   map for keys existing in the second.
intersection :: Eq k => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. If a key occurs in both maps
--   the provided function is used to combine the values from the two maps.
intersectionWith :: Eq k => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

-- | <math> 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

-- | <math> Reduce the map by applying a function to each element and
--   combining the results with a monoid operation.
foldMapWithKey :: Monoid m => (k -> v -> m) -> HashMap k v -> m

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldr' :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   using the result in the next application. This function is strict in
--   the starting value.
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   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

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldl :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> 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

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a

-- | <math> Filter this map by retaining only elements which values
--   satisfy a predicate.
filter :: (v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Filter this map by retaining only elements satisfying a
--   predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Transform this map by applying a function to every value
--   and retaining only some of them.
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2

-- | <math> 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

-- | <math> Return a list of this map's keys. The list is produced
--   lazily.
keys :: HashMap k v -> [k]

-- | <math> Return a list of this map's values. The list is produced
--   lazily.
elems :: HashMap k v -> [v]

-- | <math> Return a list of this map's elements. The list is
--   produced lazily. The order of its elements is unspecified, and it may
--   change from version to version of either this package or of
--   hashable.
toList :: HashMap k v -> [(k, v)]

-- | <math> Construct a map with the supplied mappings. If the list
--   contains duplicate mappings, the later mappings take precedence.
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v

-- | <math> 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 key-value 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 occurrences 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)))]
--   
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | <math> Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   
Examples
--   
--   Given a list of key-value 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)))]
--   
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v

-- | 
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.
--   
--   
Description
--   
--   A set of hashable values. A set cannot contain duplicate items.
--   A HashSet makes no guarantees as to the order of its elements.
--   
--   The implementation is based on hash array mapped tries. A
--   HashSet is often faster than other tree-based set types,
--   especially when value comparison is expensive, as in the case of
--   strings.
--   
--   Many operations have a average-case complexity of <math>. The
--   implementation uses a large base (i.e. 16 or 32) so in practice these
--   operations are constant time.
module Data.HashSet.Internal

-- | A set of values. A set cannot contain duplicate values.
newtype HashSet a
HashSet :: HashMap a () -> HashSet a
[asMap] :: HashSet a -> HashMap a ()

-- | <math> Construct an empty set.
--   
--   
--   >>> HashSet.empty
--   fromList []
--   
empty :: HashSet a

-- | <math> Construct a set with a single element.
--   
--   
--   >>> HashSet.singleton 1
--   fromList [1]
--   
singleton :: Hashable a => a -> HashSet a

-- | <math> Return True if this set is empty, False
--   otherwise.
--   
--   
--   >>> HashSet.null HashSet.empty
--   True
--   
--   >>> HashSet.null (HashSet.singleton 1)
--   False
--   
null :: HashSet a -> Bool

-- | <math> Return the number of elements in this set.
--   
--   
--   >>> HashSet.size HashSet.empty
--   0
--   
--   >>> HashSet.size (HashSet.fromList [1,2,3])
--   3
--   
size :: HashSet a -> Int

-- | <math> Return True if the given value is present in this
--   set, False otherwise.
--   
--   
--   >>> HashSet.member 1 (Hashset.fromList [1,2,3])
--   True
--   
--   >>> HashSet.member 1 (Hashset.fromList [4,5,6])
--   False
--   
member :: (Eq a, Hashable a) => a -> HashSet a -> Bool

-- | <math> Add the specified value to this set.
--   
--   
--   >>> HashSet.insert 1 HashSet.empty
--   fromList [1]
--   
insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a

-- | <math> Remove the specified value from this set if present.
--   
--   
--   >>> HashSet.delete 1 (HashSet.fromList [1,2,3])
--   fromList [2,3]
--   
--   >>> HashSet.delete 1 (HashSet.fromList [4,5,6])
--   fromList [4,5,6]
--   
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a

-- | <math> Inclusion of sets.
--   
--   
Examples
--   
--   
--   >>> fromList [1,3] `isSubsetOf` fromList [1,2,3]
--   True
--   
--   
--   
--   >>> fromList [1,2] `isSubsetOf` fromList [1,3]
--   False
--   
isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool

-- | <math> Transform this set by applying a function to every value.
--   The resulting set may be smaller than the source.
--   
--   
--   >>> HashSet.map show (HashSet.fromList [1,2,3])
--   HashSet.fromList ["1","2","3"]
--   
map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b

-- | <math> Construct a set containing all elements from both sets.
--   
--   To obtain good performance, the smaller set must be presented as the
--   first argument.
--   
--   
--   >>> union (fromList [1,2]) (fromList [2,3])
--   fromList [1,2,3]
--   
union :: Eq a => HashSet a -> HashSet a -> HashSet a

-- | Construct a set containing all elements from a list of sets.
unions :: Eq a => [HashSet a] -> HashSet a

-- | <math> Difference of two sets. Return elements of the first set
--   not existing in the second.
--   
--   
--   >>> HashSet.difference (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
--   fromList [1]
--   
difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a

-- | <math> Intersection of two sets. Return elements present in both
--   the first set and the second.
--   
--   
--   >>> HashSet.intersection (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
--   fromList [2,3]
--   
intersection :: Eq a => HashSet a -> HashSet a -> HashSet a

-- | <math> Reduce this set by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (b -> a -> a) -> a -> HashSet b -> a

-- | <math> Reduce this set by applying a binary operator to all
--   elements, using the given starting value (typically the right-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' :: (b -> a -> a) -> a -> HashSet b -> a

-- | <math> Reduce this set by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldl :: (a -> b -> a) -> a -> HashSet b -> a

-- | <math> Reduce this set 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.
foldl' :: (a -> b -> a) -> a -> HashSet b -> a

-- | <math> Filter this set by retaining only elements satisfying a
--   predicate.
filter :: (a -> Bool) -> HashSet a -> HashSet a

-- | <math> Return a list of this set's elements. The list is
--   produced lazily. The order of its elements is unspecified, and it may
--   change from version to version of either this package or of
--   hashable.
toList :: HashSet a -> [a]

-- | <math> Construct a set from a list of elements.
fromList :: (Eq a, Hashable a) => [a] -> HashSet a

-- | <math> Convert to set to the equivalent HashMap with
--   () values.
--   
--   
--   >>> HashSet.toMap (HashSet.singleton 1)
--   fromList [(1,())]
--   
toMap :: HashSet a -> HashMap a ()

-- | <math> Convert from the equivalent HashMap with
--   () values.
--   
--   
--   >>> HashSet.fromMap (HashMap.singleton 1 ())
--   fromList [1]
--   
fromMap :: HashMap a () -> HashSet a

-- | <math> Produce a HashSet of all the keys in the given
--   HashMap.
--   
--   
--   >>> HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")]
--   fromList [1,2]
--   
keysSet :: HashMap k a -> HashSet k
instance (GHC.Internal.Data.Data.Data a, GHC.Classes.Eq a, Data.Hashable.Class.Hashable a) => GHC.Internal.Data.Data.Data (Data.HashSet.Internal.HashSet a)
instance Data.Functor.Classes.Eq1 Data.HashSet.Internal.HashSet
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.HashSet.Internal.HashSet a)
instance GHC.Internal.Data.Foldable.Foldable Data.HashSet.Internal.HashSet
instance Data.Hashable.Class.Hashable1 Data.HashSet.Internal.HashSet
instance Data.Hashable.Class.Hashable a => Data.Hashable.Class.Hashable (Data.HashSet.Internal.HashSet a)
instance (GHC.Classes.Eq a, Data.Hashable.Class.Hashable a) => GHC.Internal.IsList.IsList (Data.HashSet.Internal.HashSet a)
instance Language.Haskell.TH.Syntax.Lift a => Language.Haskell.TH.Syntax.Lift (Data.HashSet.Internal.HashSet a)
instance (Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => GHC.Internal.Base.Monoid (Data.HashSet.Internal.HashSet a)
instance Control.DeepSeq.NFData1 Data.HashSet.Internal.HashSet
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.HashSet.Internal.HashSet a)
instance Data.Functor.Classes.Ord1 Data.HashSet.Internal.HashSet
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.HashSet.Internal.HashSet a)
instance (GHC.Classes.Eq a, Data.Hashable.Class.Hashable a, GHC.Internal.Read.Read a) => GHC.Internal.Read.Read (Data.HashSet.Internal.HashSet a)
instance (Data.Hashable.Class.Hashable a, GHC.Classes.Eq a) => GHC.Internal.Base.Semigroup (Data.HashSet.Internal.HashSet a)
instance Data.Functor.Classes.Show1 Data.HashSet.Internal.HashSet
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.HashSet.Internal.HashSet a)

-- | 
Introduction
--   
--   HashSet allows you to store unique elements, providing
--   efficient insertion, lookups, and deletion. A HashSet makes no
--   guarantees as to the order of its elements.
--   
--   If you are storing sets of Data.Ints consider using
--   Data.IntSet from the containers package.
--   
--   
Examples
--   
--   All the examples below assume HashSet is imported qualified,
--   and uses the following dataStructures set.
--   
--   
--   >>> import qualified Data.HashSet as HashSet
--   
--   >>> let dataStructures = HashSet.fromList ["Set", "Map", "Graph", "Sequence"]
--   
--   
--   
Basic Operations
--   
--   Check membership in a set:
--   
--   
--   >>> -- Check if "Map" and "Trie" are in the set of data structures.
--   
--   >>> HashSet.member "Map" dataStructures
--   True
--   
--   >>> HashSet.member "Trie" dataStructures
--   False
--   
--   
--   Add a new entry to the set:
--   
--   
--   >>> let moreDataStructures = HashSet.insert "Trie" dataStructures
--   
--   >>> HashSet.member "Trie" moreDataStructures
--   > True
--   
--   
--   Remove the "Graph" entry from the set of data structures.
--   
--   
--   >>> let fewerDataStructures = HashSet.delete "Graph" dataStructures
--   
--   >>> HashSet.toList fewerDataStructures
--   ["Map","Set","Sequence"]
--   
--   
--   Create a new set and combine it with our original set.
--   
--   
--   >>> let unorderedDataStructures = HashSet.fromList ["HashSet", "HashMap"]
--   
--   >>> HashSet.union dataStructures unorderedDataStructures
--   fromList ["Map","HashSet","Graph","HashMap","Set","Sequence"]
--   
--   
--   
Using custom data with HashSet
--   
--   To create a HashSet of your custom type, the type must have
--   instances for Eq and Hashable. The Hashable
--   typeclass is defined in the hashable package, see the
--   documentation for information on how to make your type an instance of
--   Hashable.
--   
--   We'll start by setting up our custom data type:
--   
--   
--   >>> :set -XDeriveGeneric
--   
--   >>> import GHC.Generics (Generic)
--   
--   >>> import Data.Hashable
--   
--   >>> data Person = Person { name :: String, likesDogs :: Bool } deriving (Show, Eq, Generic)
--   
--   >>> instance Hashable Person
--   
--   
--   And now we'll use it!
--   
--   
--   >>> let people = HashSet.fromList [Person "Lana" True, Person "Joe" False, Person "Simon" True]
--   
--   >>> HashSet.filter likesDogs people
--   fromList [Person {name = "Simon", likesDogs = True},Person {name = "Lana", likesDogs = True}]
--   
--   
--   
Performance
--   
--   The implementation is based on hash array mapped tries. A
--   HashSet is often faster than other Ord-based set types,
--   especially when value comparisons are expensive, as in the case of
--   strings.
--   
--   Many operations have a average-case complexity of <math>. The
--   implementation uses a large base (i.e. 16 or 32) so in practice these
--   operations are constant time.
module Data.HashSet

-- | A set of values. A set cannot contain duplicate values.
data HashSet a

-- | <math> Construct an empty set.
--   
--   
--   >>> HashSet.empty
--   fromList []
--   
empty :: HashSet a

-- | <math> Construct a set with a single element.
--   
--   
--   >>> HashSet.singleton 1
--   fromList [1]
--   
singleton :: Hashable a => a -> HashSet a

-- | <math> Construct a set containing all elements from both sets.
--   
--   To obtain good performance, the smaller set must be presented as the
--   first argument.
--   
--   
--   >>> union (fromList [1,2]) (fromList [2,3])
--   fromList [1,2,3]
--   
union :: Eq a => HashSet a -> HashSet a -> HashSet a

-- | Construct a set containing all elements from a list of sets.
unions :: Eq a => [HashSet a] -> HashSet a

-- | <math> Return True if this set is empty, False
--   otherwise.
--   
--   
--   >>> HashSet.null HashSet.empty
--   True
--   
--   >>> HashSet.null (HashSet.singleton 1)
--   False
--   
null :: HashSet a -> Bool

-- | <math> Return the number of elements in this set.
--   
--   
--   >>> HashSet.size HashSet.empty
--   0
--   
--   >>> HashSet.size (HashSet.fromList [1,2,3])
--   3
--   
size :: HashSet a -> Int

-- | <math> Return True if the given value is present in this
--   set, False otherwise.
--   
--   
--   >>> HashSet.member 1 (Hashset.fromList [1,2,3])
--   True
--   
--   >>> HashSet.member 1 (Hashset.fromList [4,5,6])
--   False
--   
member :: (Eq a, Hashable a) => a -> HashSet a -> Bool

-- | <math> Add the specified value to this set.
--   
--   
--   >>> HashSet.insert 1 HashSet.empty
--   fromList [1]
--   
insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a

-- | <math> Remove the specified value from this set if present.
--   
--   
--   >>> HashSet.delete 1 (HashSet.fromList [1,2,3])
--   fromList [2,3]
--   
--   >>> HashSet.delete 1 (HashSet.fromList [4,5,6])
--   fromList [4,5,6]
--   
delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a

-- | <math> Inclusion of sets.
--   
--   
Examples
--   
--   
--   >>> fromList [1,3] `isSubsetOf` fromList [1,2,3]
--   True
--   
--   
--   
--   >>> fromList [1,2] `isSubsetOf` fromList [1,3]
--   False
--   
isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool

-- | <math> Transform this set by applying a function to every value.
--   The resulting set may be smaller than the source.
--   
--   
--   >>> HashSet.map show (HashSet.fromList [1,2,3])
--   HashSet.fromList ["1","2","3"]
--   
map :: (Hashable b, Eq b) => (a -> b) -> HashSet a -> HashSet b

-- | <math> Difference of two sets. Return elements of the first set
--   not existing in the second.
--   
--   
--   >>> HashSet.difference (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
--   fromList [1]
--   
difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a

-- | <math> Intersection of two sets. Return elements present in both
--   the first set and the second.
--   
--   
--   >>> HashSet.intersection (HashSet.fromList [1,2,3]) (HashSet.fromList [2,3,4])
--   fromList [2,3]
--   
intersection :: Eq a => HashSet a -> HashSet a -> HashSet a

-- | <math> Reduce this set 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.
foldl' :: (a -> b -> a) -> a -> HashSet b -> a

-- | <math> Reduce this set by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (b -> a -> a) -> a -> HashSet b -> a

-- | <math> Filter this set by retaining only elements satisfying a
--   predicate.
filter :: (a -> Bool) -> HashSet a -> HashSet a

-- | <math> Return a list of this set's elements. The list is
--   produced lazily. The order of its elements is unspecified, and it may
--   change from version to version of either this package or of
--   hashable.
toList :: HashSet a -> [a]

-- | <math> Construct a set from a list of elements.
fromList :: (Eq a, Hashable a) => [a] -> HashSet a

-- | <math> Convert to set to the equivalent HashMap with
--   () values.
--   
--   
--   >>> HashSet.toMap (HashSet.singleton 1)
--   fromList [(1,())]
--   
toMap :: HashSet a -> HashMap a ()

-- | <math> Convert from the equivalent HashMap with
--   () values.
--   
--   
--   >>> HashSet.fromMap (HashMap.singleton 1 ())
--   fromList [1]
--   
fromMap :: HashMap a () -> HashSet a

-- | 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 <math>. The
--   implementation uses a large base (i.e. 16 or 32) so in practice these
--   operations are constant time.
module Data.HashMap.Strict

-- | A map from keys to values. A map cannot contain duplicate keys; each
--   key can map to at most one value.
data HashMap k v

-- | <math> Construct an empty map.
empty :: HashMap k v

-- | <math> Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | <math> Return True if this map is empty, False
--   otherwise.
null :: HashMap k v -> Bool

-- | <math> Return the number of key-value mappings in this map.
size :: HashMap k v -> Int

-- | <math> Return True if the specified key is present in the
--   map, False otherwise.
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
--   
--   This is a flipped version of lookup.
(!?) :: (Eq k, Hashable k) => HashMap k v -> k -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   the default value if this map contains no mapping for the key.
findWithDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> 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.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> Return the value to which the specified key is mapped.
--   Calls error if this map contains no mapping for the key.
(!) :: (Eq k, Hashable k, HasCallStack) => HashMap k v -> k -> v
infixl 9 !

-- | <math> 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.
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

-- | <math> 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
--   
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

-- | <math> Remove the mapping for the specified key from this map if
--   present.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v

-- | <math> Adjust the value tied to a given key in this map only if
--   it is present. Otherwise, leave the map alone.
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (update f k map) updates
--   the value x at k (if it is in the map). If (f
--   x) is Nothing, the element is deleted. If it is
--   (Just y), the key k is bound to the new value
--   y.
update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a

-- | <math> The expression (alter f k map) alters the
--   value x at k, or absence thereof.
--   
--   alter can be used to insert, delete, or update a value in a
--   map. In short:
--   
--   
--   lookup k (alter f k m) = f (lookup k m)
--   
alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (alterF f k map) alters
--   the value 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.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | <math> 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
--   
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | <math> 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
--   
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | <math> 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')]
--   
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | <math> The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWith :: Eq k => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | <math> 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 => (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | Construct a set containing all elements from a list of sets.
unions :: Eq k => [HashMap k v] -> HashMap k v

-- | Given maps bc and ab, relate the keys of ab
--   to the values of bc, by using the values of ab as
--   keys for lookups in bc.
--   
--   Complexity: <math>, where <math> 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 !?)
--   
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

-- | <math> Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Perform an Applicative action for each key-value
--   pair in a HashMap and produce a HashMap of all the
--   results. Each HashMap will be strict in all its values.
--   
--   
--   traverseWithKey f = fmap (map id) . Data.HashMap.Lazy.traverseWithKey f
--   
--   
--   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.
traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)

-- | <math>. mapKeys f s is the map obtained by
--   applying f 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")]
--   
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | <math> Difference of two maps. Return elements of the first map
--   not existing in the second.
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Difference with a combining function. When two equal keys
--   are encountered, the combining function is applied to the values of
--   these keys. If it returns Nothing, the element is discarded
--   (proper set difference). If it returns (Just y), the
--   element is updated with a new value y.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. Return elements of the first
--   map for keys existing in the second.
intersection :: Eq k => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. If a key occurs in both maps
--   the provided function is used to combine the values from the two maps.
intersectionWith :: Eq k => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

-- | <math> 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

-- | <math> Reduce the map by applying a function to each element and
--   combining the results with a monoid operation.
foldMapWithKey :: Monoid m => (k -> v -> m) -> HashMap k v -> m

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldl :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldr' :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   using the result in the next application. This function is strict in
--   the starting value.
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   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

-- | <math> 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

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a

-- | <math> Filter this map by retaining only elements which values
--   satisfy a predicate.
filter :: (v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Filter this map by retaining only elements satisfying a
--   predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Transform this map by applying a function to every value
--   and retaining only some of them.
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2

-- | <math> 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

-- | <math> Return a list of this map's keys. The list is produced
--   lazily.
keys :: HashMap k v -> [k]

-- | <math> Return a list of this map's values. The list is produced
--   lazily.
elems :: HashMap k v -> [v]

-- | <math> Return a list of this map's elements. The list is
--   produced lazily. The order of its elements is unspecified, and it may
--   change from version to version of either this package or of
--   hashable.
toList :: HashMap k v -> [(k, v)]

-- | <math> Construct a map with the supplied mappings. If the list
--   contains duplicate mappings, the later mappings take precedence.
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v

-- | <math> 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 key-value 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 occurrences 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)))]
--   
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | <math> Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   
Examples
--   
--   Given a list of key-value 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)))]
--   
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v

-- | <math> Produce a HashSet of all the keys in the given
--   HashMap.
--   
--   
--   >>> HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")]
--   fromList [1,2]
--   
keysSet :: HashMap k a -> HashSet k

-- | 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 <math>. The
--   implementation uses a large base (i.e. 16 or 32) so in practice these
--   operations are constant time.
module Data.HashMap.Lazy

-- | A map from keys to values. A map cannot contain duplicate keys; each
--   key can map to at most one value.
data HashMap k v

-- | <math> Construct an empty map.
empty :: HashMap k v

-- | <math> Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | <math> Return True if this map is empty, False
--   otherwise.
null :: HashMap k v -> Bool

-- | <math> Return the number of key-value mappings in this map.
size :: HashMap k v -> Int

-- | <math> Return True if the specified key is present in the
--   map, False otherwise.
member :: (Eq k, Hashable k) => k -> HashMap k a -> Bool

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   Nothing if this map contains no mapping for the key.
--   
--   This is a flipped version of lookup.
(!?) :: (Eq k, Hashable k) => HashMap k v -> k -> Maybe v

-- | <math> Return the value to which the specified key is mapped, or
--   the default value if this map contains no mapping for the key.
findWithDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> 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.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

-- | <math> Return the value to which the specified key is mapped.
--   Calls error if this map contains no mapping for the key.
(!) :: (Eq k, Hashable k, HasCallStack) => HashMap k v -> k -> v
infixl 9 !

-- | <math> 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.
insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v

-- | <math> 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
--   
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

-- | <math> Remove the mapping for the specified key from this map if
--   present.
delete :: (Eq k, Hashable k) => k -> HashMap k v -> HashMap k v

-- | <math> Adjust the value tied to a given key in this map only if
--   it is present. Otherwise, leave the map alone.
adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (update f k map) updates
--   the value x at k (if it is in the map). If (f
--   x) is Nothing, the element is deleted. If it is
--   (Just y), the key k is bound to the new value
--   y.
update :: (Eq k, Hashable k) => (a -> Maybe a) -> k -> HashMap k a -> HashMap k a

-- | <math> The expression (alter f k map) alters the
--   value x at k, or absence thereof.
--   
--   alter can be used to insert, delete, or update a value in a
--   map. In short:
--   
--   
--   lookup k (alter f k m) = f (lookup k m)
--   
alter :: (Eq k, Hashable k) => (Maybe v -> Maybe v) -> k -> HashMap k v -> HashMap k v

-- | <math> The expression (alterF f k map) alters
--   the value 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.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | <math> 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
--   
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | <math> 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
--   
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | <math> 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')]
--   
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | <math> The union of two maps. If a key occurs in both maps, the
--   provided function (first argument) will be used to compute the result.
unionWith :: Eq k => (v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | <math> 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 => (k -> v -> v -> v) -> HashMap k v -> HashMap k v -> HashMap k v

-- | Construct a set containing all elements from a list of sets.
unions :: Eq k => [HashMap k v] -> HashMap k v

-- | Given maps bc and ab, relate the keys of ab
--   to the values of bc, by using the values of ab as
--   keys for lookups in bc.
--   
--   Complexity: <math>, where <math> 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 !?)
--   
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

-- | <math> Transform this map by applying a function to every value.
map :: (v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Transform this map by applying a function to every value.
mapWithKey :: (k -> v1 -> v2) -> HashMap k v1 -> HashMap k v2

-- | <math> Perform an Applicative action for each key-value
--   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.
traverseWithKey :: Applicative f => (k -> v1 -> f v2) -> HashMap k v1 -> f (HashMap k v2)

-- | <math>. mapKeys f s is the map obtained by
--   applying f 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")]
--   
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | <math> Difference of two maps. Return elements of the first map
--   not existing in the second.
difference :: (Eq k, Hashable k) => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Difference with a combining function. When two equal keys
--   are encountered, the combining function is applied to the values of
--   these keys. If it returns Nothing, the element is discarded
--   (proper set difference). If it returns (Just y), the
--   element is updated with a new value y.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. Return elements of the first
--   map for keys existing in the second.
intersection :: Eq k => HashMap k v -> HashMap k w -> HashMap k v

-- | <math> Intersection of two maps. If a key occurs in both maps
--   the provided function is used to combine the values from the two maps.
intersectionWith :: Eq k => (v1 -> v2 -> v3) -> HashMap k v1 -> HashMap k v2 -> HashMap k v3

-- | <math> 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

-- | <math> Reduce the map by applying a function to each element and
--   combining the results with a monoid operation.
foldMapWithKey :: Monoid m => (k -> v -> m) -> HashMap k v -> m

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-identity
--   of the operator).
foldr :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldl :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldr' :: (v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   using the result in the next application. This function is strict in
--   the starting value.
foldl' :: (a -> v -> a) -> a -> HashMap k v -> a

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the right-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.
foldrWithKey' :: (k -> v -> a -> a) -> a -> HashMap k v -> a

-- | <math> 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
--   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

-- | <math> 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

-- | <math> Reduce this map by applying a binary operator to all
--   elements, using the given starting value (typically the left-identity
--   of the operator).
foldlWithKey :: (a -> k -> v -> a) -> a -> HashMap k v -> a

-- | <math> Filter this map by retaining only elements which values
--   satisfy a predicate.
filter :: (v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Filter this map by retaining only elements satisfying a
--   predicate.
filterWithKey :: (k -> v -> Bool) -> HashMap k v -> HashMap k v

-- | <math> Transform this map by applying a function to every value
--   and retaining only some of them.
mapMaybe :: (v1 -> Maybe v2) -> HashMap k v1 -> HashMap k v2

-- | <math> 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

-- | <math> Return a list of this map's keys. The list is produced
--   lazily.
keys :: HashMap k v -> [k]

-- | <math> Return a list of this map's values. The list is produced
--   lazily.
elems :: HashMap k v -> [v]

-- | <math> Return a list of this map's elements. The list is
--   produced lazily. The order of its elements is unspecified, and it may
--   change from version to version of either this package or of
--   hashable.
toList :: HashMap k v -> [(k, v)]

-- | <math> Construct a map with the supplied mappings. If the list
--   contains duplicate mappings, the later mappings take precedence.
fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v

-- | <math> 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 key-value 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 occurrences 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)))]
--   
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | <math> Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   
Examples
--   
--   Given a list of key-value 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)))]
--   
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v

-- | <math> Produce a HashSet of all the keys in the given
--   HashMap.
--   
--   
--   >>> HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")]
--   fromList [1,2]
--   
keysSet :: HashMap k a -> HashSet k
