-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Efficient implementation of a dependent map with types as keys
--
-- A dependent map from type representations to values of these types.
--
-- Here is an illustration of such a map:
--
--
-- TMap
-- ---------------
-- Int -> 5
-- Bool -> True
-- Char -> 'x'
--
--
-- In addition to TMap, we provide TypeRepMap
-- parametrized by a vinyl-style interpretation. This data
-- structure is equivalent to DMap TypeRep, but with
-- significantly more efficient lookups.
@package typerep-map
@version 0.3.0
-- | 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.
module Data.TypeRepMap.Internal
-- | 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.
data TypeRepMap (f :: k -> Type)
-- | an unsafe constructor for TypeRepMap
TypeRepMap :: {-# UNPACK #-} !(PrimArray Word64) -> {-# UNPACK #-} !(PrimArray Word64) -> {-# UNPACK #-} !(Array Any) -> {-# UNPACK #-} !(Array Any) -> TypeRepMap
-- | first components of key fingerprints
[fingerprintAs] :: TypeRepMap -> {-# UNPACK #-} !(PrimArray Word64)
-- | second components of key fingerprints
[fingerprintBs] :: TypeRepMap -> {-# UNPACK #-} !(PrimArray Word64)
-- | values stored in the map
[trAnys] :: TypeRepMap -> {-# UNPACK #-} !(Array Any)
-- | typerep keys
[trKeys] :: TypeRepMap -> {-# UNPACK #-} !(Array Any)
-- | Returns the list of Fingerprints from TypeRepMap.
toFingerprints :: TypeRepMap f -> [Fingerprint]
-- | A TypeRepMap with no values stored in it.
--
--
-- size empty == 0
--
--
--
-- member @a empty == False
--
empty :: TypeRepMap f
-- | Construct a TypeRepMap with a single element.
--
--
-- size (one x) == 1
--
--
--
-- member @a (one (x :: f a)) == True
--
one :: forall a f. Typeable a => f a -> TypeRepMap f
-- | Insert a value into a TypeRepMap.
--
--
-- size (insert v tm) >= size tm
--
--
--
-- member @a (insert (x :: f a) tm) == True
--
insert :: forall a f. Typeable a => f a -> TypeRepMap f -> TypeRepMap f
type KindOf (a :: k) = k
-- | Delete a value from a TypeRepMap.
--
--
-- 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
--
delete :: forall a (f :: KindOf a -> Type). Typeable 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")
--
adjust :: forall a f. Typeable a => (f a -> f a) -> TypeRepMap f -> TypeRepMap f
-- | 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"
--
hoist :: (forall x. f x -> g x) -> TypeRepMap f -> TypeRepMap g
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
-- | The union of two TypeRepMaps using a combining function.
unionWith :: (forall x. f x -> f x -> f x) -> TypeRepMap f -> TypeRepMap f -> TypeRepMap f
-- | The (left-biased) union of two TypeRepMaps. It prefers the
-- first map when duplicate keys are encountered, i.e. union
-- == unionWith const.
union :: TypeRepMap f -> TypeRepMap f -> TypeRepMap f
-- | 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
--
member :: forall a (f :: KindOf a -> Type). Typeable a => TypeRepMap f -> Bool
-- | 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
--
lookup :: forall a f. Typeable a => TypeRepMap f -> Maybe (f a)
-- | Get the amount of elements in a TypeRepMap.
size :: TypeRepMap f -> Int
-- | Return the list of SomeTypeRep from the keys.
keys :: TypeRepMap f -> [SomeTypeRep]
-- | 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.
cachedBinarySearch :: Fingerprint -> PrimArray Word64 -> PrimArray Word64 -> Maybe Int
toAny :: f a -> Any
fromAny :: Any -> f a
anyToTypeRep :: Any -> TypeRep f
typeFp :: forall a. Typeable a => Fingerprint
toTriples :: TypeRepMap f -> [(Fingerprint, Any, Any)]
deleteByFst :: Eq a => a -> [(a, b, c)] -> [(a, b, c)]
nubByFst :: (Eq a) => [(a, b, c)] -> [(a, b, c)]
fst3 :: (a, b, c) -> a
-- | Existential wrapper around Typeable indexed by f type
-- parameter. Useful for TypeRepMap structure creation form list
-- of WrapTypeables.
data WrapTypeable f
[WrapTypeable] :: Typeable a => f a -> WrapTypeable f
calcFp :: forall a. Typeable a => Fingerprint
fromTriples :: [(Fingerprint, Any, Any)] -> TypeRepMap f
fromSortedList :: forall a. [a] -> [a]
instance forall k (f :: k -> *). GHC.Show.Show (Data.TypeRepMap.Internal.WrapTypeable f)
instance forall k (f :: k -> *). GHC.Exts.IsList (Data.TypeRepMap.Internal.TypeRepMap f)
instance forall k (f :: k -> *). GHC.Show.Show (Data.TypeRepMap.Internal.TypeRepMap f)
instance forall k (f :: k -> *). GHC.Base.Semigroup (Data.TypeRepMap.Internal.TypeRepMap f)
instance forall k (f :: k -> *). GHC.Base.Monoid (Data.TypeRepMap.Internal.TypeRepMap f)
-- | A version of TMap parametrized by an interpretation f.
-- This sort of parametrization may be familiar to users of
-- vinyl records.
--
-- TypeRepMap f is a more efficient replacement for
-- DMap TypeRep f (where DMap is from the
-- dependent-map package).
--
-- Here is an example of using Maybe as an interpretation, with a
-- comparison to TMap:
--
--
-- TMap TypeRepMap Maybe
-- -------------- -------------------
-- Int -> 5 Int -> Just 5
-- Bool -> True Bool -> Nothing
-- Char -> 'x' Char -> Just 'x'
--
--
-- In fact, a TMap is defined as TypeRepMap
-- Identity.
--
-- Since TypeRep is poly-kinded, the interpretation can use any
-- kind for the keys. For instance, we can use the Symbol kind to
-- use TypeRepMap as an extensible record:
--
--
-- newtype Field name = F (FType name)
--
-- type family FType (name :: Symbol) :: Type
-- type instance FType "radius" = Double
-- type instance FType "border-color" = RGB
-- type instance FType "border-width" = Double
--
-- TypeRepMap Field
-- --------------------------------------
-- "radius" -> F 5.7
-- "border-color" -> F (rgb 148 0 211)
-- "border-width" -> F 0.5
--
module Data.TypeRepMap
-- | 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.
data TypeRepMap (f :: k -> Type)
-- | A TypeRepMap with no values stored in it.
--
--
-- size empty == 0
--
--
--
-- member @a empty == False
--
empty :: TypeRepMap f
-- | Construct a TypeRepMap with a single element.
--
--
-- size (one x) == 1
--
--
--
-- member @a (one (x :: f a)) == True
--
one :: forall a f. Typeable a => f a -> TypeRepMap f
-- | Insert a value into a TypeRepMap.
--
--
-- size (insert v tm) >= size tm
--
--
--
-- member @a (insert (x :: f a) tm) == True
--
insert :: forall a f. Typeable a => f a -> TypeRepMap f -> TypeRepMap f
-- | Delete a value from a TypeRepMap.
--
--
-- 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
--
delete :: forall a (f :: KindOf a -> Type). Typeable 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")
--
adjust :: forall a f. Typeable a => (f a -> f a) -> TypeRepMap f -> TypeRepMap f
-- | 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"
--
hoist :: (forall x. f x -> g x) -> TypeRepMap f -> TypeRepMap g
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
-- | The union of two TypeRepMaps using a combining function.
unionWith :: (forall x. f x -> f x -> f x) -> TypeRepMap f -> TypeRepMap f -> TypeRepMap f
-- | The (left-biased) union of two TypeRepMaps. It prefers the
-- first map when duplicate keys are encountered, i.e. union
-- == unionWith const.
union :: TypeRepMap f -> TypeRepMap f -> TypeRepMap f
-- | 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
--
lookup :: forall a f. Typeable a => TypeRepMap f -> Maybe (f a)
-- | 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
--
member :: forall a (f :: KindOf a -> Type). Typeable a => TypeRepMap f -> Bool
-- | Get the amount of elements in a TypeRepMap.
size :: TypeRepMap f -> Int
-- | Return the list of SomeTypeRep from the keys.
keys :: TypeRepMap f -> [SomeTypeRep]
-- | Existential wrapper around Typeable indexed by f type
-- parameter. Useful for TypeRepMap structure creation form list
-- of WrapTypeables.
data WrapTypeable f
[WrapTypeable] :: Typeable a => f a -> WrapTypeable f
-- | 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.
module Data.TMap
-- | TMap is a special case of TypeRepMap when the
-- interpretation is Identity.
type TMap = TypeRepMap Identity
-- | A TMap with no values stored in it.
--
--
-- size empty == 0
--
--
--
-- member @a empty == False
--
empty :: TMap
-- | Construct a TMap with a single element.
--
--
-- size (one x) == 1
--
--
--
-- member @a (one (x :: a)) == True
--
one :: forall a. Typeable a => a -> TMap
-- | Insert a value into a TMap.
--
--
-- size (insert v tm) >= size tm
--
--
--
-- member @a (insert (x :: a) tm) == True
--
insert :: forall a. Typeable a => a -> TMap -> TMap
-- | 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
--
delete :: forall a. Typeable a => TMap -> TMap
-- | The union of two TMaps using a combining function.
unionWith :: (forall x. x -> x -> x) -> 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.
union :: TMap -> TMap -> TMap
-- | Map a function over the values.
map :: (forall a. Typeable a => a -> a) -> TMap -> TMap
-- | Update a value with the result of the provided function.
adjust :: Typeable a => (a -> a) -> TMap -> TMap
-- | Lookup a value of the given type in a TMap.
--
--
-- >>> x = lookup $ insert (11 :: Int) empty
--
-- >>> x :: Maybe Int
-- Just 11
--
-- >>> x :: Maybe ()
-- Nothing
--
lookup :: forall a. Typeable a => TMap -> Maybe a
-- | Check if a value of the given type is present in a TMap.
--
--
-- >>> member @Char $ one 'a'
-- True
--
-- >>> member @Bool $ one 'a'
-- False
--
member :: forall a. Typeable a => TMap -> Bool
-- | Get the amount of elements in a TMap.
size :: TMap -> Int
-- | Returns the list of SomeTypeReps from keys.
keys :: TMap -> [SomeTypeRep]