-- 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.0

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 k f
[Tip] :: DMap k f
[Bin] :: !Int -> !k v -> f v -> !DMap k f -> !DMap k f -> DMap k f

-- | <i>O(1)</i>. The empty map.
--   
--   <pre>
--   empty      == fromList []
--   size empty == 0
--   </pre>
empty :: DMap k 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 :: k v -> f v -> DMap k f

-- | <i>O(1)</i>. Is the map empty?
null :: DMap k f -> Bool

-- | <i>O(1)</i>. The number of elements in the map.
size :: DMap k 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 k f v. GCompare k => k v -> DMap k f -> Maybe (f v)
lookupAssoc :: forall k f v. GCompare k => Some k -> DMap k f -> Maybe (DSum k f)
combine :: GCompare k => k v -> f v -> DMap k f -> DMap k f -> DMap k f
insertMax :: k v -> f v -> DMap k f -> DMap k f
insertMin :: k v -> f v -> DMap k f -> DMap k f
merge :: DMap k f -> DMap k f -> DMap k f
glue :: DMap k f -> DMap k f -> DMap k 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 :: DMap k f -> (DSum k f, DMap k 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 k f. DMap k f -> Maybe (DSum k f, DMap k 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 k f. DMap k f -> Maybe (DSum k f, DMap k 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 :: DMap k f -> (DSum k f, DMap k f)
delta :: Int
ratio :: Int
balance :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
rotateL :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
rotateR :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
singleL :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
singleR :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
doubleL :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
doubleR :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
bin :: k v -> f v -> DMap k f -> DMap k f -> DMap k f
trim :: (Some k -> Ordering) -> (Some k -> Ordering) -> DMap k f -> DMap k f
trimLookupLo :: GCompare k => Some k -> (Some k -> Ordering) -> DMap k f -> (Maybe (DSum k f), DMap k f)
filterGt :: GCompare k => (Some k -> Ordering) -> DMap k f -> DMap k f
filterLt :: GCompare k => (Some k -> Ordering) -> DMap k f -> DMap k 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 k f

-- | <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>
(!) :: GCompare k => DMap k f -> k v -> f v
infixl 9 !

-- | Same as <a>difference</a>.
(\\) :: GCompare k => DMap k f -> DMap k f -> DMap k f
infixl 9 \\

-- | <i>O(1)</i>. Is the map empty?
null :: DMap k f -> Bool

-- | <i>O(1)</i>. The number of elements in the map.
size :: DMap k f -> Int

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

-- | <i>O(log n)</i>. Is the key not a member of the map? See also
--   <a>member</a>.
notMember :: GCompare k => k v -> DMap k 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 k f v. GCompare k => k v -> DMap k 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 :: GCompare k => f v -> k v -> DMap k f -> f v

-- | <i>O(1)</i>. The empty map.
--   
--   <pre>
--   empty      == fromList []
--   size empty == 0
--   </pre>
empty :: DMap k 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 :: k v -> f v -> DMap k 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 k f v. GCompare k => k v -> f v -> DMap k f -> DMap k 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 :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f

-- | Same as <a>insertWith</a>, but the combining function is applied
--   strictly. This is often the most desirable behavior.
insertWith' :: GCompare k => (f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k 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 k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k f

-- | Same as <a>insertWithKey</a>, but the combining function is applied
--   strictly.
insertWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> DMap k 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 k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> (Maybe (f v), DMap k f)

-- | <i>O(log n)</i>. A strict version of <a>insertLookupWithKey</a>.
insertLookupWithKey' :: forall k f v. GCompare k => (k v -> f v -> f v -> f v) -> k v -> f v -> DMap k f -> (Maybe (f v), DMap k 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 k f v. GCompare k => k v -> DMap k f -> DMap k 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 :: GCompare k => (f v -> f v) -> k v -> DMap k f -> DMap k 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 :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f

-- | <i>O(log n)</i>. A strict version of <a>adjustWithKey</a>.
adjustWithKey' :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k 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 :: GCompare k => (f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k 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 k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> DMap k 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 k f v. GCompare k => (k v -> f v -> Maybe (f v)) -> k v -> DMap k f -> (Maybe (f v), DMap k 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 k f v. GCompare k => (Maybe (f v) -> Maybe (f v)) -> k v -> DMap k f -> DMap k 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 k f v g. (GCompare k, Functor f) => k v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k g -> f (DMap k 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 :: GCompare k => DMap k f -> DMap k f -> DMap k f

-- | <i>O(n+m)</i>. Union with a combining function.
unionWithKey :: GCompare k => (forall v. k v -> f v -> f v -> f v) -> DMap k f -> DMap k f -> DMap k f

-- | The union of a list of maps: (<tt><a>unions</a> == <a>foldl</a>
--   <a>union</a> <a>empty</a></tt>).
unions :: GCompare k => [DMap k f] -> DMap k 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 k => (forall v. k v -> f v -> f v -> f v) -> [DMap k f] -> DMap k 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 :: GCompare k => DMap k f -> DMap k g -> DMap k 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 k => (forall v. k v -> f v -> g v -> Maybe (f v)) -> DMap k f -> DMap k g -> DMap k 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 :: GCompare k => DMap k f -> DMap k f -> DMap k f

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

-- | <i>O(n)</i>. Map a function over all values in the map.
map :: (forall v. f v -> g v) -> DMap k f -> DMap k 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 :: DMap k f -> (forall v. f v -> g v) -> DMap k g

-- | <i>O(n)</i>. Map a function over all values in the map.
mapWithKey :: (forall v. k v -> f v -> g v) -> DMap k f -> DMap k 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 k f -> (forall v. k v -> f v -> g v) -> DMap k 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_ :: Applicative t => (forall v. k v -> f v -> t ()) -> DMap k 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_ :: Applicative t => DMap k f -> (forall v. k 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 :: Applicative t => (forall v. k v -> f v -> t (g v)) -> DMap k f -> t (DMap k 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 :: Applicative t => DMap k f -> (forall v. k v -> f v -> t (g v)) -> t (DMap k 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. a -> k v -> f v -> (a, g v)) -> a -> DMap k f -> (a, DMap k 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. a -> k v -> f v -> (a, g v)) -> a -> DMap k f -> (a, DMap k 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. k2 v -> f v -> f v -> f v) -> (forall v. 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 v. 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. k v -> f v -> b -> b) -> b -> DMap k f -> b

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

-- | <i>O(n)</i>. Pre-order fold. The function will be applied from the
--   highest value to the lowest.
foldlWithKey :: (forall v. b -> k v -> f v -> b) -> b -> DMap k 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 :: DMap k f -> [Some k]

-- | <i>O(n)</i>. Return all key/value pairs in the map in ascending key
--   order.
assocs :: DMap k f -> [DSum k f]

-- | <i>O(n)</i>. Convert to a list of key/value pairs.
toList :: DMap k f -> [DSum k 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 :: GCompare k => [DSum k f] -> DMap k 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 k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> DMap k f

-- | <i>O(n)</i>. Convert to an ascending list.
toAscList :: DMap k f -> [DSum k f]

-- | <i>O(n)</i>. Convert to a descending list.
toDescList :: DMap k f -> [DSum k 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 :: GEq k => [DSum k f] -> DMap k 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 k => (forall v. k v -> f v -> f v -> f v) -> [DSum k f] -> DMap k 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 :: [DSum k f] -> DMap k 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>
--   
--   <pre>
--   &gt;&gt;&gt; filter odd [1, 2, 3]
--   [1,3]
--   </pre>
filter :: (a -> Bool) -> [a] -> [a]

-- | <i>O(n)</i>. Filter all keys/values that satisfy the predicate.
filterWithKey :: GCompare k => (forall v. k v -> f v -> Bool) -> DMap k f -> DMap k 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 k => (forall v. k v -> f v -> Bool) -> DMap k f -> (DMap k f, DMap k f)

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

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

-- | <i>O(n)</i>. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> results.
mapEitherWithKey :: GCompare k => (forall v. k v -> f v -> Either (g v) (h v)) -> DMap k f -> (DMap k g, DMap k 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 k f v. GCompare k => k v -> DMap k f -> (DMap k f, DMap k 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 k f v. GCompare k => k v -> DMap k f -> (DMap k f, Maybe (f v), DMap k f)

-- | <i>O(n+m)</i>. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> <tt>eqTagged</tt>)</tt>).
isSubmapOf :: forall k f. (GCompare k, Has' Eq k f) => DMap k f -> DMap k 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 k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k 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 k f. (GCompare k, Has' Eq k f) => DMap k f -> DMap k 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 k => (forall v. k v -> k v -> f v -> g v -> Bool) -> DMap k f -> DMap k 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 k f v. GCompare k => k v -> DMap k 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 :: GCompare k => k v -> DMap k 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 :: Int -> DMap k f -> DSum k f

-- | <i>O(log n)</i>. Update the element at <i>index</i>. Does nothing when
--   an invalid index is used.
updateAt :: (forall v. k v -> f v -> Maybe (f v)) -> Int -> DMap k f -> DMap k 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 :: Int -> DMap k f -> DMap k f

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

-- | <i>O(log n)</i>. The maximal key of the map. Calls <a>error</a> is the
--   map is empty.
findMax :: DMap k f -> DSum k f
lookupMin :: DMap k f -> Maybe (DSum k f)
lookupMax :: DMap k f -> Maybe (DSum k f)

-- | <i>O(log n)</i>. Delete the minimal key. Returns an empty map if the
--   map is empty.
deleteMin :: DMap k f -> DMap k f

-- | <i>O(log n)</i>. Delete the maximal key. Returns an empty map if the
--   map is empty.
deleteMax :: DMap k f -> DMap k 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 :: DMap k f -> (DSum k f, DMap k 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 :: DMap k f -> (DSum k f, DMap k f)

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

-- | <i>O(log n)</i>. Update the value at the maximal key.
updateMaxWithKey :: (forall v. k v -> f v -> Maybe (f v)) -> DMap k f -> DMap k 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 k f. DMap k f -> Maybe (DSum k f, DMap k 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 k f. DMap k f -> Maybe (DSum k f, DMap k 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 :: (GShow k, Has' Show k f) => DMap k 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. k v -> f v -> String) -> Bool -> Bool -> DMap k f -> String

-- | <i>O(n)</i>. Test if the internal map structure is valid.
valid :: GCompare k => DMap k f -> Bool
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). Data.GADT.Internal.GCompare k2 => GHC.Base.Monoid (Data.Dependent.Map.Internal.DMap k2 f)
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). Data.GADT.Internal.GCompare k2 => GHC.Base.Semigroup (Data.Dependent.Map.Internal.DMap k2 f)
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, 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.Read.Read k2 f) => GHC.Read.Read (Data.Dependent.Map.Internal.DMap k2 f)
instance forall k1 (k2 :: k1 -> *) (f :: k1 -> *). (Data.GADT.Internal.GShow k2, Data.Constraint.Extras.Has' GHC.Show.Show k2 f) => GHC.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 :: (GCompare k, Functor f) => k v -> (Maybe (g v) -> f (Maybe (g v))) -> DMap k g -> f (DMap k 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 :: (GCompare k, Applicative f) => k v -> (g v -> f (g v)) -> DMap k g -> f (DMap k g)
