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


-- | Dependent finite maps (partial dependent products)
--   
--   Dependent finite maps (partial dependent products)
@package dependent-map
@version 0.1.1.1

module Data.Dependent.Map

-- | Dependent maps: f 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>f</tt>, as are <tt>Tag</tt>s
--   from <a>Data.Dependent.Tag</a>.
--   
--   Semantically, <tt><a>DMap</a> f</tt> is equivalent to a set of
--   <tt><a>DSum</a> 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

-- | A basic dependent sum type; the first component is a tag that
--   specifies the type of the second; for example, think of a GADT such
--   as:
--   
--   <pre>
--   data Tag a where
--      AString :: Tag String
--      AnInt   :: Tag Int
--   </pre>
--   
--   Then, we have the following valid expressions of type <tt>DSum
--   Tag</tt>:
--   
--   <pre>
--   AString :=&gt; "hello!"
--   AnInt   :=&gt; 42
--   </pre>
--   
--   And we can write functions that consume <tt>DSum Tag</tt> values by
--   matching, such as:
--   
--   <pre>
--   toString :: DSum Tag -&gt; String
--   toString (AString :=&gt; str) = str
--   toString (AnInt   :=&gt; int) = show int
--   </pre>
--   
--   By analogy to the (key =&gt; value) construction for dictionary
--   entries in many dynamic languages, we use (key :=&gt; value) as the
--   constructor for dependent sums. The :=&gt; operator has very low
--   precedence and binds to the right, so if the <tt>Tag</tt> GADT is
--   extended with an additional constructor <tt>Rec :: Tag (DSum
--   Tag)</tt>, then <tt>Rec :=&gt; AnInt :=&gt; 3 + 4</tt> is parsed as
--   would be expected (<tt>Rec :=&gt; (AnInt :=&gt; (3 + 4))</tt>) and has
--   type <tt>DSum Tag</tt>. Its precedence is just above that of <a>$</a>,
--   so <tt>foo bar $ AString :=&gt; <a>eep</a></tt> is equivalent to
--   <tt>foo bar (AString :=&gt; <a>eep</a>)</tt>.
data DSum (tag :: * -> *) :: (* -> *) -> *
(:=>) :: !(tag a) -> a -> DSum tag

-- | A <a>Key</a> is just a wrapper for the true key type <tt>f</tt> which
--   hides the associated value type and presents the key's GADT-level
--   <a>GCompare</a> instance as a vanilla <a>Ord</a> instance so it can be
--   used in cases where we don't care about the associated value.
data Key f
Key :: !(f a) -> Key f

-- | Type class for orderable GADT-like structures. When 2 things are
--   equal, must return a witness that their parameter types are equal as
--   well (GEQ). |Type class for comparable GADT-like structures. When 2
--   things are equal, must return a witness that their parameter types are
--   equal as well (<a>GEQ</a>).
class GEq f => GCompare (f :: * -> *)
gcompare :: GCompare f => f a -> f b -> GOrdering a b

-- | A type for the result of comparing GADT constructors; the type
--   parameters of the GADT values being compared are included so that in
--   the case where they are equal their parameter types can be unified.
data GOrdering a b :: * -> * -> *
GLT :: GOrdering a b
GEQ :: GOrdering t t
GGT :: GOrdering a b

-- | <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 -> k v -> v

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

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

-- | <i>O(1)</i>. The number of elements in the map.
size :: DMap k -> 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 -> 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 -> 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 :: GCompare k => k v -> DMap k -> Maybe 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 => v -> k v -> DMap k -> v

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

-- | <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 -> v -> DMap k

-- | <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 :: GCompare k => k v -> v -> DMap k -> DMap k

-- | <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 => (v -> v -> v) -> k v -> v -> DMap k -> DMap k

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

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

-- | Same as <a>insertWithKey</a>, but the combining function is applied
--   strictly.
insertWithKey' :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> DMap k

-- | <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 :: GCompare k => (k v -> v -> v -> v) -> k v -> v -> DMap k -> (Maybe v, DMap k)

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

-- | <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 :: GCompare k => k v -> DMap k -> DMap k

-- | <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 => (v -> v) -> k v -> DMap k -> DMap k

-- | <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 -> v -> v) -> k v -> DMap k -> DMap k

-- | <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 => (v -> Maybe v) -> k v -> DMap k -> DMap k

-- | <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 :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> DMap k

-- | <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 :: GCompare k => (k v -> v -> Maybe v) -> k v -> DMap k -> (Maybe v, DMap k)

-- | <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 :: GCompare k => (Maybe v -> Maybe v) -> k v -> DMap k -> DMap k

-- | <i>O(n+m)</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>). The
--   implementation uses the efficient <i>hedge-union</i> algorithm.
--   Hedge-union is more efficient on (bigset `<a>union</a>` smallset).
union :: GCompare k => DMap k -> DMap k -> DMap k

-- | <i>O(n+m)</i>. Union with a combining function. The implementation
--   uses the efficient <i>hedge-union</i> algorithm. Hedge-union is more
--   efficient on (bigset `<a>union</a>` smallset).
unionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k

-- | 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] -> DMap k

-- | 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 -> v -> v -> v) -> [DMap k] -> DMap k

-- | <i>O(n+m)</i>. Difference of two maps. Return elements of the first
--   map not existing in the second map. The implementation uses an
--   efficient <i>hedge</i> algorithm comparable with <i>hedge-union</i>.
difference :: GCompare k => DMap k -> DMap k -> DMap k

-- | <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>. The implementation
--   uses an efficient <i>hedge</i> algorithm comparable with
--   <i>hedge-union</i>.
differenceWithKey :: GCompare k => (forall v. k v -> v -> v -> Maybe v) -> DMap k -> DMap k -> DMap k

-- | <i>O(n+m)</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 -> DMap k -> DMap k

-- | <i>O(n+m)</i>. Intersection with a combining function. Intersection is
--   more efficient on (bigset `<a>intersection</a>` smallset).
intersectionWithKey :: GCompare k => (forall v. k v -> v -> v -> v) -> DMap k -> DMap k -> DMap k

-- | <i>O(n)</i>. Map a function over all values in the map.
mapWithKey :: (forall v. k v -> v -> v) -> DMap k -> DMap k

-- | <i>O(n)</i>. The function <a>mapAccumLWithKey</a> threads an
--   accumulating argument throught the map in ascending order of keys.
mapAccumLWithKey :: (forall v. a -> k v -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)

-- | <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 -> v -> (a, v)) -> a -> DMap k -> (a, DMap k)

-- | <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 -> v -> v -> v) -> (forall v. k1 v -> k2 v) -> DMap k1 -> DMap k2

-- | <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 -> DMap k2

-- | <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 -> v -> b -> b) -> b -> DMap k -> 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 -> v -> b -> b) -> b -> DMap k -> 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 -> v -> b) -> b -> DMap k -> 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 -> [Key k]

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

-- | <i>O(n)</i>. Convert to a list of key/value pairs.
toList :: DMap k -> [DSum k]

-- | <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] -> DMap k

-- | <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 -> v -> v -> v) -> [DSum k] -> DMap k

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

-- | <i>O(n)</i>. Convert to a descending list.
toDescList :: DMap k -> [DSum k]

-- | <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] -> DMap k

-- | <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 -> v -> v -> v) -> [DSum k] -> DMap k

-- | <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] -> DMap k

-- | <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>
filter :: (a -> Bool) -> [a] -> [a]

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

-- | <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 -> v -> Bool) -> DMap k -> (DMap k, DMap k)

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

-- | <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 -> v -> Either v v) -> DMap k -> (DMap k, DMap k)

-- | <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 :: GCompare k => k v -> DMap k -> (DMap k, DMap k)

-- | <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 :: GCompare k => k v -> DMap k -> (DMap k, Maybe v, DMap k)

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

-- | <i>O(log n)</i>. Update the element at <i>index</i>. Calls
--   <a>error</a> when an invalid index is used.
updateAt :: (forall v. k v -> v -> Maybe v) -> Int -> DMap k -> DMap k

-- | <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 -> DMap k

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

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

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

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

-- | <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 -> (DSum k, DMap k)

-- | <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 -> (DSum k, DMap k)

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

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

-- | <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 :: DMap k -> Maybe (DSum k, DMap k)

-- | <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 :: DMap k -> Maybe (DSum k, DMap k)

-- | <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 :: ShowTag k => DMap k -> 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 -> v -> String) -> Bool -> Bool -> DMap k -> String

-- | <i>O(n)</i>. Test if the internal map structure is valid.
valid :: GCompare k => DMap k -> Bool
instance [safe] ShowTag k => Show (DMap k)
instance [safe] (GCompare f, ReadTag f) => Read (DMap f)
instance [safe] OrdTag k => Ord (DMap k)
instance [safe] EqTag k => Eq (DMap k)
instance [safe] GCompare k => Monoid (DMap k)
