typerep-map-0.1.0: Efficient implementation of a dependent map with types as keys

Safe HaskellNone
LanguageHaskell2010

Data.TMap

Contents

Description

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.

Synopsis

Map type

type TMap = TypeRepMap Identity Source #

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

Construction

empty :: TMap Source #

A TMap with no values stored in it.

size empty == 0
member @a empty == False

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

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 Source #

Insert a value into a TMap.

size (insert v tm) >= size tm
member @a (insert (x :: a) tm) == True

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

Delete a value from a TMap.

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. x -> x -> x) -> TMap -> TMap -> TMap Source #

The union of two TMaps using a combining function.

union :: TMap -> TMap -> TMap Source #

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

Query

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

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 Source #

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 Source #

Get the amount of elements in a TMap.