Modulelinear-base-0.4.0Haskell2010

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.

2 types
20 values

Packagelinear-base-0.4.0
Exports22
LanguageHaskell2010
LicenceMIT
SourceLinear.hs

A mutable hashmap

2 declarations

datadata HashMap k v where

A mutable hashmap with a linear interface.

Instances5Functor, Consumable, Dupable, Semigroup

Functor (HashMap k)Defined in linear-base-0.4.0 · Data.HashMap.Mutable.Linear.Internal
Semigroup (HashMap k v)Defined in linear-base-0.4.0 · Data.HashMap.Mutable.Linear.Internal
Consumable (HashMap k v)Defined in linear-base-0.4.0 · Data.HashMap.Mutable.Linear.Internal
Dupable (HashMap k v)Defined in linear-base-0.4.0 · Data.HashMap.Mutable.Linear.Internal
Keyed k => Semigroup (HashMap k v)Defined in linear-base-0.4.0 · Data.HashMap.Mutable.Linear.Internal

typetype Keyed k = (Eq k, Hashable k)

At minimum, we need to store hashable and identifiable keys

Constructors

2 declarations

valueempty :: Keyed k => Int -> (HashMap k v %1 -> Ur b) %1 -> Ur b

Run a computation with an empty HashMap with given capacity.

valuefromList :: 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

10 declarations

valueinsert :: 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.

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

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

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

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

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

Complexity: O(capacity hm)

valuefilterWithKey

:: Keyed k
=> k -> v -> Bool
-> HashMap k v
-> HashMap k v

Complexity: O(capacity hm)

valuemapMaybe :: 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)

valuemapMaybeWithKey

:: Keyed k
=> k -> v -> Maybe v'
-> HashMap k v
-> HashMap k v'

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

valueshrinkToFit :: 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)

valuealter

:: Keyed k
=> Maybe v -> Maybe v
-> k
-> HashMap k v
-> 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.

valuealterF

:: (Keyed k, Functor f)
=> Maybe v -> f (Ur (Maybe v))
-> k
-> HashMap k v
-> 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

5 declarations

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

Number of key-value pairs inside the HashMap

valuecapacity :: 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.

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

Look up a value from a HashMap.

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

Check if the given key exists.

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

Converts a HashMap to a lazy list.

Combining maps

3 declarations

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

A right-biased union.

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

valueunionWith

:: Keyed k
=> v -> v -> v
-> HashMap k v
-> HashMap k v
-> HashMap k v

Union of two maps using the provided function on conflicts.

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

valueintersectionWith

:: Keyed k
=> a -> b -> c
-> HashMap k a
-> HashMap k b
-> HashMap k c

Intersection of two maps with the provided combine function.

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