Data.TMap

TMap is a heterogeneous data structure similar in its essence to Map with types as keys, where each value has the type of its key.

Here is an example of a TMap with a comparison to Map:

 Map String String             TMap
--------------------     -----------------
 "Int"  -> "5"             Int  -> 5
 "Bool" -> "True"          Bool -> True
 "Char" -> "'x'"           Char -> 'x'

The runtime representation of TMap is an array, not a tree. This makes lookup significantly more efficient.

Map type

type TMap = TypeRepMap Identity

TMap is a special case of TypeRepMap when the interpretation is Identity.

Construction

empty :: TMap

A TMap with no values stored in it.

size empty == 0

member @a empty == False

one :: forall a. Typeable a => a -> TMap

Construct a TMap with a single element.

size (one x) == 1

member @a (one (x :: a)) == True

Modification

insert :: forall a. Typeable a => a -> TMap -> TMap

Insert a value into a TMap. TMap optimizes for fast reads rather than inserts, as a trade-off inserts are O(n).

size (insert v tm) >= size tm

member @a (insert (x :: a) tm) == True

delete :: forall a. Typeable a => TMap -> TMap

Delete a value from a TMap.

TMap optimizes for fast reads rather than modifications, as a trade-off deletes are O(n), with an O(log(n)) optimization for when the element is already missing.

size (delete @a tm) <= size tm

member @a (delete @a tm) == False

>>> tm = delete @Bool $ insert True $ one 'a'
>>> size tm
1
>>> member @Bool tm
False
>>> member @Char tm
True

unionWith :: (forall x. Typeable x => x -> x -> x) -> TMap -> TMap -> TMap

The union of two TMaps using a combining function.

union :: TMap -> TMap -> TMap

The (left-biased) union of two TMaps. It prefers the first map when duplicate keys are encountered, i.e. union == unionWith const.

intersectionWith :: (forall x. Typeable x => x -> x -> x) -> TMap -> TMap -> TMap

The intersection of two TMaps using a combining function.

O(n + m)

intersection :: TMap -> TMap -> TMap

The intersection of two TMaps. It keeps all values from the first map whose keys are present in the second.

O(n + m)

map :: (forall a. Typeable a => a -> a) -> TMap -> TMap

Map a function over the values.

adjust :: Typeable a => (a -> a) -> TMap -> TMap

Update a value with the result of the provided function.

alter :: Typeable a => (Maybe a -> Maybe a) -> TMap -> TMap

Updates a value at a specific key, whether or not it exists. This can be used to insert, delete, or update a value of a given type in the map.

Query

lookup :: forall a. Typeable a => TMap -> Maybe a

Lookup a value of the given type in a TMap.

>>> x = lookup $ insert (11 :: Int) empty
>>> x :: Maybe Int
Just 11
>>> x :: Maybe ()
Nothing

member :: forall a. Typeable a => TMap -> Bool

Check if a value of the given type is present in a TMap.

>>> member @Char $ one 'a'
True
>>> member @Bool $ one 'a'
False

size :: TMap -> Int

Get the amount of elements in a TMap.

keys :: TMap -> [SomeTypeRep]

Returns the list of SomeTypeReps from keys.

keysWith :: (forall a. TypeRep a -> r) -> TMap -> [r]

Return the list of keys by wrapping them with a user-provided function.

toListWith :: (forall a. Typeable a => a -> r) -> TMap -> [r]

Return the list of key-value pairs by wrapping them with a user-provided function.