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


-- | Dependent finite maps (partial dependent products)
--   
--   Provides a type called <tt>DMap</tt> which generalizes
--   <tt>Data.Map.Map</tt>, 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: <tt>k</tt> 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 <tt>k</tt>, as are <tt>Tag</tt>s
--   from <a>Data.Unique.Tag</a> in the 'prim-uniq' package.
--   
--   Semantically, <tt><a>DMap</a> k f</tt> is equivalent to a set of
--   <tt><a>DSum</a> k f</tt> where no two elements have the same tag.
--   
--   More informally, <a>DMap</a> is to dependent products as <a>Map</a> is
--   to <tt>(-&gt;)</tt>. 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

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

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

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

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

-- | <i>O(log n)</i>. Lookup the value at a key in the map.
--   
--   The function will return the corresponding value as <tt>(<a>Just</a>
--   value)</tt>, or <a>Nothing</a> 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

-- | <i>O(log n)</i>. Delete and find the minimal element.
--   
--   <pre>
--   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
--   </pre>
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)

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

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

-- | <i>O(log n)</i>. Delete and find the maximal element.
--   
--   <pre>
--   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
--   </pre>
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: <tt>k</tt> 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 <tt>k</tt>, as are <tt>Tag</tt>s
--   from <a>Data.Unique.Tag</a> in the 'prim-uniq' package.
--   
--   Semantically, <tt><a>DMap</a> k f</tt> is equivalent to a set of
--   <tt><a>DSum</a> k f</tt> where no two elements have the same tag.
--   
--   More informally, <a>DMap</a> is to dependent products as <a>Map</a> is
--   to <tt>(-&gt;)</tt>. 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)

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

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

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

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

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

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

-- | <i>O(log n)</i>. Lookup the value at a key in the map.
--   
--   The function will return the corresponding value as <tt>(<a>Just</a>
--   value)</tt>, or <a>Nothing</a> 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)

-- | <i>O(log n)</i>. The expression <tt>(<a>findWithDefault</a> def k
--   map)</tt> returns the value at key <tt>k</tt> or returns default value
--   <tt>def</tt> 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

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

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

-- | <i>O(log n)</i>. 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. <a>insert</a> is equivalent to <tt><a>insertWith</a>
--   <a>const</a></tt>.
insert :: forall {k1} k2 f (v :: k1). GCompare k2 => k2 v -> f v -> DMap k2 f -> DMap k2 f

-- | <i>O(log n)</i>. Insert with a function, combining new value and old
--   value. <tt><a>insertWith</a> f key value mp</tt> will insert the entry
--   <tt>key :=&gt; value</tt> into <tt>mp</tt> if key does not exist in
--   the map. If the key does exist, the function will insert the entry
--   <tt>key :=&gt; f new_value old_value</tt>.
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 <a>insertWith</a>, 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

-- | <i>O(log n)</i>. Insert with a function, combining key, new value and
--   old value. <tt><a>insertWithKey</a> f key value mp</tt> will insert
--   the entry <tt>key :=&gt; value</tt> into <tt>mp</tt> if key does not
--   exist in the map. If the key does exist, the function will insert the
--   entry <tt>key :=&gt; f key new_value old_value</tt>. Note that the key
--   passed to f is the same key passed to <a>insertWithKey</a>.
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 <a>insertWithKey</a>, 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

-- | <i>O(log n)</i>. Combines insert operation with old value retrieval.
--   The expression (<tt><a>insertLookupWithKey</a> f k x map</tt>) is a
--   pair where the first element is equal to (<tt><a>lookup</a> k
--   map</tt>) and the second element equal to (<tt><a>insertWithKey</a> f
--   k x map</tt>).
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)

-- | <i>O(log n)</i>. A strict version of <a>insertLookupWithKey</a>.
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)

-- | <i>O(log n)</i>. 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

-- | <i>O(log n)</i>. 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

-- | <i>O(log n)</i>. 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

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

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

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

-- | <i>O(log n)</i>. Lookup and update. See also <a>updateWithKey</a>. 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)

-- | <i>O(log n)</i>. The expression (<tt><a>alter</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alter</a>
--   can be used to insert, delete, or update a value in a <tt>Map</tt>. In
--   short : <tt><a>lookup</a> k (<a>alter</a> f k m) = f (<a>lookup</a> k
--   m)</tt>.
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 <a>alter</a> except the new value is returned in
--   some <a>Functor</a> <tt>f</tt>. In short : <tt>(v' -&gt; alter (const
--   v') k dm) <a>$</a> f (lookup k dm)</tt>
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)

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

-- | <i>O(n+m)</i>. 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: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
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:
--   (<tt><a>unionsWithKey</a> f == <a>foldl</a> (<a>unionWithKey</a> f)
--   <a>empty</a></tt>).
unionsWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> f v -> f v) -> [DMap k2 f] -> DMap k2 f

-- | <i>O(m * log (n/m + 1)), m &lt;= n</i>. 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

-- | <i>O(n+m)</i>. 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 <a>Nothing</a>, the element is discarded
--   (proper set difference). If it returns (<tt><a>Just</a> y</tt>), the
--   element is updated with a new value <tt>y</tt>.
differenceWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> g v -> Maybe (f v)) -> DMap k2 f -> DMap k2 g -> DMap k2 f

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

-- | <i>O(m * log (n/m + 1), m &lt;= n</i>. 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

-- | <i>O(n)</i>. 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

-- | <i>O(n)</i>. <tt><a>ffor</a> == <a>flip</a> <a>map</a></tt> except we
--   cannot actually use <a>flip</a> 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

-- | <i>O(n)</i>. 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

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

-- | <i>O(n)</i>. <tt><a>traverseWithKey</a> f m == <a>fromList</a>
--   <a>$</a> <a>traverse</a> ((k, v) -&gt; (,) k <a>$</a> f k v)
--   (<a>toList</a> m)</tt> That is, behaves exactly like a regular
--   <a>traverse</a> 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 ()

-- | <i>O(n)</i>. <tt><a>forWithKey</a> == <a>flip</a>
--   <a>traverseWithKey</a></tt> except we cannot actually use <a>flip</a>
--   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 ()

-- | <i>O(n)</i>. <tt><a>traverseWithKey</a> f m == <a>fromList</a>
--   <a>$</a> <a>traverse</a> ((k, v) -&gt; (,) k <a>$</a> f k v)
--   (<a>toList</a> m)</tt> That is, behaves exactly like a regular
--   <a>traverse</a> 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)

-- | <i>O(n)</i>. <tt><a>forWithKey</a> == <a>flip</a>
--   <a>traverseWithKey</a></tt> except we cannot actually use <a>flip</a>
--   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)

-- | <i>O(n)</i>. The function <a>mapAccumLWithKey</a> 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)

-- | <i>O(n)</i>. The function <a>mapAccumRWithKey</a> 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)

-- | <i>O(n*log n)</i>. <tt><a>mapKeysWith</a> c f s</tt> is the map
--   obtained by applying <tt>f</tt> to each key of <tt>s</tt>.
--   
--   The size of the result may be smaller if <tt>f</tt> maps two or more
--   distinct keys to the same new key. In this case the associated values
--   will be combined using <tt>c</tt>.
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

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

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

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

-- | <i>O(n)</i>. 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

-- | <i>O(n)</i>. 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

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

-- | <i>O(n)</i>. 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]

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

-- | <i>O(n*log n)</i>. Build a map from a list of key/value pairs. See
--   also <a>fromAscList</a>. 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

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

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

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

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

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

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

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

-- | <i>O(n)</i>. 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

-- | <i>O(n)</i>. 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 <a>split</a>.
partitionWithKey :: GCompare k2 => (forall (v :: k1). () => k2 v -> f v -> Bool) -> DMap k2 f -> (DMap k2 f, DMap k2 f)

-- | <i>O(n)</i>. Map values and collect the <a>Just</a> 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

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

-- | <i>O(n)</i>. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> 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)

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

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

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

-- | <i>O(n+m)</i>. The expression (<tt><a>isSubmapOfBy</a> f t1 t2</tt>)
--   returns <a>True</a> if all keys in <tt>t1</tt> are in tree
--   <tt>t2</tt>, and when <tt>f</tt> returns <a>True</a> 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

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

-- | <i>O(n+m)</i>. Is this a proper submap? (ie. a submap but not equal).
--   The expression (<tt><a>isProperSubmapOfBy</a> f m1 m2</tt>) returns
--   <a>True</a> when <tt>m1</tt> and <tt>m2</tt> are not equal, all keys
--   in <tt>m1</tt> are in <tt>m2</tt>, and when <tt>f</tt> returns
--   <a>True</a> 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

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

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

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

-- | <i>O(log n)</i>. Update the element at <i>index</i>. 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

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

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

-- | <i>O(log n)</i>. The maximal key of the map. Calls <a>error</a> 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)

-- | <i>O(log n)</i>. 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

-- | <i>O(log n)</i>. 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

-- | <i>O(log n)</i>. Delete and find the minimal element.
--   
--   <pre>
--   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
--   </pre>
deleteFindMin :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)

-- | <i>O(log n)</i>. Delete and find the maximal element.
--   
--   <pre>
--   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
--   </pre>
deleteFindMax :: forall {k1} (k2 :: k1 -> Type) (f :: k1 -> Type). DMap k2 f -> (DSum k2 f, DMap k2 f)

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

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

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

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

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

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

-- | <i>O(n)</i>. 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 <a>DMap</a>.
module Data.Dependent.Map.Lens

-- | These functions have been specialised for use with <a>DMap</a> but
--   without any of the specific <tt>lens</tt> types used so that we have
--   compatibility without needing the dependency just for these functions.
--   
--   This is equivalent to the <a>at</a> <a>Lens'</a> from
--   <a>Control.Lens.At</a>:
--   
--   <pre>
--   type Lens s t a b = forall f. Functor f =&gt; (a -&gt; f b) -&gt; s -&gt; f t
--   
--   at :: Index m -&gt; Lens' m (Maybe (IxValue m))
--   </pre>
--   
--   So the type of <a>dmat</a> is equivalent to:
--   
--   <pre>
--   dmat :: GCompare k =&gt; Lens' (DMap k f) (Maybe (f v))
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; DMap.fromList [AInt :=&gt; Identity 33, AFloat :=&gt; Identity 3.5] &amp; dmat AString ?~ "Hat"
--   DMap.fromList [AString :=&gt; Identity "Hat", AInt :=&gt; Identity 33, AFloat :=&gt; Identity 3.5]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; DMap.fromList [AString :=&gt; Identity "Shoe", AInt :=&gt; Identity 33, AFloat :=&gt; Identity 3.5] ^? dmat AFloat
--   Just (AFloat :=&gt; 3.5)
--   </pre>
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 <a>ix</a> <a>Traversal'</a> from
--   <a>Control.Lens.At</a>:
--   
--   <pre>
--   type Traversal s t a b = forall f. Applicative f =&gt; (a -&gt; f b) -&gt; s -&gt; f t
--   
--   ix :: Index m -&gt; Traversal' m (IxValue m)
--   </pre>
--   
--   So the type of <a>dmix</a> is equivalent to:
--   
--   <pre>
--   dmix :: GCompare k =&gt; k v -&gt; Traversal' (DMap k f) (f v)
--   </pre>
--   
--   <i>NB:</i> Setting the value of this <a>Traversal</a> will only set
--   the value in <a>dmix</a> if it is already present.
--   
--   If you want to be able to insert <i>missing</i> values, you want
--   <a>dmat</a>.
--   
--   <pre>
--   &gt;&gt;&gt; DMap.fromList [AString :=&gt; Identity "Shoe", AInt :=&gt; Identity 33, AFloat :=&gt; Identity 3.5] &amp; dmix AInt %~ f
--   DMap.fromList [AString :=&gt; Identity "Shoe", AInt :=&gt; Identity (f 33), AFloat :=&gt; Identity 3.5]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; DMap.fromList [AString :=&gt; Identity "Shoe", AInt :=&gt; Identity 33, AFloat :=&gt; Identity 3.5] &amp; dmix AString .~ "Hat"
--   DMap.fromList [AString :=&gt; Identity "Hat", AInt :=&gt; Identity 33, AFloat :=&gt; Identity 3.5]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; DMap.fromList [AString :=&gt; Identity "Shoe", AInt :=&gt; Identity 33, AFloat :=&gt; Identity 3.5] ^? dmix AFloat
--   Just (AFloat :=&gt; 3.5)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; DMap.fromList [AString :=&gt; Identity "Shoe", AFloat :=&gt; Identity 3.5] ^? dmix AInt
--   Nothing
--   </pre>
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)
