vector-hashtables-0.1.2.1: Efficient vector-based mutable hashtables implementation.

Copyright | (c) klapaucius swamp_agr 2016-2021
License | BSD3
Safe Haskell | None
Language | Haskell2010

Data.Vector.Hashtables

Contents

- Documentation
  - Usage
  - Types
  - Construction
  - Basic interface
  - Combine
    - Union
    - Difference
    - Intersection
  - Conversions
    - Mutable
    - List
  - Low-level interface

Description

Synopsis

- newtype Dictionary s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v = DRef {
  - getDRef :: MutVar s (Dictionary_ s ks k vs v)
  }
- data FrozenDictionary (ks :: Type -> Type) k (vs :: Type -> Type) v = FrozenDictionary {
  - fhashCode :: !(PrimArray Int)
  - fnext :: !(PrimArray Int)
  - fbuckets :: !(PrimArray Int)
  - count :: !Int
  - freeList :: !Int
  - freeCount :: !Int
  - fkey :: !(ks k)
  - fvalue :: !(vs v)
  - fremSize :: !FastRem
  }
- findElem :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v. (Vector ks k, Vector vs v, Hashable k, Eq k) => FrozenDictionary ks k vs v -> k -> Int
- initialize :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Int -> m (Dictionary (PrimState m) ks k vs v)
- clone :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- null :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Bool
- size :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int
- keys :: forall ks k m (vs :: Type -> Type -> Type) v. (Vector ks k, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k)
- values :: forall vs v m (ks :: Type -> Type -> Type) k. (Vector vs v, PrimMonad m) => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v)
- lookup :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v)
- lookup' :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v
- insert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> v -> m ()
- delete :: forall k (ks :: Type -> Type -> Type) (vs :: Type -> Type -> Type) v m. (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Dictionary (PrimState m) ks k vs v -> k -> m ()
- upsert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m ()
- alter :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> Maybe v) -> k -> m ()
- alterM :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> m (Maybe v)) -> k -> m ()
- findEntry :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Int
- union :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- unionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- unionWithKey :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (k -> v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v)
- difference :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)
- differenceWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => (v -> w -> Maybe v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)
- intersection :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v)
- intersectionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)
- intersectionWithKey :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (k -> v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3)
- unsafeFreeze :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v -> m (FrozenDictionary ks k vs v)
- unsafeThaw :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => FrozenDictionary ks k vs v -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v)
- fromList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v)
- toList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> m [(k, v)]
- data Dictionary_ s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v = Dictionary {
  - hashCode :: !(IntArray s)
  - next :: !(IntArray s)
  - buckets :: !(IntArray s)
  - refs :: !(IntArray s)
  - key :: !(ks s k)
  - value :: !(vs s v)
  - remSize :: !FastRem
  }
- findEntry_ :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> k -> m Int
- module Control.Monad.Primitive

# Documentation

- This package provides hashtable implementation similar to .NET Generic Dictionary implementation (at the time of 2015) https://github.com/dotnet/coreclr/blob/3a0d638843472056c0cbb723beaed0b1152ca36d/src/mscorlib/src/System/Collections/Generic/Dictionary.cs.
- It was originated as response to https://comp.lang.functional.narkive.com/uYVjkKfl/f-vs-ocaml-vs-python-vs-haskell-hash-table-performance#post5.
- For more hashtables implementations see https://rcoh.me/posts/hash-map-analysis/.

## Usage

    >>> 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
    >>> ht <- initialize 0 :: IO (HashTable Int Int)
    >>> insert ht 0 1

## Types

newtype Dictionary s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v Source #

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

Constructors

DRef |

Fields

- getDRef :: MutVar s (Dictionary_ s ks k vs v)

data FrozenDictionary (ks :: Type -> Type) k (vs :: Type -> Type) v Source #

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

Constructors

FrozenDictionary |

Fields

- fhashCode :: !(PrimArray Int)
- fnext :: !(PrimArray Int)
- fbuckets :: !(PrimArray Int)
- count :: !Int
- freeList :: !Int
- freeCount :: !Int
- fkey :: !(ks k)
- fvalue :: !(vs v)
- fremSize :: !FastRem

#### Instances

Instances details

(Show (ks k), Show (vs v)) => Show (FrozenDictionary ks k vs v) Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods showsPrec :: Int -> FrozenDictionary ks k vs v -> ShowS Source # show :: FrozenDictionary ks k vs v -> String Source # showList :: [FrozenDictionary ks k vs v] -> ShowS Source #
(Eq (ks k), Eq (vs v)) => Eq (FrozenDictionary ks k vs v) Source # |
Instance details Defined in Data.Vector.Hashtables.Internal Methods (==) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source # (/=) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #
(Ord (ks k), Ord (vs v)) => Ord (FrozenDictionary ks k vs v) Source # |

Instance details

Defined in Data.Vector.Hashtables.Internal

Methods

compare :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Ordering Source #

(<) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

(<=) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

(>) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

(>=) :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> Bool Source #

max :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v Source #

min :: FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v -> FrozenDictionary ks k vs v Source #

findElem :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v. (Vector ks k, Vector vs v, Hashable k, Eq k) => FrozenDictionary ks k vs v -> k -> Int Source #

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.

## Construction

initialize :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Int -> m (Dictionary (PrimState m) ks k vs v) Source #

O(1) Dictionary with given capacity.

clone :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

Create a copy of mutable dictionary.

## Basic interface

null :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Bool Source #

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

size :: forall (ks :: Type -> Type -> Type) k m (vs :: Type -> Type -> Type) v. (MVector ks k, PrimMonad m) => Dictionary (PrimState m) ks k vs v -> m Int Source #

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

keys :: forall ks k m (vs :: Type -> Type -> Type) v. (Vector ks k, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k vs v -> m (ks k) Source #

O(n) Retrieve list of keys from `Dictionary`.

values :: forall vs v m (ks :: Type -> Type -> Type) k. (Vector vs v, PrimMonad m) => Dictionary (PrimState m) ks k (Mutable vs) v -> m (vs v) Source #

O(n) Retrieve list of values from `Dictionary`.

lookup :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m (Maybe v) Source #

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.

lookup' :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m v Source #

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.

insert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> v -> m () Source #

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.

delete :: forall k (ks :: Type -> Type -> Type) (vs :: Type -> Type -> Type) v m. (Eq k, MVector ks k, MVector vs v, Hashable k, PrimMonad m, DeleteEntry ks, DeleteEntry vs) => Dictionary (PrimState m) ks k vs v -> k -> m () Source #

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

upsert :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> v) -> k -> m () Source #

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")]

alter :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> Maybe v) -> k -> m () Source #

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")]

alterM :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, DeleteEntry ks, DeleteEntry vs, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> (Maybe v -> m (Maybe v)) -> k -> m () Source #

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`.

findEntry :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> k -> m Int Source #

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

## Combine

### Union

union :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

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.

unionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

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.

unionWithKey :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => (k -> v -> v -> v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs v -> m (Dictionary (PrimState m) ks k vs v) Source #

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.

### Difference

difference :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v) Source #

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.

differenceWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => (v -> w -> Maybe v) -> Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v) Source #

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`.

### Intersection

intersection :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v w m. (MVector ks k, MVector vs v, MVector vs w, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> Dictionary (PrimState m) ks k vs w -> m (Dictionary (PrimState m) ks k vs v) Source #

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.

intersectionWith :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3) Source #

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 :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v1 v2 v3 m. (MVector ks k, MVector vs v1, MVector vs v2, MVector vs v3, PrimMonad m, Hashable k, Eq k) => (k -> v1 -> v2 -> v3) -> Dictionary (PrimState m) ks k vs v1 -> Dictionary (PrimState m) ks k vs v2 -> m (Dictionary (PrimState m) ks k vs v3) Source #

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

## Conversions

### Mutable

unsafeFreeze :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v -> m (FrozenDictionary ks k vs v) Source #

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

unsafeThaw :: forall (ks :: Type -> Type) k (vs :: Type -> Type) v m. (Vector ks k, Vector vs v, PrimMonad m) => FrozenDictionary ks k vs v -> m (Dictionary (PrimState m) (Mutable ks) k (Mutable vs) v) Source #

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

### List

fromList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => [(k, v)] -> m (Dictionary (PrimState m) ks k vs v) Source #

O(n) Convert list to a `Dictionary`.

toList :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary (PrimState m) ks k vs v -> m [(k, v)] Source #

O(n) Convert `Dictionary` to a list.

## Low-level interface

data Dictionary_ s (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v Source #

Represents collection of hashtable internal primitive arrays and vectors.

- hash codes,
- references to the next element,
- buckets,
- keys
- and values.

Constructors

Dictionary |

Fields

- hashCode :: !(IntArray s)
- next :: !(IntArray s)
- buckets :: !(IntArray s)
- refs :: !(IntArray s)
- key :: !(ks s k)
- value :: !(vs s v)
- remSize :: !FastRem

findEntry_ :: forall (ks :: Type -> Type -> Type) k (vs :: Type -> Type -> Type) v m. (MVector ks k, MVector vs v, PrimMonad m, Hashable k, Eq k) => Dictionary_ (PrimState m) ks k vs v -> k -> m Int Source #

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

module Control.Monad.Primitive