Data.TypeRepMap.Internal

Internal API for TypeRepMap and operations on it. The functions here do not have any stability guarantees and can change between minor versions.

If you need to use this module for purposes other than tests, create an issue.

Documentation

data TypeRepMap (f :: k -> Type)

TypeRepMap is a heterogeneous data structure similar in its essence to Map with types as keys, where each value has the type of its key. In addition to that, each value is wrapped in an interpretation f.

Here is an example of using Maybe as an interpretation, with a comparison to Map:

 Map String (Maybe String)          TypeRepMap Maybe
---------------------------       ---------------------
 "Int"  -> Just "5"                 Int  -> Just 5
 "Bool" -> Just "True"              Bool -> Just True
 "Char" -> Nothing                  Char -> Nothing

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

Constructors

TypeRepMap

an unsafe constructor for TypeRepMap

Fields

• fingerprintAs :: !(PrimArray Word64)

  first components of key fingerprints

• fingerprintBs :: !(PrimArray Word64)

  second components of key fingerprints

• trAnys :: !(Array Any)

  values stored in the map

• trKeys :: !(Array Any)

  typerep keys

Instances

IsList (TypeRepMap f)

fromList . toList == 'id'

Creates TypeRepMap from a list of WrapTypeables.

>>> show $ fromList [WrapTypeable $ Identity True, WrapTypeable $ Identity 'a']
TypeRepMap [Bool, Char]

Defined in Data.TypeRepMap.Internal

Associated Types

type Item (TypeRepMap f)

Methods

fromList :: [Item (TypeRepMap f)] -> TypeRepMap f

fromListN :: Int -> [Item (TypeRepMap f)] -> TypeRepMap f

toList :: TypeRepMap f -> [Item (TypeRepMap f)]

(forall (a :: k). Typeable a => Eq (f a)) => Eq (TypeRepMap f)

Defined in Data.TypeRepMap.Internal

Methods

(==) :: TypeRepMap f -> TypeRepMap f -> Bool

(/=) :: TypeRepMap f -> TypeRepMap f -> Bool

Show (TypeRepMap f)

Shows only keys.

Defined in Data.TypeRepMap.Internal

Methods

showsPrec :: Int -> TypeRepMap f -> ShowS

show :: TypeRepMap f -> String

showList :: [TypeRepMap f] -> ShowS

Semigroup (TypeRepMap f)

Uses union to combine TypeRepMaps.

Defined in Data.TypeRepMap.Internal

Methods

(<>) :: TypeRepMap f -> TypeRepMap f -> TypeRepMap f

sconcat :: NonEmpty (TypeRepMap f) -> TypeRepMap f

stimes :: Integral b => b -> TypeRepMap f -> TypeRepMap f

Monoid (TypeRepMap f)

Defined in Data.TypeRepMap.Internal

Methods

mempty :: TypeRepMap f

mappend :: TypeRepMap f -> TypeRepMap f -> TypeRepMap f

mconcat :: [TypeRepMap f] -> TypeRepMap f

NFData (TypeRepMap f)

Defined in Data.TypeRepMap.Internal

Methods

rnf :: TypeRepMap f -> ()

type Item (TypeRepMap f)

Defined in Data.TypeRepMap.Internal

type Item (TypeRepMap f) = WrapTypeable f

toFingerprints :: TypeRepMap f -> [Fingerprint]

Returns the list of Fingerprints from TypeRepMap.

empty :: TypeRepMap f

A TypeRepMap with no values stored in it.

size empty == 0

member @a empty == False

one :: forall a f. Typeable a => f a -> TypeRepMap f

Construct a TypeRepMap with a single element.

size (one x) == 1

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

insert :: forall a f. Typeable a => f a -> TypeRepMap f -> TypeRepMap f

Insert a value into a TypeRepMap. TypeRepMap 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 :: f a) tm) == True

type KindOf (a :: k) = k

type ArgKindOf (f :: k -> l) = k

delete :: forall a (f :: KindOf a -> Type). Typeable a => TypeRepMap f -> TypeRepMap f

Delete a value from a TypeRepMap.

TypeRepMap 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 (Just True) $ one (Just 'a')
>>> size tm
1
>>> member @Bool tm
False
>>> member @Char tm
True

deleteFirst :: (a -> Bool) -> [a] -> [a]

adjust :: forall a f. Typeable a => (f a -> f a) -> TypeRepMap f -> TypeRepMap f

Update a value at a specific key with the result of the provided function. When the key is not a member of the map, the original map is returned.

>>> trmap = fromList @(TypeRepMap Identity) [WrapTypeable $ Identity "a"]
>>> lookup @String $ adjust (fmap (++ "ww")) trmap
Just (Identity "aww")

alter :: forall a f. Typeable a => (Maybe (f a) -> Maybe (f a)) -> TypeRepMap f -> TypeRepMap f

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.

>>> func = (\case Nothing -> Just (Identity "new"); Just (Identity s) -> Just (Identity (reverse s)))
>>> lookup @String $ alter func empty
Just (Identity "new")
>>> trmap = fromList @(TypeRepMap Identity) [WrapTypeable $ Identity "helllo"]
>>> lookup @String $ alter func trmap
>>> Just (Identity "olleh")

hoist :: (forall x. f x -> g x) -> TypeRepMap f -> TypeRepMap g

Map over the elements of a TypeRepMap.

>>> tm = insert (Identity True) $ one (Identity 'a')
>>> lookup @Bool tm
Just (Identity True)
>>> lookup @Char tm
Just (Identity 'a')
>>> tm2 = hoist ((:[]) . runIdentity) tm
>>> lookup @Bool tm2
Just [True]
>>> lookup @Char tm2
Just "a"

hoistA :: Applicative t => (forall x. f x -> t (g x)) -> TypeRepMap f -> t (TypeRepMap g)

hoistWithKey :: forall f g. (forall x. Typeable x => f x -> g x) -> TypeRepMap f -> TypeRepMap g

unionWith :: forall f. (forall x. Typeable x => f x -> f x -> f x) -> TypeRepMap f -> TypeRepMap f -> TypeRepMap f

The union of two TypeRepMaps using a combining function for conflicting entries. O(n + m)

union :: TypeRepMap f -> TypeRepMap f -> TypeRepMap f

The (left-biased) union of two TypeRepMaps in O(n + m). It prefers the first map when duplicate keys are encountered, i.e. union == unionWith const.

intersectionWith :: forall f. (forall x. Typeable x => f x -> f x -> f x) -> TypeRepMap f -> TypeRepMap f -> TypeRepMap f

The intersection of two TypeRepMaps using a combining function

O(n + m)

intersection :: TypeRepMap f -> TypeRepMap f -> TypeRepMap f

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

O(n + m)

member :: forall a (f :: KindOf a -> Type). Typeable a => TypeRepMap f -> Bool

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

>>> member @Char $ one (Identity 'a')
True
>>> member @Bool $ one (Identity 'a')
False

lookup :: forall a f. Typeable a => TypeRepMap f -> Maybe (f a)

Lookup a value of the given type in a TypeRepMap.

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

size :: TypeRepMap f -> Int

Get the amount of elements in a TypeRepMap.

keys :: TypeRepMap f -> [SomeTypeRep]

Return the list of SomeTypeRep from the keys.

keysWith :: (forall (a :: ArgKindOf f). TypeRep a -> r) -> TypeRepMap f -> [r]

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

toListWith :: forall f r. (forall (a :: ArgKindOf f). Typeable a => f a -> r) -> TypeRepMap f -> [r]

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

cachedBinarySearch :: Fingerprint -> PrimArray Word64 -> PrimArray Word64 -> Maybe Int

Binary searched based on this article http://bannalia.blogspot.com/2015/06/cache-friendly-binary-search.html with modification for our two-vector search case.

toAny :: f a -> Any

fromAny :: Any -> f a

anyToTypeRep :: Any -> TypeRep f

typeFp :: forall a. Typeable a => Fingerprint

toTriples :: TypeRepMap f -> [(Fingerprint, Any, Any)]

toSortedTriples :: TypeRepMap f -> [(Fingerprint, Any, Any)]

Efficiently get sorted triples from a map in O(n) time

We assume the incoming TypeRepMap is already sorted into cachedBinarySearch order using fromSortedList. Then we can construct the index mapping from the "cached" ordering into monotonically increasing order using generateOrderMapping with the length of the TRM. This takes O(n). We then pull those indexes from the source TRM to get the sorted triples in a total of O(n).

nubByFst :: Eq a => [(a, b, c)] -> [(a, b, c)]

fst3 :: (a, b, c) -> a

data WrapTypeable f where

Existential wrapper around Typeable indexed by f type parameter. Useful for TypeRepMap structure creation form list of WrapTypeables.

Constructors

WrapTypeable :: Typeable a => f a -> WrapTypeable f

Instances

Show (WrapTypeable f)

Defined in Data.TypeRepMap.Internal

Methods

showsPrec :: Int -> WrapTypeable f -> ShowS

show :: WrapTypeable f -> String

showList :: [WrapTypeable f] -> ShowS

calcFp :: forall a. Typeable a => Fingerprint

fromTriples :: [(Fingerprint, Any, Any)] -> TypeRepMap f

fromSortedTriples :: [(Fingerprint, Any, Any)] -> TypeRepMap f

fromSortedList :: forall a. [a] -> [a]

generateOrderMapping :: Int -> [Int]

invariantCheck :: TypeRepMap f -> Bool

Check that invariant of the structure holds. The structure maintains the following invariant. For each element A at index i:

1. if there is an element B at index 2*i+1, then B < A.
2. if there is an element C at index 2*i+2, then A < C.