-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Dependent hash maps
--
-- Provides DHashMap, a type for hash maps where the keys can
-- specify the type of value that is associated with them.
@package dependent-hashmap
@version 0.1.0.1
-- | A map from hashable keys to values where the keys can specify the type
-- of value that is associated with them. A map cannot contain duplicate
-- keys; each key can map to at most one value. A DHashMap makes
-- no guarantees as to the order of its elements.
--
-- The interface mirrors that of HashMap, with small adjustments
-- and additions. The implementation is a thin layer on top of
-- HashMap.
--
-- The implementation is based on hash array mapped tries. A
-- DHashMap is often faster than other tree-based set types,
-- especially when key comparison is expensive, as in the case of
-- strings.
--
-- Many operations have a average-case complexity of O(log n). The
-- implementation uses a large base (i.e. 16) so in practice these
-- operations are constant time.
module Data.Dependent.HashMap
-- | A map from keys k to values v where k and
-- v are indexed types and where every key-value pair is indexed
-- by the same type.
data DHashMap k v
-- | O(1) Construct an empty map.
empty :: DHashMap k v
-- | O(1) Construct a map with a single element.
singleton :: Hashable (Some k) => k a -> v a -> DHashMap k v
-- | O(1) Return True if this map is empty, False
-- otherwise.
null :: DHashMap k v -> Bool
-- | O(n) Return the number of key-value mappings in this map.
size :: DHashMap k v -> Int
-- | O(log n) Return True if the specified key is present in
-- the map, False otherwise.
member :: (GEq k, Hashable (Some k)) => k a -> DHashMap k v -> Bool
-- | O(log n) Return the value to which the specified key is mapped,
-- or Nothing if this map contains no mapping for the key.
lookup :: (GEq k, Hashable (Some k)) => k a -> DHashMap k v -> Maybe (v a)
-- | O(log n) Return the value to which the specified key is mapped,
-- or the default value if this map contains no mapping for the key.
lookupDefault :: (GEq k, Hashable (Some k)) => v a -> k a -> DHashMap k v -> v a
-- | O(log n) Return the value to which the specified key is mapped.
-- Calls error if this map contains no mapping for the key.
(!) :: (GEq k, Hashable (Some k)) => DHashMap k v -> k a -> v a
-- | O(log n) Associate the specified value with the specified key
-- in this map. If this map previously contained a mapping for the key,
-- the old value is replaced.
insert :: (GEq k, Hashable (Some k)) => k a -> v a -> DHashMap k v -> DHashMap k v
-- | O(log n) Associate the value with the key in this map. If this
-- map previously contained a mapping for the key, the old value is
-- replaced by the result of applying the given function to the new and
-- old value. Example:
--
--
-- insertWith f k v map
-- where f new old = new + old
--
insertWith :: (GEq k, Hashable (Some k)) => (v a -> v a -> v a) -> k a -> v a -> DHashMap k v -> DHashMap k v
-- | O(log n) Remove the mapping for the specified key from this map
-- if present.
delete :: (GEq k, Hashable (Some k)) => k a -> DHashMap k v -> DHashMap k v
-- | O(log n) Adjust the value tied to a given key in this map only
-- if it is present. Otherwise, leave the map alone.
adjust :: (GEq k, Hashable (Some k)) => (v a -> v a) -> k a -> DHashMap k v -> DHashMap k v
-- | O(log n) The expression (update f k map)
-- updates the value x at k, (if it is in the map). If
-- (f k x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value y.
update :: (GEq k, Hashable (Some k)) => (v a -> Maybe (v a)) -> k a -> DHashMap k v -> DHashMap k v
-- | O(log n) The expression (alter f k map) alters
-- the value x at k, or absence thereof. alter
-- can be used to insert, delete, or update a value in a map. In short :
-- lookup k (alter f k m) = f (lookup k m).
alter :: (GEq k, Hashable (Some k)) => (Maybe (v a) -> Maybe (v a)) -> k a -> DHashMap k v -> DHashMap k v
-- | O(log n) The expression (alterF f k map) alters
-- the value x at k, or absence thereof.
-- alterF can be used to insert, delete, or update a value in a
-- map.
alterF :: (Functor f, GEq k, Hashable (Some k)) => (Maybe (v a) -> f (Maybe (v a))) -> k a -> DHashMap k v -> f (DHashMap k v)
-- | O(log n) alterLookup f k map looks up the value
-- at k, if any, and alters it, in one operation.
--
--
-- alterLookup f k map = (lookup k map, alter f k map)
--
alterLookup :: (GEq k, Hashable (Some k)) => (Maybe (v a) -> Maybe (v a)) -> k a -> DHashMap k v -> (Maybe (v a), DHashMap k v)
-- | O(n+m) The union of two maps. If a key occurs in both maps, the
-- mapping from the first will be the mapping in the result.
union :: (GEq k, Hashable (Some k)) => DHashMap k v -> DHashMap k v -> DHashMap k v
-- | O(n+m) The union of two maps. If a key occurs in both maps, the
-- provided function (first argument) will be used to compute the result.
unionWith :: (GEq k, Hashable (Some k)) => (forall a. v a -> v a -> v a) -> DHashMap k v -> DHashMap k v -> DHashMap k v
-- | O(n+m) The union of two maps. If a key occurs in both maps, the
-- provided function (first argument) will be used to compute the result.
unionWithKey :: (GEq k, Hashable (Some k)) => (forall a. k a -> v a -> v a -> v a) -> DHashMap k v -> DHashMap k v -> DHashMap k v
-- | The union of a list of maps.
unions :: (GEq k, Hashable (Some k), Foldable f) => f (DHashMap k v) -> DHashMap k v
-- | The union of a list of maps, with combining operation.
unionsWith :: (GEq k, Hashable (Some k), Foldable f) => (forall a. v a -> v a -> v a) -> f (DHashMap k v) -> DHashMap k v
-- | The union of a list of maps, with combining operation.
unionsWithKey :: (GEq k, Hashable (Some k), Foldable f) => (forall a. k a -> v a -> v a -> v a) -> f (DHashMap k v) -> DHashMap k v
-- | O(n) Transform this map by applying a function to every value.
map :: (forall a. v a -> v' a) -> DHashMap k v -> DHashMap k v'
-- | O(n) Transform this map by applying a function to every value.
mapWithKey :: (forall a. k a -> v a -> v' a) -> DHashMap k v -> DHashMap k v'
-- | O(n) Perform an Applicative action for each value in a
-- map and produce a map of all the results.
--
-- Note: the order in which the actions occur is unspecified. In
-- particular, when the map contains hash collisions, the order in which
-- the actions associated with the keys involved will depend in an
-- unspecified way on their insertion order.
traverse :: Applicative f => (forall a. v a -> f (v' a)) -> DHashMap k v -> f (DHashMap k v')
-- | O(n) Perform an Applicative action for each key-value
-- pair in a map and produce a map of all the results.
--
-- Note: the order in which the actions occur is unspecified. In
-- particular, when the map contains hash collisions, the order in which
-- the actions associated with the keys involved will depend in an
-- unspecified way on their insertion order.
traverseWithKey :: Applicative f => (forall a. k a -> v a -> f (v' a)) -> DHashMap k v -> f (DHashMap k v')
-- | O(n*log m) Difference of two maps. Return elements of the first
-- map not existing in the second.
difference :: (GEq k, Hashable (Some k)) => DHashMap k v -> DHashMap k v' -> DHashMap k v
-- | O(n*log m) Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the values
-- of these keys. If it returns Nothing, the element is discarded
-- (proper set difference). If it returns (Just y), the
-- element is updated with a new value y.
differenceWith :: (GEq k, Hashable (Some k)) => (forall a. v a -> v' a -> Maybe (v a)) -> DHashMap k v -> DHashMap k v' -> DHashMap k v
-- | O(n*log m) Difference with a combining function. When two equal
-- keys are encountered, the combining function is applied to the key and
-- the values of these keys. If it returns Nothing, the element is
-- discarded (proper set difference). If it returns (Just
-- y), the element is updated with a new value y.
differenceWithKey :: (GEq k, Hashable (Some k)) => (forall a. k a -> v a -> v' a -> Maybe (v a)) -> DHashMap k v -> DHashMap k v' -> DHashMap k v
-- | O(n*log m) Intersection of two maps. Return elements of the
-- first map for keys existing in the second.
intersection :: (GEq k, Hashable (Some k)) => DHashMap k v -> DHashMap k v' -> DHashMap k v
-- | O(n+m) Intersection of two maps. If a key occurs in both maps
-- the provided function is used to combine the values from the two maps.
intersectionWith :: (GEq k, Hashable (Some k)) => (forall a. v1 a -> v2 a -> v3 a) -> DHashMap k v1 -> DHashMap k v2 -> DHashMap k v3
-- | O(n+m) Intersection of two maps. If a key occurs in both maps
-- the provided function is used to combine the values from the two maps.
intersectionWithKey :: (GEq k, Hashable (Some k)) => (forall a. k a -> v1 a -> v2 a -> v3 a) -> DHashMap k v1 -> DHashMap k v2 -> DHashMap k v3
-- | Map each value of the map to a monoid, and combine the results.
foldMap :: Monoid m => (forall a. v a -> m) -> DHashMap k v -> m
-- | Map each key-value pair of the map to a monoid, and combine the
-- results.
foldMapWithKey :: Monoid m => (forall a. k a -> v a -> m) -> DHashMap k v -> m
-- | O(n) Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the left-identity
-- of the operator).
foldl :: (forall a. b -> v a -> b) -> b -> DHashMap k v -> b
-- | O(n) Reduce this map by applying a binary operator to all
-- key-value pairs, using the given starting value (typically the
-- left-identity of the operator).
foldlWithKey :: (forall a. b -> k a -> v a -> b) -> b -> DHashMap k v -> b
-- | O(n) Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the left-identity
-- of the operator). Each application of the operator is evaluated before
-- using the result in the next application. This function is strict in
-- the starting value.
foldl' :: (forall a. b -> v a -> b) -> b -> DHashMap k v -> b
-- | O(n) Reduce this map by applying a binary operator to all
-- key-value pairs, using the given starting value (typically the
-- left-identity of the operator). Each application of the operator is
-- evaluated before using the result in the next application. This
-- function is strict in the starting value.
foldlWithKey' :: (forall a. b -> k a -> v a -> b) -> b -> DHashMap k v -> b
-- | O(n) Reduce this map by applying a binary operator to all
-- elements, using the given starting value (typically the right-identity
-- of the operator).
foldr :: (forall a. v a -> b -> b) -> b -> DHashMap k v -> b
-- | O(n) Reduce this map by applying a binary operator to all
-- key-value pairs, using the given starting value (typically the
-- right-identity of the operator).
foldrWithKey :: (forall a. k a -> v a -> b -> b) -> b -> DHashMap k v -> b
-- | O(n) Filter this map by retaining values that satisfy a
-- predicate.
filter :: (forall a. v a -> Bool) -> DHashMap k v -> DHashMap k v
-- | O(n) Filter this map by retaining only key-value pairs
-- satisfying a predicate.
filterWithKey :: (forall a. k a -> v a -> Bool) -> DHashMap k v -> DHashMap k v
-- | O(n) Transform this map by applying a function to every value
-- and retaining only the Just results.
mapMaybe :: (forall a. v1 a -> Maybe (v2 a)) -> DHashMap k v1 -> DHashMap k v2
-- | O(n) Transform this map by applying a function to every
-- key-value pair and retaining only the Just results.
mapMaybeWithKey :: (forall a. k a -> v1 a -> Maybe (v2 a)) -> DHashMap k v1 -> DHashMap k v2
-- | O(n) Return a list of this map's keys. The list is produced
-- lazily.
keys :: DHashMap k v -> [Some k]
-- | O(n) Return a list of this map's values. The list is produced
-- lazily.
elems :: DHashMap k v -> [Some v]
-- | O(n) Return a list of this map's elements. The list is produced
-- lazily. The order of its elements is unspecified.
toList :: DHashMap k v -> [DSum k v]
-- | O(n) Construct a map with the supplied mappings. If the list
-- contains duplicate mappings, the later mappings take precedence.
fromList :: (GEq k, Hashable (Some k)) => [DSum k f] -> DHashMap k f
-- | O(n*log n) Construct a map from a list of elements. Uses the
-- provided function to merge duplicate entries.
fromListWith :: (GEq k, Hashable (Some k)) => (forall a. v a -> v a -> v a) -> [DSum k v] -> DHashMap k v
-- | O(n*log n) Construct a map from a list of elements. Uses the
-- provided function to merge duplicate entries.
fromListWithKey :: (GEq k, Hashable (Some k)) => (forall a. k a -> v a -> v a -> v a) -> [DSum k v] -> DHashMap k v
-- | A basic dependent sum type; the first component is a tag that
-- specifies the type of the second; for example, think of a GADT such
-- as:
--
--
-- data Tag a where
-- AString :: Tag String
-- AnInt :: Tag Int
--
--
-- Then, we have the following valid expressions of type Applicative
-- f => DSum Tag f:
--
--
-- AString ==> "hello!"
-- AnInt ==> 42
--
--
-- And we can write functions that consume DSum Tag f values by
-- matching, such as:
--
--
-- toString :: DSum Tag Identity -> String
-- toString (AString :=> Identity str) = str
-- toString (AnInt :=> Identity int) = show int
--
--
-- By analogy to the (key => value) construction for dictionary
-- entries in many dynamic languages, we use (key :=> value) as the
-- constructor for dependent sums. The :=> and ==> operators have
-- very low precedence and bind to the right, so if the Tag GADT
-- is extended with an additional constructor Rec :: Tag (DSum Tag
-- Identity), then Rec ==> AnInt ==> 3 + 4 is parsed
-- as would be expected (Rec ==> (AnInt ==> (3 + 4))) and
-- has type DSum Identity Tag. Its precedence is just above that
-- of $, so foo bar $ AString ==> "eep" is equivalent
-- to foo bar (AString ==> "eep").
data DSum (tag :: k -> Type) (f :: k -> Type) :: forall k. () => k -> Type -> k -> Type -> Type
[:=>] :: forall k (tag :: k -> Type) (f :: k -> Type) (a :: k). () => !tag a -> f a -> DSum tag f
infixr 1 :=>
-- | Existential. This is type is useful to hide GADTs' parameters.
--
--
-- >>> data Tag :: * -> * where TagInt :: Tag Int; TagBool :: Tag Bool
--
-- >>> instance GShow Tag where gshowsPrec _ TagInt = showString "TagInt"; gshowsPrec _ TagBool = showString "TagBool"
--
--
-- You can either use PatternSynonyms
--
--
-- >>> let x = Some TagInt
--
-- >>> x
-- Some TagInt
--
--
--
-- >>> case x of { Some TagInt -> "I"; Some TagBool -> "B" } :: String
-- "I"
--
--
-- or you can use functions
--
--
-- >>> let y = mkSome TagBool
--
-- >>> y
-- Some TagBool
--
--
--
-- >>> withSome y $ \y' -> case y' of { TagInt -> "I"; TagBool -> "B" } :: String
-- "B"
--
--
-- The implementation of mapSome is safe.
--
--
-- >>> let f :: Tag a -> Tag a; f TagInt = TagInt; f TagBool = TagBool
--
-- >>> mapSome f y
-- Some TagBool
--
--
-- but you can also use:
--
--
-- >>> withSome y (mkSome . f)
-- Some TagBool
--
data Some (tag :: k -> Type) :: forall k. () => k -> Type -> Type
pattern Some :: forall k (tag :: k -> Type). () => forall (a :: k). () => tag a -> Some tag
instance (Data.GADT.Compare.GEq k, Data.Constraint.Extras.Has' GHC.Classes.Eq k v) => GHC.Classes.Eq (Data.Dependent.HashMap.DHashMap k v)
instance (Data.GADT.Compare.GCompare k, Data.Constraint.Extras.Has' GHC.Classes.Eq k v, Data.Constraint.Extras.Has' GHC.Classes.Ord k v) => GHC.Classes.Ord (Data.Dependent.HashMap.DHashMap k v)
instance (Data.GADT.Compare.GEq k, Data.Hashable.Class.Hashable (Data.Some.Some k)) => GHC.Base.Semigroup (Data.Dependent.HashMap.DHashMap k v)
instance (Data.GADT.Compare.GEq k, Data.Hashable.Class.Hashable (Data.Some.Some k)) => GHC.Base.Monoid (Data.Dependent.HashMap.DHashMap k v)
instance (Data.GADT.Compare.GEq k, Data.Hashable.Class.Hashable (Data.Some.Some k)) => GHC.Exts.IsList (Data.Dependent.HashMap.DHashMap k v)
instance (Data.GADT.Compare.GEq k, Data.GADT.Show.GRead k, Data.Constraint.Extras.Has' GHC.Read.Read k v, Data.Hashable.Class.Hashable (Data.Some.Some k)) => GHC.Read.Read (Data.Dependent.HashMap.DHashMap k v)
instance (Data.GADT.Show.GShow k, Data.Constraint.Extras.Has' GHC.Show.Show k v) => GHC.Show.Show (Data.Dependent.HashMap.DHashMap k v)