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

-- | Mutable hash tables in the ST monad
--   
--   This package provides a couple of different implementations of mutable
--   hash tables in the ST monad, as well as a typeclass abstracting their
--   common operations, and a set of wrappers to use the hash tables in the
--   IO monad.
--   
--   QUICK START: documentation for the hash table operations is
--   provided in the Data.HashTable.Class module, and the IO
--   wrappers (which most users will probably prefer) are located in the
--   Data.HashTable.IO module.
--   
--   This package currently contains three hash table implementations:
--   
--   
--   
- Data.HashTable.ST.Cuckoo contains an implementation of
--   "cuckoo hashing" as introduced by Pagh and Rodler in 2001 (see
--   http://en.wikipedia.org/wiki/Cuckoo_hashing). Cuckoo hashing
--   has worst-case O(1) lookups and can reach a high "load factor",
--   in which the table can perform acceptably well even when approaching
--   90% full. Randomized testing shows this implementation of cuckoo
--   hashing to be slightly faster on insert and slightly slower on lookup
--   than Data.HashTable.ST.Basic, while being more space efficient
--   by about a half-word per key-value mapping. Cuckoo hashing, like the
--   basic hash table implementation using linear probing, can suffer from
--   long delays when the table is resized.
--   
- Data.HashTable.ST.Basic contains a basic open-addressing
--   hash table using linear probing as the collision strategy. On a pure
--   speed basis it should currently be the fastest available Haskell hash
--   table implementation for lookups, although it has a higher memory
--   overhead than the other tables and can suffer from long delays when
--   the table is resized because all of the elements in the table need to
--   be rehashed.
--   
- Data.HashTable.ST.Linear contains a linear hash table (see
--   http://en.wikipedia.org/wiki/Linear_hashing), which trades some
--   insert and lookup performance for higher space efficiency and much
--   shorter delays when expanding the table. In most cases, benchmarks
--   show this table to be currently slightly faster than
--   Data.HashTable from the Haskell base library.
--   
--   
--   It is recommended to create a concrete type alias in your code when
--   using this package, i.e.:
--   
--   
--   import qualified Data.HashTable.IO as H
--   
--   type HashTable k v = H.BasicHashTable k v
--   
--   foo :: IO (HashTable Int Int)
--   foo = do
--       ht <- H.new
--       H.insert ht 1 1
--       return ht
--   
--   
--   Firstly, this makes it easy to switch to a different hash table
--   implementation, and secondly, using a concrete type rather than
--   leaving your functions abstract in the HashTable class should allow
--   GHC to optimize away the typeclass dictionaries.
--   
--   This package accepts a couple of different cabal flags:
--   
--   
--   
- unsafe-tricks, default ON. If this flag is
--   enabled, we use some unsafe GHC-specific tricks to save indirections
--   (namely unsafeCoerce# and reallyUnsafePtrEquality#.
--   These techniques rely on assumptions about the behaviour of the GHC
--   runtime system and, although they've been tested and should be safe
--   under normal conditions, are slightly dangerous. Caveat emptor. In
--   particular, these techniques are incompatible with HPC code coverage
--   reports.
--   
- sse42, default OFF. If this flag is enabled, we
--   use some SSE 4.2 instructions (see
--   http://en.wikipedia.org/wiki/SSE4, first available on Intel
--   Core 2 processors) to speed up cache-line searches for cuckoo
--   hashing.
--   
- bounds-checking, default OFF. If this flag is
--   enabled, array accesses are bounds-checked.
--   
- debug, default OFF. If turned on, we'll rudely
--   spew debug output to stdout.
--   
- portable, default OFF. If this flag is enabled, we
--   use only pure Haskell code and try not to use unportable GHC
--   extensions. Turning this flag on forces unsafe-tricks and
--   sse42 OFF.
--   
--   
--   Please send bug reports to
--   https://github.com/gregorycollins/hashtables/issues.
@package hashtables
@version 1.4.2

-- | This module contains a HashTable typeclass for the hash table
--   implementations in this package. This allows you to provide functions
--   which will work for any hash table implementation in this collection.
--   
--   It is recommended to create a concrete type alias in your code when
--   using this package, i.e.:
--   
--   
--   import qualified Data.HashTable.IO as H
--   
--   type HashTable k v = H.BasicHashTable k v
--   
--   foo :: IO (HashTable Int Int)
--   foo = do
--       ht <- H.new
--       H.insert ht 1 1
--       return ht
--   
--   
--   or
--   
--   
--   import qualified Data.HashTable.ST.Cuckoo as C
--   import qualified Data.HashTable.Class as H
--   
--   type HashTable s k v = C.HashTable s k v
--   
--   foo :: ST s (HashTable s k v)
--   foo = do
--       ht <- H.new
--       H.insert ht 1 1
--       return ht
--   
--   
--   Firstly, this makes it easy to switch to a different hash table
--   implementation, and secondly, using a concrete type rather than
--   leaving your functions abstract in the HashTable class should
--   allow GHC to optimize away the typeclass dictionaries.
--   
--   Note that the functions in this typeclass are in the ST monad;
--   if you want hash tables in IO, use the convenience wrappers in
--   Data.HashTable.IO.
module Data.HashTable.Class

-- | A typeclass for hash tables in the ST monad. The operations on
--   these hash tables are typically both key- and value-strict.
class HashTable (h :: Type -> Type -> Type -> Type)

-- | Creates a new, default-sized hash table. O(1).
new :: HashTable h => ST s (h s k v)

-- | Creates a new hash table sized to hold n elements.
--   O(n).
newSized :: HashTable h => Int -> ST s (h s k v)

-- | Generalized update. Given a key k, and a user function
--   f, calls:
--   
--   
--   
- `f Nothing` if the key did not exist in the hash table
--   
- `f (Just v)` otherwise
--   
--   
--   If the user function returns (Nothing, _), then the value is
--   deleted from the hash table. Otherwise the mapping for k is
--   inserted or replaced with the provided value.
--   
--   Returns the second part of the tuple returned by f.
mutate :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> (Maybe v -> (Maybe v, a)) -> ST s a

-- | As mutate, except that the action can perform additional side
--   effects.
mutateST :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a

-- | Inserts a key/value mapping into a hash table, replacing any existing
--   mapping for that key.
--   
--   O(n) worst case, O(1) amortized.
insert :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> v -> ST s ()

-- | Deletes a key-value mapping from a hash table. O(n) worst case,
--   O(1) amortized.
delete :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> ST s ()

-- | Looks up a key-value mapping in a hash table. O(n) worst case,
--   (O(1) for cuckoo hash), O(1) amortized.
lookup :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> ST s (Maybe v)

-- | A strict fold over the key-value records of a hash table in the
--   ST monad. O(n).
foldM :: HashTable h => (a -> (k, v) -> ST s a) -> a -> h s k v -> ST s a

-- | A side-effecting map over the key-value records of a hash table.
--   O(n).
mapM_ :: HashTable h => ((k, v) -> ST s b) -> h s k v -> ST s ()

-- | Looks up the index of a key-value mapping in a hash table suitable for
--   passing to nextByIndex.
lookupIndex :: (HashTable h, Eq k, Hashable k) => h s k v -> k -> ST s (Maybe Word)

-- | Returns the next key-value mapping stored at the given index or at a
--   greater index. The index, key, and value of the next record are
--   returned.
nextByIndex :: HashTable h => h s k v -> Word -> ST s (Maybe (Word, k, v))

-- | Computes the overhead (in words) per key-value mapping. Used for
--   debugging, etc; time complexity depends on the underlying hash table
--   implementation. O(n).
computeOverhead :: HashTable h => h s k v -> ST s Double

-- | Create a hash table from a list of key-value pairs. O(n).
fromList :: (HashTable h, Eq k, Hashable k) => [(k, v)] -> ST s (h s k v)

-- | Create a hash table from a list of key-value pairs, with a size hint.
--   O(n).
fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) => Int -> [(k, v)] -> ST s (h s k v)

-- | Given a hash table, produce a list of key-value pairs. O(n).
toList :: HashTable h => h s k v -> ST s [(k, v)]

-- | A basic open-addressing hash table using linear probing. Use this hash
--   table if you...
--   
--   
--   
- want the fastest possible lookups, and very fast inserts.
--   
- don't care about wasting a little bit of memory to get it.
--   
- don't care that a table resize might pause for a long time to
--   rehash all of the key-value mappings.
--   
- have a workload which is not heavy with deletes; deletes clutter
--   the table with deleted markers and force the table to be completely
--   rehashed fairly often.
--   
--   
--   Of the hash tables in this collection, this hash table has the best
--   lookup performance, while maintaining competitive insert performance.
--   
--   Space overhead
--   
--   This table is not especially memory-efficient; firstly, the table has
--   a maximum load factor of 0.83 and will be resized if load exceeds this
--   value. Secondly, to improve insert and lookup performance, we store a
--   16-bit hash code for each key in the table.
--   
--   Each hash table entry requires at least 2.25 words (on a 64-bit
--   machine), two for the pointers to the key and value and one quarter
--   word for the hash code. We don't count key and value pointers as
--   overhead, because they have to be there -- so the overhead for a full
--   slot is at least one quarter word -- but empty slots in the hash table
--   count for a full 2.25 words of overhead. Define m as the
--   number of slots in the table, n as the number of key value
--   mappings, and ws as the machine word size in bytes. If
--   the load factor is k=n/m, the amount of space wasted
--   per mapping in words is:
--   
--   
--   w(n) = (m*(2*ws + 2) - n*(2*ws)) / ws
--   
--   
--   Since m=n/k,
--   
--   
--   w(n) = n/k * (2*ws + 2) - n*(2*ws)
--        = (n * (2 + 2*ws*(1-k))  k)  ws
--   
--   
--   Solving for k=0.83, the maximum load factor, gives a
--   minimum overhead of 0.71 words per mapping on a 64-bit machine,
--   or 1.01 words per mapping on a 32-bit machine. If k=0.5,
--   which should be under normal usage the maximum overhead
--   situation, then the overhead would be 2.5 words per mapping on a
--   64-bit machine, or 3.0 words per mapping on a 32-bit machine.
--   
--   Space overhead: experimental results
--   
--   In randomized testing on a 64-bit machine (see
--   test/compute-overhead/ComputeOverhead.hs in the source
--   distribution), mean overhead (that is, the number of words needed to
--   store the key-value mapping over and above the two words necessary for
--   the key and the value pointers) is approximately 1.24 machine words
--   per key-value mapping with a standard deviation of about 0.30 words,
--   and 1.70 words per mapping at the 95th percentile.
--   
--   Expensive resizes
--   
--   If enough elements are inserted into the table to make it exceed the
--   maximum load factor, the table is resized. A resize involves a
--   complete rehash of all the elements in the table, which means that any
--   given call to insert might take O(n) time in the size of
--   the table, with a large constant factor. If a long pause waiting for
--   the table to resize is unacceptable for your application, you should
--   choose the included linear hash table instead.
--   
--   References:
--   
--   
--   
- Knuth, Donald E. The Art of Computer Programming, vol. 3
--   Sorting and Searching. Addison-Wesley Publishing Company, 1973.
--   
module Data.HashTable.ST.Basic

-- | An open addressing hash table using linear probing.
data HashTable s k v

-- | See the documentation for this function in new.
new :: ST s (HashTable s k v)

-- | See the documentation for this function in newSized.
newSized :: Int -> ST s (HashTable s k v)

-- | Returns the number of mappings currently stored in this table.
--   O(1)
size :: HashTable s k v -> ST s Int

-- | See the documentation for this function in delete.
delete :: (Hashable k, Eq k) => HashTable s k v -> k -> ST s ()

-- | See the documentation for this function in lookup.
lookup :: (Eq k, Hashable k) => HashTable s k v -> k -> ST s (Maybe v)

-- | See the documentation for this function in insert.
insert :: (Eq k, Hashable k) => HashTable s k v -> k -> v -> ST s ()

-- | See the documentation for this function in mutate.
mutate :: (Eq k, Hashable k) => HashTable s k v -> k -> (Maybe v -> (Maybe v, a)) -> ST s a

-- | See the documentation for this function in mutateST.
mutateST :: (Eq k, Hashable k) => HashTable s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a

-- | See the documentation for this function in mapM_.
mapM_ :: ((k, v) -> ST s b) -> HashTable s k v -> ST s ()

-- | See the documentation for this function in foldM.
foldM :: (a -> (k, v) -> ST s a) -> a -> HashTable s k v -> ST s a

-- | See the documentation for this function in computeOverhead.
computeOverhead :: HashTable s k v -> ST s Double
instance Data.HashTable.Class.HashTable Data.HashTable.ST.Basic.HashTable
instance GHC.Internal.Base.Monoid Data.HashTable.ST.Basic.Slot
instance GHC.Internal.Base.Semigroup Data.HashTable.ST.Basic.Slot
instance GHC.Internal.Show.Show (Data.HashTable.ST.Basic.HashTable s k v)
instance GHC.Internal.Show.Show Data.HashTable.ST.Basic.Slot
instance GHC.Internal.Show.Show Data.HashTable.ST.Basic.SlotFindResponse

-- | A hash table using the cuckoo strategy. (See
--   http://en.wikipedia.org/wiki/Cuckoo_hashing). Use this hash
--   table if you...
--   
--   
--   
- want the fastest possible inserts, and very fast lookups.
--   
- are conscious of memory usage; this table has less space overhead
--   than Data.HashTable.ST.Basic or
--   Data.HashTable.ST.Linear.
--   
- don't care that a table resize might pause for a long time to
--   rehash all of the key-value mappings.
--   
--   
--   Details:
--   
--   The basic idea of cuckoo hashing, first introduced by Pagh and Rodler
--   in 2001, is to use d hash functions instead of only one; in
--   this implementation d=2 and the strategy we use is to split up a flat
--   array of slots into k buckets, each cache-line-sized:
--   
--   
--   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+----------+
--   |x0|x1|x2|x3|x4|x5|x6|x7|y0|y1|y2|y3|y4|y5|y6|y7|z0|z1|z2........|
--   +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+----------+
--   [  ^^^  bucket 0  ^^^  ][  ^^^  bucket 1  ^^^  ]...
--   
--   
--   There are actually three parallel arrays: one unboxed array of
--   Ints for hash codes, one boxed array for keys, and one boxed
--   array for values. When looking up a key-value mapping, we hash the key
--   using two hash functions and look in both buckets in the hash code
--   array for the key. Each bucket is cache-line sized, with its keys in
--   no particular order. Because the hash code array is unboxed, we can
--   search it for the key using a highly-efficient branchless strategy in
--   C code, using SSE instructions if available.
--   
--   On insert, if both buckets are full, we knock out a randomly-selected
--   entry from one of the buckets (using a random walk ensures that "key
--   cycles" are broken with maximum probability) and try to repeat the
--   insert procedure. This process may not succeed; if all items have not
--   successfully found a home after some number of tries, we give up and
--   rehash all of the elements into a larger table.
--   
--   Space overhead: experimental results
--   
--   The implementation of cuckoo hash given here is almost as fast for
--   lookups as the basic open-addressing hash table using linear probing,
--   and on average is more space-efficient: in randomized testing on my
--   64-bit machine (see test/compute-overhead/ComputeOverhead.hs
--   in the source distribution), mean overhead is 0.77 machine words per
--   key-value mapping, with a standard deviation of 0.29 words, and 1.23
--   words per mapping at the 95th percentile.
--   
--   References:
--   
--   
--   
- A. Pagh and F. Rodler. Cuckoo hashing. In /Proceedings of the 9th
--   Annual European Symposium on Algorithms/, pp. 121-133, 2001.
--   
module Data.HashTable.ST.Cuckoo

-- | A cuckoo hash table.
data HashTable s k v

-- | See the documentation for this function in new.
new :: ST s (HashTable s k v)

-- | See the documentation for this function in newSized.
newSized :: Int -> ST s (HashTable s k v)

-- | See the documentation for this function in delete.
delete :: (Hashable k, Eq k) => HashTable s k v -> k -> ST s ()

-- | See the documentation for this function in lookup.
lookup :: (Eq k, Hashable k) => HashTable s k v -> k -> ST s (Maybe v)

-- | See the documentation for this function in insert.
insert :: (Eq k, Hashable k) => HashTable s k v -> k -> v -> ST s ()
mutate :: (Eq k, Hashable k) => HashTable s k v -> k -> (Maybe v -> (Maybe v, a)) -> ST s a
mutateST :: (Eq k, Hashable k) => HashTable s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a

-- | See the documentation for this function in mapM_.
mapM_ :: ((k, v) -> ST s a) -> HashTable s k v -> ST s ()

-- | See the documentation for this function in foldM.
foldM :: (a -> (k, v) -> ST s a) -> a -> HashTable s k v -> ST s a

-- | Find index of given key in the hashtable.
lookupIndex :: (Hashable k, Eq k) => HashTable s k v -> k -> ST s (Maybe Word)

-- | Find the next entry in the hashtable starting at the given index.
nextByIndex :: HashTable s k v -> Word -> ST s (Maybe (Word, k, v))
instance Data.HashTable.Class.HashTable Data.HashTable.ST.Cuckoo.HashTable
instance GHC.Internal.Show.Show (Data.HashTable.ST.Cuckoo.HashTable s k v)

-- | An implementation of linear hash tables. (See
--   http://en.wikipedia.org/wiki/Linear_hashing). Use this hash
--   table if you...
--   
--   
--   
- don't care that inserts and lookups are slower than the other hash
--   table implementations in this collection (this one is slightly faster
--   than Data.HashTable from the base library in most cases)
--   
- have a soft real-time or interactive application for which the
--   risk of introducing a long pause on insert while all of the keys are
--   rehashed is unacceptable.
--   
--   
--   Details:
--   
--   Linear hashing allows for the expansion of the hash table one slot at
--   a time, by moving a "split" pointer across an array of pointers to
--   buckets. The number of buckets is always a power of two, and the
--   bucket to look in is defined as:
--   
--   
--   bucket(level,key) = hash(key) mod (2^level)
--   
--   
--   The "split pointer" controls the expansion of the hash table. If the
--   hash table is at level k (i.e. 2^k buckets have been
--   allocated), we first calculate b=bucket(level-1,key). If
--   b < splitptr, the destination bucket is calculated as
--   b'=bucket(level,key), otherwise the original value b
--   is used.
--   
--   The split pointer is incremented once an insert causes some bucket to
--   become fuller than some predetermined threshold; the bucket at the
--   split pointer (*not* the bucket which triggered the split!) is then
--   rehashed, and half of its keys can be expected to be rehashed into the
--   upper half of the table.
--   
--   When the split pointer reaches the middle of the bucket array, the
--   size of the bucket array is doubled, the level increases, and the
--   split pointer is reset to zero.
--   
--   Linear hashing, although not quite as fast for inserts or lookups as
--   the implementation of linear probing included in this package, is well
--   suited for interactive applications because it has much better worst
--   case behaviour on inserts. Other hash table implementations can suffer
--   from long pauses, because it is occasionally necessary to rehash all
--   of the keys when the table grows. Linear hashing, on the other hand,
--   only ever rehashes a bounded (effectively constant) number of keys
--   when an insert forces a bucket split.
--   
--   Space overhead: experimental results
--   
--   In randomized testing (see
--   test/compute-overhead/ComputeOverhead.hs in the source
--   distribution), mean overhead is approximately 1.51 machine words per
--   key-value mapping with a very low standard deviation of about 0.06
--   words, 1.60 words per mapping at the 95th percentile.
--   
--   Unsafe tricks
--   
--   Then the unsafe-tricks flag is on when this package is built
--   (and it is on by default), we use some unsafe tricks (namely
--   unsafeCoerce# and reallyUnsafePtrEquality#) to save
--   indirections in this table. These techniques rely on assumptions about
--   the behaviour of the GHC runtime system and, although they've been
--   tested and should be safe under normal conditions, are slightly
--   dangerous. Caveat emptor. In particular, these techniques are
--   incompatible with HPC code coverage reports.
--   
--   References:
--   
--   
--   
- W. Litwin. Linear hashing: a new tool for file and table
--   addressing. In Proc. 6th International Conference on Very Large
--   Data Bases, Volume 6, pp. 212-223, 1980.
--   
- P-A. Larson. Dynamic hash tables. Communications of the ACM
--   31: 446-457, 1988.
--   
module Data.HashTable.ST.Linear

-- | A linear hash table.
data HashTable s k v

-- | See the documentation for this function in
--   Data.HashTable.Class#v:new.
new :: ST s (HashTable s k v)

-- | See the documentation for this function in
--   Data.HashTable.Class#v:newSized.
newSized :: Int -> ST s (HashTable s k v)

-- | See the documentation for this function in
--   Data.HashTable.Class#v:delete.
delete :: (Hashable k, Eq k) => HashTable s k v -> k -> ST s ()

-- | See the documentation for this function in
--   Data.HashTable.Class#v:lookup.
lookup :: (Eq k, Hashable k) => HashTable s k v -> k -> ST s (Maybe v)

-- | See the documentation for this function in
--   Data.HashTable.Class#v:insert.
insert :: (Eq k, Hashable k) => HashTable s k v -> k -> v -> ST s ()
mutate :: (Eq k, Hashable k) => HashTable s k v -> k -> (Maybe v -> (Maybe v, a)) -> ST s a
mutateST :: (Eq k, Hashable k) => HashTable s k v -> k -> (Maybe v -> ST s (Maybe v, a)) -> ST s a

-- | See the documentation for this function in
--   Data.HashTable.Class#v:mapM_.
mapM_ :: ((k, v) -> ST s b) -> HashTable s k v -> ST s ()

-- | See the documentation for this function in
--   Data.HashTable.Class#v:foldM.
foldM :: (a -> (k, v) -> ST s a) -> a -> HashTable s k v -> ST s a

-- | See the documentation for this function in
--   Data.HashTable.Class#v:computeOverhead.
computeOverhead :: HashTable s k v -> ST s Double
instance Data.HashTable.Class.HashTable Data.HashTable.ST.Linear.HashTable
instance GHC.Internal.Show.Show (Data.HashTable.ST.Linear.HashTable s k v)

-- | This module provides wrappers in IO around the functions from
--   Data.HashTable.Class.
--   
--   This module exports three concrete hash table types, one for each hash
--   table implementation in this package:
--   
--   
--   type BasicHashTable  k v = IOHashTable (B.HashTable)  k v
--   type CuckooHashTable k v = IOHashTable (Cu.HashTable) k v
--   type LinearHashTable k v = IOHashTable (L.HashTable)  k v
--   
--   
--   The IOHashTable type can be thought of as a wrapper around a
--   concrete hashtable type, which sets the ST monad state type
--   to PrimState IO, a.k.a. RealWorld:
--   
--   
--   type IOHashTable tabletype k v = tabletype (PrimState IO) k v
--   
--   
--   This module provides stToIO wrappers around the hashtable
--   functions (which are in ST) to make it convenient to use them
--   in IO. It is intended to be imported qualified and used with a
--   user-defined type alias, i.e.:
--   
--   
--   import qualified Data.HashTable.IO as H
--   
--   type HashTable k v = H.CuckooHashTable k v
--   
--   foo :: IO (HashTable Int Int)
--   foo = do
--       ht <- H.new
--       H.insert ht 1 1
--       return ht
--   
--   
--   Essentially, anywhere you see IOHashTable h k v in the
--   type signatures below, you can plug in any of
--   BasicHashTable k v, CuckooHashTable k
--   v, or LinearHashTable k v.
module Data.HashTable.IO

-- | A type alias for a basic open addressing hash table using linear
--   probing. See Data.HashTable.ST.Basic.
type BasicHashTable k v = IOHashTable HashTable k v

-- | A type alias for the cuckoo hash table. See
--   Data.HashTable.ST.Cuckoo.
type CuckooHashTable k v = IOHashTable HashTable k v

-- | A type alias for the linear hash table. See
--   Data.HashTable.ST.Linear.
type LinearHashTable k v = IOHashTable HashTable k v

-- | A type alias for our hash tables, which run in ST, to set the
--   state token type to PrimState IO (aka
--   RealWorld) so that we can use them in IO.
type IOHashTable (tabletype :: Type -> Type -> Type -> Type) k v = tabletype PrimState IO k v

-- | See the documentation for this function in new.
new :: HashTable h => IO (IOHashTable h k v)

-- | See the documentation for this function in newSized.
newSized :: HashTable h => Int -> IO (IOHashTable h k v)

-- | See the documentation for this function in insert.
insert :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> v -> IO ()

-- | See the documentation for this function in delete.
delete :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> IO ()

-- | See the documentation for this function in lookup.
lookup :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> IO (Maybe v)

-- | See the documentation for this function in mutate.
mutate :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> (Maybe v -> (Maybe v, a)) -> IO a

-- | See the documentation for this function in mutateST.
mutateIO :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> (Maybe v -> IO (Maybe v, a)) -> IO a

-- | See the documentation for this function in fromList.
fromList :: (HashTable h, Eq k, Hashable k) => [(k, v)] -> IO (IOHashTable h k v)

-- | See the documentation for this function in
--   fromListWithSizeHint.
fromListWithSizeHint :: (HashTable h, Eq k, Hashable k) => Int -> [(k, v)] -> IO (IOHashTable h k v)

-- | See the documentation for this function in toList.
toList :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> IO [(k, v)]

-- | See the documentation for this function in mapM_.
mapM_ :: HashTable h => ((k, v) -> IO a) -> IOHashTable h k v -> IO ()

-- | See the documentation for this function in foldM.
foldM :: HashTable h => (a -> (k, v) -> IO a) -> a -> IOHashTable h k v -> IO a

-- | See the documentation for this function in computeOverhead.
computeOverhead :: HashTable h => IOHashTable h k v -> IO Double

-- | See the documentation for this function in lookupIndex.
lookupIndex :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> k -> IO (Maybe Word)

-- | See the documentation for this function in nextByIndex.
nextByIndex :: (HashTable h, Eq k, Hashable k) => IOHashTable h k v -> Word -> IO (Maybe (Word, k, v))
