Data.HashMap.Mutable.Linear

This module provides mutable hashmaps with a linear interface.

It is implemented with Robin Hood hashing which has amortized constant time lookups and updates.

A mutable hashmap

data HashMap k v

A mutable hashmap with a linear interface.

Instances

Functor (HashMap k)

Defined in Data.HashMap.Mutable.Linear

Methods

fmap :: (a %1 -> b) -> HashMap k a %1 -> HashMap k b

Semigroup (HashMap k v)

Defined in Data.HashMap.Mutable.Linear

Methods

(<>) :: HashMap k v -> HashMap k v -> HashMap k v

sconcat :: NonEmpty (HashMap k v) -> HashMap k v

stimes :: Integral b => b -> HashMap k v -> HashMap k v

Consumable (HashMap k v)

Defined in Data.HashMap.Mutable.Linear

Methods

consume :: HashMap k v %1 -> ()

Keyed k => Semigroup (HashMap k v)

Defined in Data.HashMap.Mutable.Linear

Methods

(<>) :: HashMap k v %1 -> HashMap k v %1 -> HashMap k v

Dupable (HashMap k v)

Defined in Data.HashMap.Mutable.Linear

Methods

dupV :: forall (n :: Nat). KnownNat n => HashMap k v %1 -> V n (HashMap k v)

dup2 :: HashMap k v %1 -> (HashMap k v, HashMap k v)

type Keyed k = (Eq k, Hashable k)

At minimum, we need to store hashable and identifiable keys

Constructors

empty :: forall k v b. Keyed k => Int -> (HashMap k v %1 -> Ur b) %1 -> Ur b

Run a computation with an empty HashMap with given capacity.

fromList :: forall k v b. Keyed k => [(k, v)] -> (HashMap k v %1 -> Ur b) %1 -> Ur b

Run a computation with an HashMap containing given key-value pairs.

Modifiers

insert :: Keyed k => k -> v -> HashMap k v %1 -> HashMap k v

Insert a key value pair to a HashMap. It overwrites the previous value if it exists.

insertAll :: Keyed k => [(k, v)] -> HashMap k v %1 -> HashMap k v

insert (in the provided order) the given key-value pairs to the hashmap.

delete :: Keyed k => k -> HashMap k v %1 -> HashMap k v

Delete a key from a HashMap. Does nothing if the key does not exist.

filter :: Keyed k => (v -> Bool) -> HashMap k v %1 -> HashMap k v

Complexity: O(capacity hm)

filterWithKey :: Keyed k => (k -> v -> Bool) -> HashMap k v %1 -> HashMap k v

Complexity: O(capacity hm)

mapMaybe :: Keyed k => (v -> Maybe v') -> HashMap k v %1 -> HashMap k v'

A version of fmap which can throw out the elements.

Complexity: O(capacity hm)

mapMaybeWithKey :: forall k v v'. Keyed k => (k -> v -> Maybe v') -> HashMap k v %1 -> HashMap k v'

Same as mapMaybe, but also has access to the keys.

shrinkToFit :: Keyed k => HashMap k a %1 -> HashMap k a

Reduce the HashMap capacity to decrease wasted memory. Returns a semantically identical HashMap.

This is only useful after a lot of deletes.

Complexity: O(capacity hm)

alter :: Keyed k => (Maybe v -> Maybe v) -> k -> HashMap k v %1 -> HashMap k v

A general modification function; which can insert, update or delete a value of the key. See alterF, for an even more general function.

alterF :: (Keyed k, Functor f) => (Maybe v -> f (Ur (Maybe v))) -> k -> HashMap k v %1 -> f (HashMap k v)

The most general modification function; which can insert, update or delete a value of the key, while collecting an effect in the form of an arbitrary Functor.

Accessors

size :: HashMap k v %1 -> (Ur Int, HashMap k v)

Number of key-value pairs inside the HashMap

capacity :: HashMap k v %1 -> (Ur Int, HashMap k v)

Maximum number of elements the HashMap can store without resizing. However, for performance reasons, the HashMap might be before full.

Use shrinkToFit to reduce the wasted space.

lookup :: Keyed k => k -> HashMap k v %1 -> (Ur (Maybe v), HashMap k v)

Look up a value from a HashMap.

member :: Keyed k => k -> HashMap k v %1 -> (Ur Bool, HashMap k v)

Check if the given key exists.

toList :: HashMap k v %1 -> Ur [(k, v)]

Converts a HashMap to a lazy list.

Combining maps

union :: Keyed k => HashMap k v %1 -> HashMap k v %1 -> HashMap k v

A right-biased union.

Complexity: O(min(capacity hm1, capacity hm2)

unionWith :: Keyed k => (v -> v -> v) -> HashMap k v %1 -> HashMap k v %1 -> HashMap k v

Union of two maps using the provided function on conflicts.

Complexity: O(min(capacity hm1, capacity hm2)

intersectionWith :: Keyed k => (a -> b -> c) -> HashMap k a %1 -> HashMap k b %1 -> HashMap k c

Intersection of two maps with the provided combine function.

Complexity: O(min(capacity hm1, capacity hm2)