Data.Vector.Hashtables

Single-element mutable array of Dictionary_ with primitive state token parameterized with state, keys and values types.

Different flavors of MVector could be used for keys and values. It's preferable to use Data.Vector.Unboxed.Mutable or Data.Vector.Storable.Mutable if possible. Otherwise, if you must use boxed vectors, consider employing strict ones from strict-containers to eliminate potential accumulation of thunks.

Example

>>> import qualified Data.Vector.Storable.Mutable as VM>>> import qualified Data.Vector.Unboxed.Mutable  as UM>>> import Data.Vector.Hashtables>>> type HashTable k v = Dictionary (PrimState IO) VM.MVector k UM.MVector v

Represents immutable dictionary as collection of immutable arrays and vectors. See unsafeFreeze and unsafeThaw for conversions from/to mutable dictionary.

O(1) in the best case, O(n) in the worst case. Find dictionary entry by given key in immutable FrozenDictionary. If entry not found -1 returned.

O(1) Dictionary with given capacity.

Create a copy of mutable dictionary.

O(1) Return True if dictionary is empty, False otherwise.

O(1) Return the number of non-empty entries of dictionary. Synonym of length.

O(n) Retrieve list of keys from Dictionary.

O(n) Retrieve list of values from Dictionary.

O(1) in the best case, O(n) in the worst case. Find value by given key in Dictionary. Like lookup' but return Nothing if value not found.

O(1) in the best case, O(n) in the worst case. Find value by given key in Dictionary. Throws an error if value not found.

O(1) in the best case, O(n) in the worst case. Insert key and value in dictionary by key's hash. If entry with given key found value will be replaced.

O(1) in the best case, O(n) in the worst case. Delete entry from Dictionary by given key.

O(1) in the best case, O(n) in the worst case. The expression (upsert ht f k) updates or inserts the value x at k.

It's a responsibility of MVector vs to force evaluation of the updated value. Unboxed / storable vectors do it automatically. If you use boxed vectors, consider employing strict ones from strict-containers to eliminate potential accumulation of thunks.

let f _ = "c"
ht <- fromList [(5,"a"), (3,"b")]
upsert ht f 7
toList ht
[(3, "b"), (5, "a"), (7, "c")]

ht <- fromList [(5,"a"), (3,"b")]
upsert ht f 5
toList ht
[(3, "b"), (5, "c")]

O(1) in the best case, O(n) in the worst case. The expression (alter ht f k) alters the value x at k, or absence thereof. alter can be used to insert, delete, or update a value in a Dictionary.

It's a responsibility of MVector vs to force evaluation of the updated value. Unboxed / storable vectors do it automatically. If you use boxed vectors, consider employing strict ones from strict-containers to eliminate potential accumulation of thunks.

let f _ = Nothing
ht <- fromList [(5,"a"), (3,"b")]
alter ht f 7
toList ht
[(3, "b"), (5, "a")]

ht <- fromList [(5,"a"), (3,"b")]
alter ht f 5
toList ht
[(3 "b")]

let f _ = Just "c"
ht <- fromList [(5,"a"), (3,"b")]
alter ht f 7
toList ht
[(3, "b"), (5, "a"), (7, "c")]

ht <- fromList [(5,"a"), (3,"b")]
alter ht f 5
toList ht
[(3, "b"), (5, "c")]

O(1) in the best case, O(n) in the worst case. The expression (alterM ht f k) alters the value x at k, or absence thereof. alterM can be used to insert, delete, or update a value in a Dictionary in the same PrimMonad m.

O(1) in the best case, O(n) in the worst case. Find dictionary entry by given key. If entry not found -1 returned.

O(min n m) in the best case, O(min n m * max n m) in the worst case. The union of two maps. If a key occurs in both maps, the mapping from the first will be the mapping in the result.

O(min n m) in the best case, O(min n m * max n m) in the worst case. The union of two maps. The provided function (first argument) will be used to compute the result.

O(min n m) in the best case, O(min n m * max n m) in the worst case. The union of two maps. If a key occurs in both maps, the provided function (first argument) will be used to compute the result.

O(n) in the best case, O(n * m) in the worst case. Difference of two tables. Return elements of the first table not existing in the second.

O(n) in the best case, O(n * m) in the worst case. Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns Nothing, the element is discarded (proper set difference). If it returns (Just y), the element is updated with a new value y.

O(n) in the best case, O(n * m) in the worst case. Intersection of two maps. Return elements of the first map for keys existing in the second.

Intersection of two maps. If a key occurs in both maps the provided function is used to combine the values from the two maps.

Intersection of two maps. If a key occurs in both maps the provided function is used to combine the values from the two maps.

O(1) Unsafe convert a mutable dictionary to an immutable one without copying. The mutable dictionary may not be used after this operation.

O(1) Unsafely convert immutable FrozenDictionary to a mutable Dictionary without copying. The immutable dictionary may not be used after this operation.

O(n) Convert list to a Dictionary.

O(n) Convert Dictionary to a list.

Represents collection of hashtable internal primitive arrays and vectors.

• hash codes,

• references to the next element,

• buckets,

• keys

• and values.

O(1) in the best case, O(n) in the worst case. Same as findEntry, but for Dictionary_.

Class of monads which can perform primitive state-transformer actions.

RealWorld is deeply magical. It is primitive, but it is not unlifted (hence ptrArg). We never manipulate values of type RealWorld; it's only used in the type system, to parameterise State#.

State token type.

Class of primitive monads for state-transformer actions.

Unlike PrimMonad, this typeclass requires that the Monad be fully expressed as a state transformer, therefore disallowing other monad transformers on top of the base IO or ST.

Variant of keepAlive in which the value kept alive is of an unlifted boxed type.

Execute a primitive operation with no result.

Keep value x alive until computation k completes. Warning: This primop exists for completeness, but it is difficult to use correctly. Prefer keepAliveUnlifted if the value to keep alive is simply a wrapper around an unlifted type (e.g. ByteArray).

PrimBase's state token type can be annoying to handle in constraints. This typeclass lets users (visually) notice PrimState equality constraints less, by witnessing that s ~ PrimState m.

PrimMonad's state token type can be annoying to handle in constraints. This typeclass lets users (visually) notice PrimState equality constraints less, by witnessing that s ~ PrimState m.

Create an action to force a value; generalizes evaluate

Convert an IO action to a PrimMonad.

Lifts a PrimBase into another PrimMonad with the same underlying state token type.

Convert a PrimBase with a RealWorld state token to IO

Convert a PrimBase to another monad with the same state token.

Convert a PrimBase to ST

Convert an ST action to a PrimMonad.

Ensure that the value is considered alive by the garbage collection. Warning: GHC has optimization passes that can erase touch if it is certain that an exception is thrown afterward. Prefer keepAlive.

Variant of touch that keeps a value of an unlifted type (e.g. MutableByteArray#) alive.

Convert an IO action to any PrimMonad. This operation is highly unsafe!

Generally, do not use this function. It is the same as accursedUnutterablePerformIO from bytestring and is well behaved under narrow conditions. See the documentation of that function to get an idea of when this is sound. In most cases GHC.IO.Unsafe.unsafeDupablePerformIO should be preferred.

See unsafeInlineIO. This function is not recommended for the same reasons.

See unsafeInlineIO. This function is not recommended for the same reasons. Prefer runST when s is free.

Convert any PrimBase to IO. This operation is highly unsafe!

Convert a PrimBase to another monad with a possibly different state token. This operation is highly unsafe!

Convert any PrimBase to ST with an arbitrary state token. This operation is highly unsafe!

Convert an ST action with an arbitrary state token to any PrimMonad. This operation is highly unsafe!