-- 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.
--   
--   <i>Security</i>
--   
--   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 <tt>Data.Map</tt> or <tt>Data.Set</tt> from
--   the <tt>containers</tt> package instead.
@package unordered-containers
@version 0.2.20.1


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> between minor versions of this package.
--   
--   Authors importing this module are expected to track development
--   closely.
--   
--   <h1>Description</h1>
--   
--   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 #)

-- | &lt;math&gt; Update the element at the given position in this array.
update :: Array e -> Int -> e -> Array e

-- | &lt;math&gt; 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

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

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

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

-- | &lt;math&gt; 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 <a>map</a>.
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 <a>shrinkSmallMutableArray#</a> 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)


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> between minor versions of this package.
--   
--   Authors importing this module are expected to track development
--   closely.
--   
--   <h1>Description</h1>
--   
--   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


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> 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:
--   
--   <ul>
--   <li><a>Empty</a> is not a valid sub-node. It can only appear at the
--   root. (INV1)</li>
--   </ul>
Empty :: HashMap k v

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

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

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

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

-- | &lt;math&gt; Construct an empty map.
empty :: HashMap k v

-- | &lt;math&gt; Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | &lt;math&gt; Return <a>True</a> if this map is empty, <a>False</a>
--   otherwise.
null :: HashMap k v -> Bool

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

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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>findWithDefault</a>.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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:
--   
--   <pre>
--   insertWith f k v map
--     where f new old = new + old
--   </pre>
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

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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; The expression <tt>(<a>alterF</a> f k map)</tt> alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof.
--   
--   <a>alterF</a> can be used to insert, delete, or update a value in a
--   map.
--   
--   Note: <a>alterF</a> is a flipped version of the <tt>at</tt> combinator
--   from <a>Control.Lens.At</a>.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | &lt;math&gt; Inclusion of maps. A map is included in another map if
--   the keys are subsets and the corresponding values are equal:
--   
--   <pre>
--   isSubmapOf m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                      and [ v1 == v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a')] `isSubmapOf` fromList [(1,'a'),(2,'b')]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a'),(2,'b')] `isSubmapOf` fromList [(1,'a')]
--   False
--   </pre>
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | &lt;math&gt; 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:
--   
--   <pre>
--   isSubmapOfBy cmpV m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                             and [ v1 `cmpV` v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'b')]) (fromList [(1,'a'),(2,'c')])
--   False
--   </pre>
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | &lt;math&gt; The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [(1,'a'),(2,'b')]) (fromList [(2,'c'),(3,'d')])
--   fromList [(1,'a'),(2,'b'),(3,'d')]
--   </pre>
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <tt>bc</tt> and <tt>ab</tt>, relate the keys of <tt>ab</tt>
--   to the values of <tt>bc</tt>, by using the values of <tt>ab</tt> as
--   keys for lookups in <tt>bc</tt>.
--   
--   Complexity: &lt;math&gt;, where &lt;math&gt; is the size of the first
--   argument
--   
--   <pre>
--   &gt;&gt;&gt; compose (fromList [('a', "A"), ('b', "B")]) (fromList [(1,'a'),(2,'b'),(3,'z')])
--   fromList [(1,"A"),(2,"B")]
--   </pre>
--   
--   <pre>
--   (<a>compose</a> bc ab <a>!?</a>) = (bc <a>!?</a>) &lt;=&lt; (ab <a>!?</a>)
--   </pre>
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

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

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

-- | &lt;math&gt; Perform an <a>Applicative</a> action for each key-value
--   pair in a <a>HashMap</a> and produce a <a>HashMap</a> 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)

-- | &lt;math&gt;. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> 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.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])
--   fromList [(4,"b"),(6,"a")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(1,"c")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(3,"c")]
--   </pre>
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

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

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

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

-- | &lt;math&gt; 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
--   <tt>hashable</tt>.
toList :: HashMap k v -> [(k, v)]

-- | &lt;math&gt; 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

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function <tt>f</tt> to merge duplicate entries with <tt>(f
--   newVal oldVal)</tt>.
--   
--   <h3>Examples</h3>
--   
--   Given a list <tt>xs</tt>, create a map with the number of occurrences
--   of each element in <tt>xs</tt>:
--   
--   <pre>
--   let xs = ['a', 'b', 'a']
--   in fromListWith (+) [ (x, 1) | x &lt;- xs ]
--   
--   = fromList [('a', 2), ('b', 1)]
--   </pre>
--   
--   Given a list of key-value pairs <tt>xs :: [(k, v)]</tt>, group all
--   values by their keys and return a <tt>HashMap k [v]</tt>.
--   
--   <pre>
--   let xs = [('a', 1), ('b', 2), ('a', 3)]
--   in fromListWith (++) [ (k, [v]) | (k, v) &lt;- xs ]
--   
--   = fromList [('a', [3, 1]), ('b', [2])]
--   </pre>
--   
--   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 <tt>f</tt> is not commutative or not associative.
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f d (f c (f b a)))]
--   </pre>
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   <h3>Examples</h3>
--   
--   Given a list of key-value pairs where the keys are of different
--   flavours, e.g:
--   
--   <pre>
--   data Key = Div | Sub
--   </pre>
--   
--   and the values need to be combined differently when there are
--   duplicates, depending on the key:
--   
--   <pre>
--   combine Div = div
--   combine Sub = (-)
--   </pre>
--   
--   then <tt>fromListWithKey</tt> can be used as follows:
--   
--   <pre>
--   fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)]
--   = fromList [(Div, 3), (Sub, 1)]
--   </pre>
--   
--   More generally, duplicate entries are accumulated as follows;
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f k d (f k c (f k b a)))]
--   </pre>
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
--   <a>hash</a>.
type Hash = Word

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

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

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

-- | Create a <a>Collision</a> value with two <a>Leaf</a> 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 <a>Hash</a> and a <a>Shift</a> that indicates the level in the
--   tree, compute the bitmap that contains only the <a>index</a> of the
--   hash at this level.
--   
--   The result can be used for constructing one-element
--   <a>BitmapIndexed</a> nodes or to check whether a <a>BitmapIndexed</a>
--   node may possibly contain the given <a>Hash</a>.
--   
--   <pre>
--   &gt;&gt;&gt; mask 0b0010_0010 0
--   0b0100
--   </pre>
mask :: Hash -> Shift -> Bitmap

-- | Given a <a>Hash</a> and a <a>Shift</a> that indicates the level in the
--   tree, compute the index into a <a>Full</a> node or into the bitmap of
--   a <a>BitmapIndexed</a> node.
--   
--   <pre>
--   &gt;&gt;&gt; index 0b0010_0010 0
--   0b0000_0010
--   </pre>
index :: Hash -> Shift -> Int

-- | Number of bits that are inspected at each level of the hash tree.
--   
--   This constant is named <i>t</i> in the original <i>Ideal Hash
--   Trees</i> 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 <a>Full</a> node, i.e. <tt>2 ^
--   <a>bitsPerSubkey</a></tt>.
maxChildren :: Int

-- | Helper function to detect <a>Leaf</a>s and <a>Collision</a>s.
isLeafOrCollision :: HashMap k v -> Bool

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

-- | Bit mask with the lowest <a>bitsPerSubkey</a> bits set, i.e.
--   <tt>0b11111</tt>.
subkeyMask :: Word

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

-- | This array index is computed by counting the number of 1-bits below
--   the <a>index</a> represented by the mask.
--   
--   <pre>
--   &gt;&gt;&gt; sparseIndex 0b0110_0110 0b0010_0000
--   2
--   </pre>
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 <tt>f</tt>.
unionArrayBy :: (a -> a -> a) -> Bitmap -> Bitmap -> Array a -> Array a -> Array a

-- | &lt;math&gt; Update the element at the given position in this array.
updateFullArray :: Array e -> Int -> e -> Array e

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

-- | &lt;math&gt; 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 <a>filterWithKey</a> and
--   <a>mapMaybeWithKey</a>, 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 <a>lookupRecordCollision</a>. If there is no
--   collision, pass (-1) as collPos.
deleteKeyExists :: Int -> Hash -> k -> HashMap k v -> HashMap k v

-- | <tt>insertModifying</tt> 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 <a>adjust</a>, 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)


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> between minor versions of this package.
--   
--   Authors importing this module are expected to track development
--   closely.
--   
--   <h1>Description</h1>
--   
--   Debugging utilities for <a>HashMap</a>s.
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 <a>HashMap</a> 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 <a>Hash</a> with <a>bitsPerSubkey</a> 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)


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> between minor versions of this package.
--   
--   Authors importing this module are expected to track development
--   closely.
--   
--   <h1>Description</h1>
--   
--   A map from <i>hashable</i> keys to values. A map cannot contain
--   duplicate keys; each key can map to at most one value. A
--   <a>HashMap</a> makes no guarantees as to the order of its elements.
--   
--   The implementation is based on <i>hash array mapped tries</i>. A
--   <a>HashMap</a> 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 &lt;math&gt;. 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

-- | &lt;math&gt; Construct an empty map.
empty :: HashMap k v

-- | &lt;math&gt; Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | &lt;math&gt; Return <a>True</a> if this map is empty, <a>False</a>
--   otherwise.
null :: HashMap k v -> Bool

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

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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>findWithDefault</a>.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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:
--   
--   <pre>
--   insertWith f k v map
--     where f new old = new + old
--   </pre>
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; The expression (<tt><a>alterF</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof.
--   
--   <a>alterF</a> can be used to insert, delete, or update a value in a
--   map.
--   
--   Note: <a>alterF</a> is a flipped version of the <tt>at</tt> combinator
--   from <a>Control.Lens.At</a>.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | &lt;math&gt; Inclusion of maps. A map is included in another map if
--   the keys are subsets and the corresponding values are equal:
--   
--   <pre>
--   isSubmapOf m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                      and [ v1 == v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a')] `isSubmapOf` fromList [(1,'a'),(2,'b')]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a'),(2,'b')] `isSubmapOf` fromList [(1,'a')]
--   False
--   </pre>
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | &lt;math&gt; 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:
--   
--   <pre>
--   isSubmapOfBy cmpV m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                             and [ v1 `cmpV` v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'b')]) (fromList [(1,'a'),(2,'c')])
--   False
--   </pre>
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | &lt;math&gt; The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [(1,'a'),(2,'b')]) (fromList [(2,'c'),(3,'d')])
--   fromList [(1,'a'),(2,'b'),(3,'d')]
--   </pre>
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <tt>bc</tt> and <tt>ab</tt>, relate the keys of <tt>ab</tt>
--   to the values of <tt>bc</tt>, by using the values of <tt>ab</tt> as
--   keys for lookups in <tt>bc</tt>.
--   
--   Complexity: &lt;math&gt;, where &lt;math&gt; is the size of the first
--   argument
--   
--   <pre>
--   &gt;&gt;&gt; compose (fromList [('a', "A"), ('b', "B")]) (fromList [(1,'a'),(2,'b'),(3,'z')])
--   fromList [(1,"A"),(2,"B")]
--   </pre>
--   
--   <pre>
--   (<a>compose</a> bc ab <a>!?</a>) = (bc <a>!?</a>) &lt;=&lt; (ab <a>!?</a>)
--   </pre>
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

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

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

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

-- | &lt;math&gt;. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> 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.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])
--   fromList [(4,"b"),(6,"a")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(1,"c")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(3,"c")]
--   </pre>
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; 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
--   <tt>hashable</tt>.
toList :: HashMap k v -> [(k, v)]

-- | &lt;math&gt; 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

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function <tt>f</tt> to merge duplicate entries with <tt>(f
--   newVal oldVal)</tt>.
--   
--   <h3>Examples</h3>
--   
--   Given a list <tt>xs</tt>, create a map with the number of occurrences
--   of each element in <tt>xs</tt>:
--   
--   <pre>
--   let xs = ['a', 'b', 'a']
--   in fromListWith (+) [ (x, 1) | x &lt;- xs ]
--   
--   = fromList [('a', 2), ('b', 1)]
--   </pre>
--   
--   Given a list of key-value pairs <tt>xs :: [(k, v)]</tt>, group all
--   values by their keys and return a <tt>HashMap k [v]</tt>.
--   
--   <pre>
--   let xs = ('a', 1), ('b', 2), ('a', 3)]
--   in fromListWith (++) [ (k, [v]) | (k, v) &lt;- xs ]
--   
--   = fromList [('a', [3, 1]), ('b', [2])]
--   </pre>
--   
--   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 <tt>f</tt> is not commutative or not associative.
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f d (f c (f b a)))]
--   </pre>
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   <h3>Examples</h3>
--   
--   Given a list of key-value pairs where the keys are of different
--   flavours, e.g:
--   
--   <pre>
--   data Key = Div | Sub
--   </pre>
--   
--   and the values need to be combined differently when there are
--   duplicates, depending on the key:
--   
--   <pre>
--   combine Div = div
--   combine Sub = (-)
--   </pre>
--   
--   then <tt>fromListWithKey</tt> can be used as follows:
--   
--   <pre>
--   fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)]
--   = fromList [(Div, 3), (Sub, 1)]
--   </pre>
--   
--   More generally, duplicate entries are accumulated as follows;
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f k d (f k c (f k b a)))]
--   </pre>
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v


-- | <h1>WARNING</h1>
--   
--   This module is considered <b>internal</b>.
--   
--   The Package Versioning Policy <b>does not apply</b>.
--   
--   The contents of this module may change <b>in any way whatsoever</b>
--   and <b>without any warning</b> between minor versions of this package.
--   
--   Authors importing this module are expected to track development
--   closely.
--   
--   <h1>Description</h1>
--   
--   A set of <i>hashable</i> values. A set cannot contain duplicate items.
--   A <a>HashSet</a> makes no guarantees as to the order of its elements.
--   
--   The implementation is based on <i>hash array mapped tries</i>. A
--   <a>HashSet</a> 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 &lt;math&gt;. 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 ()

-- | &lt;math&gt; Construct an empty set.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.empty
--   fromList []
--   </pre>
empty :: HashSet a

-- | &lt;math&gt; Construct a set with a single element.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.singleton 1
--   fromList [1]
--   </pre>
singleton :: Hashable a => a -> HashSet a

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

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

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

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

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

-- | &lt;math&gt; Inclusion of sets.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [1,3] `isSubsetOf` fromList [1,2,3]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [1,2] `isSubsetOf` fromList [1,3]
--   False
--   </pre>
isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool

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

-- | &lt;math&gt; Construct a set containing all elements from both sets.
--   
--   To obtain good performance, the smaller set must be presented as the
--   first argument.
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [1,2]) (fromList [2,3])
--   fromList [1,2,3]
--   </pre>
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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

-- | &lt;math&gt; 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
--   <tt>hashable</tt>.
toList :: HashSet a -> [a]

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

-- | &lt;math&gt; Convert to set to the equivalent <a>HashMap</a> with
--   <tt>()</tt> values.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.toMap (HashSet.singleton 1)
--   fromList [(1,())]
--   </pre>
toMap :: HashSet a -> HashMap a ()

-- | &lt;math&gt; Convert from the equivalent <a>HashMap</a> with
--   <tt>()</tt> values.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.fromMap (HashMap.singleton 1 ())
--   fromList [1]
--   </pre>
fromMap :: HashMap a () -> HashSet a

-- | &lt;math&gt; Produce a <a>HashSet</a> of all the keys in the given
--   <a>HashMap</a>.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.keysSet (HashMap.fromList [(1, "a"), (2, "b")]
--   fromList [1,2]
--   </pre>
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)


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

-- | &lt;math&gt; Construct an empty set.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.empty
--   fromList []
--   </pre>
empty :: HashSet a

-- | &lt;math&gt; Construct a set with a single element.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.singleton 1
--   fromList [1]
--   </pre>
singleton :: Hashable a => a -> HashSet a

-- | &lt;math&gt; Construct a set containing all elements from both sets.
--   
--   To obtain good performance, the smaller set must be presented as the
--   first argument.
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [1,2]) (fromList [2,3])
--   fromList [1,2,3]
--   </pre>
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

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

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

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

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

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

-- | &lt;math&gt; Inclusion of sets.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [1,3] `isSubsetOf` fromList [1,2,3]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [1,2] `isSubsetOf` fromList [1,3]
--   False
--   </pre>
isSubsetOf :: (Eq a, Hashable a) => HashSet a -> HashSet a -> Bool

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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

-- | &lt;math&gt; 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
--   <tt>hashable</tt>.
toList :: HashSet a -> [a]

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

-- | &lt;math&gt; Convert to set to the equivalent <a>HashMap</a> with
--   <tt>()</tt> values.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.toMap (HashSet.singleton 1)
--   fromList [(1,())]
--   </pre>
toMap :: HashSet a -> HashMap a ()

-- | &lt;math&gt; Convert from the equivalent <a>HashMap</a> with
--   <tt>()</tt> values.
--   
--   <pre>
--   &gt;&gt;&gt; HashSet.fromMap (HashMap.singleton 1 ())
--   fromList [1]
--   </pre>
fromMap :: HashMap a () -> HashSet a


-- | A map from <i>hashable</i> keys to values. A map cannot contain
--   duplicate keys; each key can map to at most one value. A
--   <a>HashMap</a> makes no guarantees as to the order of its elements.
--   
--   The implementation is based on <i>hash array mapped tries</i>. A
--   <a>HashMap</a> 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 &lt;math&gt;. 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

-- | &lt;math&gt; Construct an empty map.
empty :: HashMap k v

-- | &lt;math&gt; Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | &lt;math&gt; Return <a>True</a> if this map is empty, <a>False</a>
--   otherwise.
null :: HashMap k v -> Bool

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

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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>findWithDefault</a>.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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:
--   
--   <pre>
--   insertWith f k v map
--     where f new old = new + old
--   </pre>
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; The expression (<tt><a>alterF</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof.
--   
--   <a>alterF</a> can be used to insert, delete, or update a value in a
--   map.
--   
--   Note: <a>alterF</a> is a flipped version of the <tt>at</tt> combinator
--   from <a>Control.Lens.At</a>.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | &lt;math&gt; Inclusion of maps. A map is included in another map if
--   the keys are subsets and the corresponding values are equal:
--   
--   <pre>
--   isSubmapOf m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                      and [ v1 == v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a')] `isSubmapOf` fromList [(1,'a'),(2,'b')]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a'),(2,'b')] `isSubmapOf` fromList [(1,'a')]
--   False
--   </pre>
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | &lt;math&gt; 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:
--   
--   <pre>
--   isSubmapOfBy cmpV m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                             and [ v1 `cmpV` v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'b')]) (fromList [(1,'a'),(2,'c')])
--   False
--   </pre>
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | &lt;math&gt; The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [(1,'a'),(2,'b')]) (fromList [(2,'c'),(3,'d')])
--   fromList [(1,'a'),(2,'b'),(3,'d')]
--   </pre>
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <tt>bc</tt> and <tt>ab</tt>, relate the keys of <tt>ab</tt>
--   to the values of <tt>bc</tt>, by using the values of <tt>ab</tt> as
--   keys for lookups in <tt>bc</tt>.
--   
--   Complexity: &lt;math&gt;, where &lt;math&gt; is the size of the first
--   argument
--   
--   <pre>
--   &gt;&gt;&gt; compose (fromList [('a', "A"), ('b', "B")]) (fromList [(1,'a'),(2,'b'),(3,'z')])
--   fromList [(1,"A"),(2,"B")]
--   </pre>
--   
--   <pre>
--   (<a>compose</a> bc ab <a>!?</a>) = (bc <a>!?</a>) &lt;=&lt; (ab <a>!?</a>)
--   </pre>
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

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

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

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

-- | &lt;math&gt;. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> 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.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])
--   fromList [(4,"b"),(6,"a")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(1,"c")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(3,"c")]
--   </pre>
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; 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
--   <tt>hashable</tt>.
toList :: HashMap k v -> [(k, v)]

-- | &lt;math&gt; 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

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function <tt>f</tt> to merge duplicate entries with <tt>(f
--   newVal oldVal)</tt>.
--   
--   <h3>Examples</h3>
--   
--   Given a list <tt>xs</tt>, create a map with the number of occurrences
--   of each element in <tt>xs</tt>:
--   
--   <pre>
--   let xs = ['a', 'b', 'a']
--   in fromListWith (+) [ (x, 1) | x &lt;- xs ]
--   
--   = fromList [('a', 2), ('b', 1)]
--   </pre>
--   
--   Given a list of key-value pairs <tt>xs :: [(k, v)]</tt>, group all
--   values by their keys and return a <tt>HashMap k [v]</tt>.
--   
--   <pre>
--   let xs = ('a', 1), ('b', 2), ('a', 3)]
--   in fromListWith (++) [ (k, [v]) | (k, v) &lt;- xs ]
--   
--   = fromList [('a', [3, 1]), ('b', [2])]
--   </pre>
--   
--   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 <tt>f</tt> is not commutative or not associative.
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f d (f c (f b a)))]
--   </pre>
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   <h3>Examples</h3>
--   
--   Given a list of key-value pairs where the keys are of different
--   flavours, e.g:
--   
--   <pre>
--   data Key = Div | Sub
--   </pre>
--   
--   and the values need to be combined differently when there are
--   duplicates, depending on the key:
--   
--   <pre>
--   combine Div = div
--   combine Sub = (-)
--   </pre>
--   
--   then <tt>fromListWithKey</tt> can be used as follows:
--   
--   <pre>
--   fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)]
--   = fromList [(Div, 3), (Sub, 1)]
--   </pre>
--   
--   More generally, duplicate entries are accumulated as follows;
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f k d (f k c (f k b a)))]
--   </pre>
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v

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


-- | A map from <i>hashable</i> keys to values. A map cannot contain
--   duplicate keys; each key can map to at most one value. A
--   <a>HashMap</a> makes no guarantees as to the order of its elements.
--   
--   The implementation is based on <i>hash array mapped tries</i>. A
--   <a>HashMap</a> 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 &lt;math&gt;. 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

-- | &lt;math&gt; Construct an empty map.
empty :: HashMap k v

-- | &lt;math&gt; Construct a map with a single element.
singleton :: Hashable k => k -> v -> HashMap k v

-- | &lt;math&gt; Return <a>True</a> if this map is empty, <a>False</a>
--   otherwise.
null :: HashMap k v -> Bool

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

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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>findWithDefault</a>.
lookupDefault :: (Eq k, Hashable k) => v -> k -> HashMap k v -> v

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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:
--   
--   <pre>
--   insertWith f k v map
--     where f new old = new + old
--   </pre>
insertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v -> HashMap k v

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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; The expression <tt>(<a>alterF</a> f k map)</tt> alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof.
--   
--   <a>alterF</a> can be used to insert, delete, or update a value in a
--   map.
--   
--   Note: <a>alterF</a> is a flipped version of the <tt>at</tt> combinator
--   from <a>Control.Lens.At</a>.
alterF :: (Functor f, Eq k, Hashable k) => (Maybe v -> f (Maybe v)) -> k -> HashMap k v -> f (HashMap k v)

-- | &lt;math&gt; Inclusion of maps. A map is included in another map if
--   the keys are subsets and the corresponding values are equal:
--   
--   <pre>
--   isSubmapOf m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                      and [ v1 == v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a')] `isSubmapOf` fromList [(1,'a'),(2,'b')]
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fromList [(1,'a'),(2,'b')] `isSubmapOf` fromList [(1,'a')]
--   False
--   </pre>
isSubmapOf :: (Eq k, Hashable k, Eq v) => HashMap k v -> HashMap k v -> Bool

-- | &lt;math&gt; 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:
--   
--   <pre>
--   isSubmapOfBy cmpV m1 m2 = keys m1 `isSubsetOf` keys m2 &amp;&amp;
--                             and [ v1 `cmpV` v2 | (k1,v1) &lt;- toList m1; let v2 = m2 ! k1 ]
--   </pre>
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'b')]) (fromList [(1,'a'),(2,'c')])
--   False
--   </pre>
isSubmapOfBy :: (Eq k, Hashable k) => (v1 -> v2 -> Bool) -> HashMap k v1 -> HashMap k v2 -> Bool

-- | &lt;math&gt; The union of two maps. If a key occurs in both maps, the
--   mapping from the first will be the mapping in the result.
--   
--   <h4><b>Examples</b></h4>
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [(1,'a'),(2,'b')]) (fromList [(2,'c'),(3,'d')])
--   fromList [(1,'a'),(2,'b'),(3,'d')]
--   </pre>
union :: Eq k => HashMap k v -> HashMap k v -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <tt>bc</tt> and <tt>ab</tt>, relate the keys of <tt>ab</tt>
--   to the values of <tt>bc</tt>, by using the values of <tt>ab</tt> as
--   keys for lookups in <tt>bc</tt>.
--   
--   Complexity: &lt;math&gt;, where &lt;math&gt; is the size of the first
--   argument
--   
--   <pre>
--   &gt;&gt;&gt; compose (fromList [('a', "A"), ('b', "B")]) (fromList [(1,'a'),(2,'b'),(3,'z')])
--   fromList [(1,"A"),(2,"B")]
--   </pre>
--   
--   <pre>
--   (<a>compose</a> bc ab <a>!?</a>) = (bc <a>!?</a>) &lt;=&lt; (ab <a>!?</a>)
--   </pre>
compose :: (Eq b, Hashable b) => HashMap b c -> HashMap a b -> HashMap a c

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

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

-- | &lt;math&gt; Perform an <a>Applicative</a> action for each key-value
--   pair in a <a>HashMap</a> and produce a <a>HashMap</a> 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)

-- | &lt;math&gt;. <tt><a>mapKeys</a> f s</tt> is the map obtained by
--   applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> 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.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeys (+ 1) (fromList [(5,"a"), (3,"b")])
--   fromList [(4,"b"),(6,"a")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(1,"c")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(3,"c")]
--   </pre>
mapKeys :: (Eq k2, Hashable k2) => (k1 -> k2) -> HashMap k1 v -> HashMap k2 v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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 <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWith :: (Eq k, Hashable k) => (v -> w -> Maybe v) -> HashMap k v -> HashMap k w -> HashMap k v

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; 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

-- | &lt;math&gt; 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

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

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

-- | &lt;math&gt; 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
--   <tt>hashable</tt>.
toList :: HashMap k v -> [(k, v)]

-- | &lt;math&gt; 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

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function <tt>f</tt> to merge duplicate entries with <tt>(f
--   newVal oldVal)</tt>.
--   
--   <h3>Examples</h3>
--   
--   Given a list <tt>xs</tt>, create a map with the number of occurrences
--   of each element in <tt>xs</tt>:
--   
--   <pre>
--   let xs = ['a', 'b', 'a']
--   in fromListWith (+) [ (x, 1) | x &lt;- xs ]
--   
--   = fromList [('a', 2), ('b', 1)]
--   </pre>
--   
--   Given a list of key-value pairs <tt>xs :: [(k, v)]</tt>, group all
--   values by their keys and return a <tt>HashMap k [v]</tt>.
--   
--   <pre>
--   let xs = [('a', 1), ('b', 2), ('a', 3)]
--   in fromListWith (++) [ (k, [v]) | (k, v) &lt;- xs ]
--   
--   = fromList [('a', [3, 1]), ('b', [2])]
--   </pre>
--   
--   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 <tt>f</tt> is not commutative or not associative.
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f d (f c (f b a)))]
--   </pre>
fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v

-- | &lt;math&gt; Construct a map from a list of elements. Uses the
--   provided function to merge duplicate entries.
--   
--   <h3>Examples</h3>
--   
--   Given a list of key-value pairs where the keys are of different
--   flavours, e.g:
--   
--   <pre>
--   data Key = Div | Sub
--   </pre>
--   
--   and the values need to be combined differently when there are
--   duplicates, depending on the key:
--   
--   <pre>
--   combine Div = div
--   combine Sub = (-)
--   </pre>
--   
--   then <tt>fromListWithKey</tt> can be used as follows:
--   
--   <pre>
--   fromListWithKey combine [(Div, 2), (Div, 6), (Sub, 2), (Sub, 3)]
--   = fromList [(Div, 3), (Sub, 1)]
--   </pre>
--   
--   More generally, duplicate entries are accumulated as follows;
--   
--   <pre>
--   fromListWith f [(k, a), (k, b), (k, c), (k, d)]
--   = fromList [(k, f k d (f k c (f k b a)))]
--   </pre>
fromListWithKey :: (Eq k, Hashable k) => (k -> v -> v -> v) -> [(k, v)] -> HashMap k v

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