-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Dependent finite maps (partial dependent products)
--   
--   Provides a type called DMap which generalizes
--   Data.Map.Map, allowing keys to specify the type of value that
--   can be associated with them.
@package dependent-map
@version 0.4.0.1

module Data.Dependent.Map.Internal

-- | Dependent maps: k is a GADT-like thing with a facility for
--   rediscovering its type parameter, elements of which function as
--   identifiers tagged with the type of the thing they identify. Real
--   GADTs are one useful instantiation of k, as are Tags
--   from Data.Unique.Tag in the 'prim-uniq' package.
--   
--   Semantically, DMap k f is equivalent to a set of
--   DSum k f where no two elements have the same tag.
--   
--   More informally, DMap is to dependent products as Map is
--   to (->). Thus it could also be thought of as a partial (in
--   the sense of "partial function") dependent product.
data DMap (k1 :: k -> Type) (f :: k -> Type)
[Tip] :: forall {k} (k1 :: k -> Type) (f :: k -> Type). DMap k1 f
[Bin] :: forall {k} (k1 :: k -> Type) (v :: k) (f :: k -> Type). !Int -> !k1 v -> f v -> !DMap k1 f -> !DMap k1 f -> DMap k1 f

-- | O(1). The empty map.
--   
--   
--   empty      == fromList []
--   size empty == 0
--   
empty :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f

-- | O(1). A map with a single element.
--   
--   
--   singleton 1 'a'        == fromList [(1, 'a')]
--   size (singleton 1 'a') == 1
--   
singleton :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f

-- | O(1). Is the map empty?
null :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Bool

-- | O(1). The number of elements in the map.
size :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Int

-- | O(log n). Lookup the value at a key in the map.
--   
--   The function will return the corresponding value as (Just
--   value), or Nothing if the key isn't in the map.
lookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe (f v)
lookupAssoc :: forall {k1} {k2} (k3 :: k1 -> Type) (f :: k1 -> Type) (v :: k2). GCompare k3 => Some k3 -> DMap k3 f -> Maybe (DSum k3 f)
combine :: forall {k1} k2 (v :: k1) f. GCompare k2 => k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
insertMax :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f
insertMin :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f
merge :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f -> DMap k2 f
glue :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f -> DMap k2 f

-- | O(log n). Delete and find the minimal element.
--   
--   
--   deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
--   deleteFindMin                                            Error: can not return the minimal element of an empty map
--   
deleteFindMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)

-- | A strict pair.
data a :*: b
(:*:) :: !a -> !b -> (:*:) a b
infixr 1 :*:
infixr 1 :*:

-- | Convert a strict pair to a pair.
toPair :: (a :*: b) -> (a, b)
data Triple' a b c
Triple' :: !a -> !b -> !c -> Triple' a b c

-- | Convert a strict triple to a triple.
toTriple :: Triple' a b c -> (a, b, c)

-- | O(log n). Retrieves the minimal (key :=> value) entry of the
--   map, and the map stripped of that element, or Nothing if passed
--   an empty map.
minViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)

-- | O(log n). Retrieves the maximal (key :=> value) entry of the
--   map, and the map stripped of that element, or Nothing if passed
--   an empty map.
maxViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)

-- | O(log n). Delete and find the maximal element.
--   
--   
--   deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
--   deleteFindMax empty                                      Error: can not return the maximal element of an empty map
--   
deleteFindMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)
delta :: Int
ratio :: Int
balance :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
rotateL :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
rotateR :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
singleL :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
singleR :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
doubleL :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
doubleR :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
bin :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f -> DMap k2 f -> DMap k2 f
trim :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (Some k2 -> Ordering) -> (Some k2 -> Ordering) -> DMap k2 f -> DMap k2 f
trimLookupLo :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => Some k2 -> (Some k2 -> Ordering) -> DMap k2 f -> (Maybe (DSum k2 f), DMap k2 f)
filterGt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => (Some k2 -> Ordering) -> DMap k2 f -> DMap k2 f
filterLt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => (Some k2 -> Ordering) -> DMap k2 f -> DMap k2 f

module Data.Dependent.Map

-- | Dependent maps: k is a GADT-like thing with a facility for
--   rediscovering its type parameter, elements of which function as
--   identifiers tagged with the type of the thing they identify. Real
--   GADTs are one useful instantiation of k, as are Tags
--   from Data.Unique.Tag in the 'prim-uniq' package.
--   
--   Semantically, DMap k f is equivalent to a set of
--   DSum k f where no two elements have the same tag.
--   
--   More informally, DMap is to dependent products as Map is
--   to (->). Thus it could also be thought of as a partial (in
--   the sense of "partial function") dependent product.
data DMap (k1 :: k -> Type) (f :: k -> Type)

-- | O(log n). Find the value at a key. Calls error when the
--   element can not be found.
--   
--   
--   fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
--   fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--   
(!) :: forall {k1} k2 f (v :: k1). GCompare k2 => DMap k2 f -> k2 v -> f v
infixl 9 !

-- | Same as difference.
(\\) :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f
infixl 9 \\

-- | O(1). Is the map empty?
null :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Bool

-- | O(1). The number of elements in the map.
size :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Int

-- | O(log n). Is the key a member of the map? See also
--   notMember.
member :: forall {k1} k2 (a :: k1) (f :: k1 -> Type). GCompare k2 => k2 a -> DMap k2 f -> Bool

-- | O(log n). Is the key not a member of the map? See also
--   member.
notMember :: forall {k1} k2 (v :: k1) (f :: k1 -> Type). GCompare k2 => k2 v -> DMap k2 f -> Bool

-- | O(log n). Lookup the value at a key in the map.
--   
--   The function will return the corresponding value as (Just
--   value), or Nothing if the key isn't in the map.
lookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe (f v)

-- | O(log n). The expression (findWithDefault def k
--   map) returns the value at key k or returns default value
--   def when the key is not in the map.
findWithDefault :: forall {k1} k2 f (v :: k1). GCompare k2 => f v -> k2 v -> DMap k2 f -> f v

-- | O(1). The empty map.
--   
--   
--   empty      == fromList []
--   size empty == 0
--   
empty :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f

-- | O(1). A map with a single element.
--   
--   
--   singleton 1 'a'        == fromList [(1, 'a')]
--   size (singleton 1 'a') == 1
--   
singleton :: forall {k1} k2 (v :: k1) f. k2 v -> f v -> DMap k2 f

-- | O(log n). Insert a new key and value in the map. If the key is
--   already present in the map, the associated value is replaced with the
--   supplied value. insert is equivalent to insertWith
--   const.
insert :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> f v -> DMap k2 f -> DMap k2 f

-- | O(log n). Insert with a function, combining new value and old
--   value. insertWith f key value mp will insert the entry
--   key :=> value into mp if key does not exist in
--   the map. If the key does exist, the function will insert the entry
--   key :=> f new_value old_value.
insertWith :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f

-- | Same as insertWith, but the combining function is applied
--   strictly. This is often the most desirable behavior.
insertWith' :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f

-- | O(log n). Insert with a function, combining key, new value and
--   old value. insertWithKey f key value mp will insert
--   the entry key :=> value into mp if key does not
--   exist in the map. If the key does exist, the function will insert the
--   entry key :=> f key new_value old_value. Note that the key
--   passed to f is the same key passed to insertWithKey.
insertWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f

-- | Same as insertWithKey, but the combining function is applied
--   strictly.
insertWithKey' :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> DMap k2 f

-- | O(log n). Combines insert operation with old value retrieval.
--   The expression (insertLookupWithKey f k x map) is a
--   pair where the first element is equal to (lookup k
--   map) and the second element equal to (insertWithKey f
--   k x map).
insertLookupWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f)

-- | O(log n). A strict version of insertLookupWithKey.
insertLookupWithKey' :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> f v -> f v) -> k2 v -> f v -> DMap k2 f -> (Maybe (f v), DMap k2 f)

-- | O(log n). Delete a key and its value from the map. When the key
--   is not a member of the map, the original map is returned.
delete :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> DMap k2 f

-- | O(log n). 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.
adjust :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f

-- | O(log n). Adjust a value at a specific key. When the key is not
--   a member of the map, the original map is returned.
adjustWithKey :: forall {k1} k2 (v :: k1) f. GCompare k2 => (k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f

-- | O(log n). A strict version of adjustWithKey.
adjustWithKey' :: forall {k1} k2 (v :: k1) f. GCompare k2 => (k2 v -> f v -> f v) -> k2 v -> DMap k2 f -> DMap k2 f

-- | O(log n). The expression (update f k map)
--   updates the value x at k (if it is in the map). If
--   (f x) is Nothing, the element is deleted. If it is
--   (Just y), the key k is bound to the new value
--   y.
update :: forall {k1} k2 f (v :: k1). GCompare k2 => (f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f

-- | O(log n). The expression (updateWithKey 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.
updateWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f

-- | O(log n). Lookup and update. See also updateWithKey. The
--   function returns changed value, if it is updated. Returns the original
--   key value if the map entry is deleted.
updateLookupWithKey :: forall {k1} k2 f (v :: k1). GCompare k2 => (k2 v -> f v -> Maybe (f v)) -> k2 v -> DMap k2 f -> (Maybe (f v), DMap k2 f)

-- | 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 :: forall {k1} k2 f (v :: k1). GCompare k2 => (Maybe (f v) -> Maybe (f v)) -> k2 v -> DMap k2 f -> DMap k2 f

-- | Works the same as alter except the new value is returned in
--   some Functor f. In short : (v' -> alter (const
--   v') k dm) $ f (lookup k dm)
alterF :: forall {k1} k2 f (v :: k1) g. (GCompare k2, Functor f) => k2 v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k2 g -> f (DMap k2 g)

-- | O(m*log(n/m + 1)), m <= n. The expression (union
--   t1 t2) takes the left-biased union of t1 and
--   t2. It prefers t1 when duplicate keys are
--   encountered, i.e. (union == unionWith
--   const).
union :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f

-- | O(n+m). Union with a combining function.
unionWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> f v -> f v) -> DMap k2 f -> DMap k2 f -> DMap k2 f

-- | The union of a list of maps: (unions == foldl
--   union empty).
unions :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => [DMap k2 f] -> DMap k2 f

-- | The union of a list of maps, with a combining operation:
--   (unionsWithKey f == foldl (unionWithKey f)
--   empty).
unionsWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> f v -> f v) -> [DMap k2 f] -> DMap k2 f

-- | O(m * log (n/m + 1)), m <= n. Difference of two maps. Return
--   elements of the first map not existing in the second map.
difference :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type) (g :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 g -> DMap k2 f

-- | O(n+m). Difference with a combining function. When two equal
--   keys are encountered, the combining function is applied to the key and
--   both values. 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 :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> g v -> Maybe (f v)) -> DMap k2 f -> DMap k2 g -> DMap k2 f

-- | O(m * log (n/m + 1), m <= n. Intersection of two maps.
--   Return data in the first map for the keys existing in both maps.
--   (intersection m1 m2 == intersectionWith
--   const m1 m2).
intersection :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> DMap k2 f -> DMap k2 f

-- | O(m * log (n/m + 1), m <= n. Intersection with a combining
--   function.
intersectionWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> g v -> h v) -> DMap k2 f -> DMap k2 g -> DMap k2 h

-- | O(n). Map a function over all values in the map.
map :: forall {k1} f g (k2 :: k1 -> Type). (forall (v :: k1). () => f v -> g v) -> DMap k2 f -> DMap k2 g

-- | O(n). ffor == flip map except we
--   cannot actually use flip because of the lack of impredicative
--   types.
ffor :: forall {k1} (k2 :: k1 -> Type) f g. DMap k2 f -> (forall (v :: k1). () => f v -> g v) -> DMap k2 g

-- | O(n). Map a function over all values in the map.
mapWithKey :: (forall (v :: k1). () => k2 v -> f v -> g v) -> DMap k2 f -> DMap k2 g

-- | O(n). fforWithKey == flip
--   mapWithKey except we cannot actually use flip
--   because of the lack of impredicative types.
fforWithKey :: DMap k2 f -> (forall (v :: k1). () => k2 v -> f v -> g v) -> DMap k2 g

-- | O(n). traverseWithKey f m == fromList
--   $ traverse ((k, v) -> (,) k $ f k v)
--   (toList m) That is, behaves exactly like a regular
--   traverse except that the traversing function also has access to
--   the key associated with a value.
traverseWithKey_ :: forall {k1} t k2 f. Applicative t => (forall (v :: k1). () => k2 v -> f v -> t ()) -> DMap k2 f -> t ()

-- | O(n). forWithKey == flip
--   traverseWithKey except we cannot actually use flip
--   because of the lack of impredicative types.
forWithKey_ :: forall {k1} t k2 f. Applicative t => DMap k2 f -> (forall (v :: k1). () => k2 v -> f v -> t ()) -> t ()

-- | O(n). traverseWithKey f m == fromList
--   $ traverse ((k, v) -> (,) k $ f k v)
--   (toList m) That is, behaves exactly like a regular
--   traverse except that the traversing function also has access to
--   the key associated with a value.
traverseWithKey :: forall {k1} t k2 f g. Applicative t => (forall (v :: k1). () => k2 v -> f v -> t (g v)) -> DMap k2 f -> t (DMap k2 g)

-- | O(n). forWithKey == flip
--   traverseWithKey except we cannot actually use flip
--   because of the lack of impredicative types.
forWithKey :: forall {k1} t k2 f g. Applicative t => DMap k2 f -> (forall (v :: k1). () => k2 v -> f v -> t (g v)) -> t (DMap k2 g)

-- | O(n). The function mapAccumLWithKey threads an
--   accumulating argument through the map in ascending order of keys.
mapAccumLWithKey :: (forall (v :: k1). () => a -> k2 v -> f v -> (a, g v)) -> a -> DMap k2 f -> (a, DMap k2 g)

-- | O(n). The function mapAccumRWithKey threads an
--   accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (forall (v :: k1). () => a -> k2 v -> f v -> (a, g v)) -> a -> DMap k2 f -> (a, DMap k2 g)

-- | O(n*log n). mapKeysWith c f s is the map
--   obtained by applying f to each key of s.
--   
--   The size of the result may be smaller if f maps two or more
--   distinct keys to the same new key. In this case the associated values
--   will be combined using c.
mapKeysWith :: GCompare k2 => (forall (v :: k). () => k2 v -> f v -> f v -> f v) -> (forall (v :: k). () => k1 v -> k2 v) -> DMap k1 f -> DMap k2 f

-- | O(n). mapKeysMonotonic f s == mapKeys f
--   s, but works only when f is strictly monotonic. That is,
--   for any values x and y, if x <
--   y then f x < f y. The precondition is
--   not checked. Semi-formally, we have:
--   
--   
--   and [x < y ==> f x < f y | x <- ls, y <- ls]
--                       ==> mapKeysMonotonic f s == mapKeys f s
--       where ls = keys s
--   
--   
--   This means that f maps distinct original keys to distinct
--   resulting keys. This function has better performance than
--   mapKeys.
mapKeysMonotonic :: forall {k} k1 k2 (f :: k -> Type). (forall (v :: k). () => k1 v -> k2 v) -> DMap k1 f -> DMap k2 f

-- | O(n). Fold the keys and values in the map, such that
--   foldWithKey f z == foldr (uncurry f) z .
--   toAscList.
--   
--   This is identical to foldrWithKey, and you should use that one
--   instead of this one. This name is kept for backward compatibility.

-- | Deprecated: Use foldrWithKey instead
foldWithKey :: (forall (v :: k1). () => k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b

-- | O(n). Post-order fold. The function will be applied from the
--   lowest value to the highest.
foldrWithKey :: (forall (v :: k1). () => k2 v -> f v -> b -> b) -> b -> DMap k2 f -> b

-- | O(n). Pre-order fold. The function will be applied from the
--   highest value to the lowest.
foldlWithKey :: (forall (v :: k1). () => b -> k2 v -> f v -> b) -> b -> DMap k2 f -> b

-- | O(n). Return all keys of the map in ascending order.
--   
--   
--   keys (fromList [(5,"a"), (3,"b")]) == [3,5]
--   keys empty == []
--   
keys :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [Some k2]

-- | O(n). Return all key/value pairs in the map in ascending key
--   order.
assocs :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]

-- | O(n). Convert to a list of key/value pairs.
toList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]

-- | O(n*log n). Build a map from a list of key/value pairs. See
--   also fromAscList. If the list contains more than one value for
--   the same key, the last value for the key is retained.
fromList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => [DSum k2 f] -> DMap k2 f

-- | O(n*log n). Build a map from a list of key/value pairs with a
--   combining function. See also fromAscListWithKey.
fromListWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> f v -> f v) -> [DSum k2 f] -> DMap k2 f

-- | O(n). Convert to an ascending list.
toAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]

-- | O(n). Convert to a descending list.
toDescList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> [DSum k2 f]

-- | O(n). Build a map from an ascending list in linear time. The
--   precondition (input list is ascending) is not checked.
fromAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GEq k2 => [DSum k2 f] -> DMap k2 f

-- | O(n). Build a map from an ascending list in linear time with a
--   combining function for equal keys. The precondition (input list is
--   ascending) is not checked.
fromAscListWithKey :: GEq k2 => (forall (v :: k1). () => k2 v -> f v -> f v -> f v) -> [DSum k2 f] -> DMap k2 f

-- | O(n). Build a map from an ascending list of distinct elements
--   in linear time. The precondition is not checked.
fromDistinctAscList :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). [DSum k2 f] -> DMap k2 f

-- | <math>. filter, applied to a predicate and a list,
--   returns the list of those elements that satisfy the predicate; i.e.,
--   
--   
--   filter p xs = [ x | x <- xs, p x]
--   
--   
--   
Examples
--   
--   
--   >>> filter odd [1, 2, 3]
--   [1,3]
--   
--   
--   
--   >>> filter (\l -> length l > 3) ["Hello", ", ", "World", "!"]
--   ["Hello","World"]
--   
--   
--   
--   >>> filter (/= 3) [1, 2, 3, 4, 3, 2, 1]
--   [1,2,4,2,1]
--   
filter :: (a -> Bool) -> [a] -> [a]

-- | O(n). Filter all keys/values that satisfy the predicate.
filterWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> Bool) -> DMap k2 f -> DMap k2 f

-- | O(n). Partition the map according to a predicate. The first map
--   contains all elements that satisfy the predicate, the second all
--   elements that fail the predicate. See also split.
partitionWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> Bool) -> DMap k2 f -> (DMap k2 f, DMap k2 f)

-- | O(n). Map values and collect the Just results.
mapMaybe :: forall {k1} (k2 :: k1 -> Type) f g. GCompare k2 => (forall (v :: k1). () => f v -> Maybe (g v)) -> DMap k2 f -> DMap k2 g

-- | O(n). Map keys/values and collect the Just results.
mapMaybeWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> Maybe (g v)) -> DMap k2 f -> DMap k2 g

-- | O(n). Map keys/values and separate the Left and
--   Right results.
mapEitherWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> Either (g v) (h v)) -> DMap k2 f -> (DMap k2 g, DMap k2 h)

-- | O(log n). The expression (split k map) is a
--   pair (map1,map2) where the keys in map1 are smaller
--   than k and the keys in map2 larger than k.
--   Any key equal to k is found in neither map1 nor
--   map2.
split :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> (DMap k2 f, DMap k2 f)

-- | O(log n). The expression (splitLookup k map)
--   splits a map just like split but also returns lookup
--   k map.
splitLookup :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> (DMap k2 f, Maybe (f v), DMap k2 f)

-- | O(n+m). This function is defined as (isSubmapOf =
--   isSubmapOfBy eqTagged)).
isSubmapOf :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GCompare k2, Has' Eq k2 f) => DMap k2 f -> DMap k2 f -> Bool

-- | O(n+m). The expression (isSubmapOfBy f t1 t2)
--   returns True if all keys in t1 are in tree
--   t2, and when f returns True when applied to
--   their respective keys and values.
isSubmapOfBy :: GCompare k2 => (forall (v :: k1). () => k2 v -> k2 v -> f v -> g v -> Bool) -> DMap k2 f -> DMap k2 g -> Bool

-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
--   Defined as (isProperSubmapOf = isProperSubmapOfBy
--   eqTagged).
isProperSubmapOf :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GCompare k2, Has' Eq k2 f) => DMap k2 f -> DMap k2 f -> Bool

-- | O(n+m). Is this a proper submap? (ie. a submap but not equal).
--   The expression (isProperSubmapOfBy f m1 m2) returns
--   True when m1 and m2 are not equal, all keys
--   in m1 are in m2, and when f returns
--   True when applied to their respective keys and values.
isProperSubmapOfBy :: GCompare k2 => (forall (v :: k1). () => k2 v -> k2 v -> f v -> g v -> Bool) -> DMap k2 f -> DMap k2 g -> Bool

-- | O(log n). Lookup the index of a key. The index is a
--   number from 0 up to, but not including, the size of the
--   map.
lookupIndex :: forall {k1} k2 (f :: k1 -> Type) (v :: k1). GCompare k2 => k2 v -> DMap k2 f -> Maybe Int

-- | O(log n). Return the index of a key. The index is a
--   number from 0 up to, but not including, the size of the
--   map. Calls error when the key is not a member of the
--   map.
findIndex :: forall {k1} k2 (v :: k1) (f :: k1 -> Type). GCompare k2 => k2 v -> DMap k2 f -> Int

-- | O(log n). Retrieve an element by index. Calls
--   error when an invalid index is used.
elemAt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). Int -> DMap k2 f -> DSum k2 f

-- | O(log n). Update the element at index. Does nothing when
--   an invalid index is used.
updateAt :: (forall (v :: k1). () => k2 v -> f v -> Maybe (f v)) -> Int -> DMap k2 f -> DMap k2 f

-- | O(log n). Delete the element at index. Defined as
--   (deleteAt i map = updateAt (k x ->
--   Nothing) i map).
deleteAt :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). Int -> DMap k2 f -> DMap k2 f

-- | O(log n). The minimal key of the map. Calls error is the
--   map is empty.
findMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DSum k2 f

-- | O(log n). The maximal key of the map. Calls error is the
--   map is empty.
findMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DSum k2 f
lookupMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f)
lookupMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f)

-- | O(log n). Delete the minimal key. Returns an empty map if the
--   map is empty.
deleteMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f

-- | O(log n). Delete the maximal key. Returns an empty map if the
--   map is empty.
deleteMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> DMap k2 f

-- | O(log n). Delete and find the minimal element.
--   
--   
--   deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
--   deleteFindMin                                            Error: can not return the minimal element of an empty map
--   
deleteFindMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)

-- | O(log n). Delete and find the maximal element.
--   
--   
--   deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
--   deleteFindMax empty                                      Error: can not return the maximal element of an empty map
--   
deleteFindMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)

-- | O(log n). Update the value at the minimal key.
updateMinWithKey :: (forall (v :: k1). () => k2 v -> f v -> Maybe (f v)) -> DMap k2 f -> DMap k2 f

-- | O(log n). Update the value at the maximal key.
updateMaxWithKey :: (forall (v :: k1). () => k2 v -> f v -> Maybe (f v)) -> DMap k2 f -> DMap k2 f

-- | O(log n). Retrieves the minimal (key :=> value) entry of the
--   map, and the map stripped of that element, or Nothing if passed
--   an empty map.
minViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)

-- | O(log n). Retrieves the maximal (key :=> value) entry of the
--   map, and the map stripped of that element, or Nothing if passed
--   an empty map.
maxViewWithKey :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> Maybe (DSum k2 f, DMap k2 f)

-- | O(n). Show the tree that implements the map. The tree is shown
--   in a compressed, hanging format. See showTreeWith.
showTree :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). (GShow k2, Has' Show k2 f) => DMap k2 f -> String

-- | O(n). The expression (showTreeWith showelem hang
--   wide map) shows the tree that implements the map. Elements are
--   shown using the showElem function. If hang is
--   True, a hanging tree is shown otherwise a rotated tree
--   is shown. If wide is True, an extra wide version is
--   shown.
showTreeWith :: (forall (v :: k1). () => k2 v -> f v -> String) -> Bool -> Bool -> DMap k2 f -> String

-- | O(n). Test if the internal map structure is valid.
valid :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). GCompare k2 => DMap k2 f -> Bool
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). (Data.GADT.Internal.GEq k2, Data.Constraint.Extras.Has' GHC.Classes.Eq k2 f) => GHC.Classes.Eq (Data.Dependent.Map.Internal.DMap k2 f)
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). Data.GADT.Internal.GCompare k2 => GHC.Internal.Base.Monoid (Data.Dependent.Map.Internal.DMap k2 f)
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). (Data.GADT.Internal.GCompare k2, Data.Constraint.Extras.Has' GHC.Classes.Eq k2 f, Data.Constraint.Extras.Has' GHC.Classes.Ord k2 f) => GHC.Classes.Ord (Data.Dependent.Map.Internal.DMap k2 f)
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). (Data.GADT.Internal.GCompare k2, Data.GADT.Internal.GRead k2, Data.Constraint.Extras.Has' GHC.Internal.Read.Read k2 f) => GHC.Internal.Read.Read (Data.Dependent.Map.Internal.DMap k2 f)
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). Data.GADT.Internal.GCompare k2 => GHC.Internal.Base.Semigroup (Data.Dependent.Map.Internal.DMap k2 f)
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). (Data.GADT.Internal.GShow k2, Data.Constraint.Extras.Has' GHC.Internal.Show.Show k2 f) => GHC.Internal.Show.Show (Data.Dependent.Map.Internal.DMap k2 f)

-- | Some functions for using lenses with DMap.
module Data.Dependent.Map.Lens

-- | These functions have been specialised for use with DMap but
--   without any of the specific lens types used so that we have
--   compatibility without needing the dependency just for these functions.
--   
--   This is equivalent to the at Lens' from
--   Control.Lens.At:
--   
--   
--   type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t
--   
--   at :: Index m -> Lens' m (Maybe (IxValue m))
--   
--   
--   So the type of dmat is equivalent to:
--   
--   
--   dmat :: GCompare k => Lens' (DMap k f) (Maybe (f v))
--   
--   
--   
--   >>> DMap.fromList [AInt :=> Identity 33, AFloat :=> Identity 3.5] & dmat AString ?~ "Hat"
--   DMap.fromList [AString :=> Identity "Hat", AInt :=> Identity 33, AFloat :=> Identity 3.5]
--   
--   
--   
--   >>> DMap.fromList [AString :=> Identity "Shoe", AInt :=> Identity 33, AFloat :=> Identity 3.5] ^? dmat AFloat
--   Just (AFloat :=> 3.5)
--   
dmat :: forall {k1} k2 f (v :: k1) g. (GCompare k2, Functor f) => k2 v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k2 g -> f (DMap k2 g)

-- | This is equivalent to the ix Traversal' from
--   Control.Lens.At:
--   
--   
--   type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t
--   
--   ix :: Index m -> Traversal' m (IxValue m)
--   
--   
--   So the type of dmix is equivalent to:
--   
--   
--   dmix :: GCompare k => k v -> Traversal' (DMap k f) (f v)
--   
--   
--   NB: Setting the value of this Traversal will only set
--   the value in dmix if it is already present.
--   
--   If you want to be able to insert missing values, you want
--   dmat.
--   
--   
--   >>> DMap.fromList [AString :=> Identity "Shoe", AInt :=> Identity 33, AFloat :=> Identity 3.5] & dmix AInt %~ f
--   DMap.fromList [AString :=> Identity "Shoe", AInt :=> Identity (f 33), AFloat :=> Identity 3.5]
--   
--   
--   
--   >>> DMap.fromList [AString :=> Identity "Shoe", AInt :=> Identity 33, AFloat :=> Identity 3.5] & dmix AString .~ "Hat"
--   DMap.fromList [AString :=> Identity "Hat", AInt :=> Identity 33, AFloat :=> Identity 3.5]
--   
--   
--   
--   >>> DMap.fromList [AString :=> Identity "Shoe", AInt :=> Identity 33, AFloat :=> Identity 3.5] ^? dmix AFloat
--   Just (AFloat :=> 3.5)
--   
--   
--   
--   >>> DMap.fromList [AString :=> Identity "Shoe", AFloat :=> Identity 3.5] ^? dmix AInt
--   Nothing
--   
dmix :: forall {k1} k2 f (v :: k1) g. (GCompare k2, Applicative f) => k2 v -> (g v -> f (g v)) -> DMap k2 g -> f (DMap k2 g)
