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


-- | Maps and sets of partial orders
--   
--   Maps (and sets) indexed by keys satisfying <a>PartialOrd</a>.
--   
--   The goal is to provide asymptotically better data structures than
--   simple association lists or lookup tables. Asymptotics depend on the
--   partial order used as keys, its width <i>w</i> specifically (the size
--   of the biggest anti-chain).
--   
--   For partial orders of great width, this package won't provide any
--   benefit over using association lists, so benchmark for your use-case!
@package pomaps
@version 0.0.1.0


-- | This module doesn't respect the PVP! Breaking changes may happen at
--   any minor version (&gt;= *.*.m.*)
module Data.POMap.Internal

-- | Allows us to abstract over value-strictness in a zero-cost manner. GHC
--   should always be able to specialise the two instances of this and
--   consequently inline <a>areWeStrict</a>.
--   
--   It's a little sad we can't just use regular singletons, for reasons
--   outlined <a>here</a>.
class SingIAreWeStrict (s :: AreWeStrict)
areWeStrict :: SingIAreWeStrict s => Proxy# s -> AreWeStrict

-- | Should be inlined and specialised at all call sites.
seq' :: SingIAreWeStrict s => Proxy# s -> a -> b -> b
seqList :: [a] -> [a]

-- | A map from partially-ordered keys <tt>k</tt> to values <tt>v</tt>.
data POMap k v
POMap :: !Int -> ![Map k v] -> POMap k v

-- | Internal smart constructor so that we can be sure that we are always
--   spine-strict, discard empty maps and have appropriate size
--   information.
mkPOMap :: [Map k v] -> POMap k v
chainDecomposition :: POMap k v -> [Map k v]

-- | &lt;math&gt;, where &lt;math&gt;.

-- | &lt;math&gt;, where &lt;math&gt;.

-- | &lt;math&gt;. The number of elements in this map.
size :: POMap k v -> Int

-- | &lt;math&gt;. The width &lt;math&gt; of the chain decomposition in the
--   internal data structure. This is always at least as big as the size of
--   the biggest possible anti-chain.
width :: POMap k v -> Int
foldEntry :: (Monoid m, PartialOrd k) => k -> (v -> m) -> POMap k v -> m

-- | &lt;math&gt;. Is the key a member of the map?
lookup :: PartialOrd k => k -> POMap k v -> Maybe v

-- | &lt;math&gt;. Is the key a member of the map? See also
--   <a>notMember</a>.
--   
--   <pre>
--   &gt;&gt;&gt; member 5 (fromList [(5,'a'), (3,'b')]) == True
--   True
--   
--   &gt;&gt;&gt; member 1 (fromList [(5,'a'), (3,'b')]) == False
--   True
--   </pre>
member :: PartialOrd k => k -> POMap k v -> Bool

-- | &lt;math&gt;. Is the key not a member of the map? See also
--   <a>member</a>.
--   
--   <pre>
--   &gt;&gt;&gt; notMember 5 (fromList [(5,'a'), (3,'b')]) == False
--   True
--   
--   &gt;&gt;&gt; notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--   True
--   </pre>
notMember :: PartialOrd k => k -> POMap k v -> Bool

-- | &lt;math&gt;. 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.
--   
--   <pre>
--   &gt;&gt;&gt; findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   True
--   
--   &gt;&gt;&gt; findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--   True
--   </pre>
findWithDefault :: PartialOrd k => v -> k -> POMap k v -> v
data RelationalOperator
LessThan :: RelationalOperator
LessEqual :: RelationalOperator
Equal :: RelationalOperator
GreaterEqual :: RelationalOperator
GreaterThan :: RelationalOperator
flipRelationalOperator :: RelationalOperator -> RelationalOperator
containsOrdering :: Ordering -> RelationalOperator -> Bool
comparePartial :: PartialOrd k => k -> k -> Maybe Ordering
addToAntichain :: PartialOrd k => RelationalOperator -> (k, v) -> [(k, v)] -> [(k, v)]
dedupAntichain :: PartialOrd k => RelationalOperator -> [(k, v)] -> [(k, v)]
lookupX :: PartialOrd k => RelationalOperator -> k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the largest set of keys smaller than the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLT 3  (fromList [(3,'a'), (5,'b')])
--   []
--   
--   &gt;&gt;&gt; lookupLT 9 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   </pre>
lookupLT :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the largest key smaller or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLE 2 (fromList [(3,'a'), (5,'b')])
--   []
--   
--   &gt;&gt;&gt; lookupLE 3 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   
--   &gt;&gt;&gt; lookupLE 10 (fromList [(3,'a'), (5,'b')])
--   [(5,'b')]
--   </pre>
lookupLE :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the smallest key greater or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGE 3 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   
--   &gt;&gt;&gt; lookupGE 5 (fromList [(3,'a'), (10,'b')])
--   [(10,'b')]
--   
--   &gt;&gt;&gt; lookupGE 6 (fromList [(3,'a'), (5,'b')])
--   []
--   </pre>
lookupGE :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the smallest key greater than the given one and
--   return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGT 5 (fromList [(3,'a'), (10,'b')])
--   [(10,'b')]
--   
--   &gt;&gt;&gt; lookupGT 5 (fromList [(3,'a'), (5,'b')])
--   []
--   </pre>
lookupGT :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. The empty map.
--   
--   <pre>
--   &gt;&gt;&gt; empty
--   fromList []
--   
--   &gt;&gt;&gt; size empty
--   0
--   </pre>
empty :: POMap k v
singleton :: SingIAreWeStrict s => Proxy# s -> k -> v -> POMap k v
insert :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> k -> v -> POMap k v -> POMap k v
insertWith :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v
insertLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> k -> v -> POMap k v -> (Maybe v, POMap k v)
keyedInsertAsAlter :: (k -> v -> v -> v) -> v -> k -> Maybe v -> Maybe v
data LookupResult a
Incomparable :: LookupResult a
NotFound :: a -> LookupResult a
Found :: a -> LookupResult a
overChains :: (Map k v -> LookupResult a) -> (Map k v -> b -> b) -> (a -> [Map k v] -> b) -> ([Map k v] -> b) -> POMap k v -> b

-- | &lt;math&gt;. Delete a key and its value from the map. When the key is
--   not a member of the map, the original map is returned.
--   
--   <pre>
--   &gt;&gt;&gt; delete 5 (fromList [(5,"a"), (3,"b")])
--   fromList [(3,"b")]
--   
--   &gt;&gt;&gt; delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; delete 5 empty
--   fromList []
--   </pre>
delete :: PartialOrd k => k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Simultaneous <a>delete</a> and <a>lookup</a>.
deleteLookup :: PartialOrd k => k -> POMap k v -> (Maybe v, POMap k v)
adjust :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v) -> k -> POMap k v -> POMap k v
adjustWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v) -> k -> POMap k v -> POMap k v
adjustLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v)
update :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> Maybe v) -> k -> POMap k v -> POMap k v
updateWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v
updateLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
alter :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v
alterChain :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> Map k v -> LookupResult (Map k v)
alterLookupWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)
alterLookupChain :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> Maybe v -> Maybe v) -> k -> Map k v -> LookupResult (Maybe v, Map k v)
alterF :: (Functor f, PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v)
alterFChain :: (Functor f, PartialOrd k, SingIAreWeStrict s) => Proxy# s -> k -> Map k v -> LookupResult ((Maybe v -> f (Maybe v)) -> f (Map k v))

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. 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> == <a>unionWith</a>
--   <a>const</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--   True
--   </pre>
union :: PartialOrd k => POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Union with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--   True
--   </pre>
unionWith :: PartialOrd k => (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Union with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
--   
--   &gt;&gt;&gt; unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
--   True
--   </pre>
unionWithKey :: PartialOrd k => (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of maps: (<tt><a>unions</a> == <a>foldl</a> <a>union</a>
--   <a>empty</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--        == fromList [(3, "b"), (5, "a"), (7, "C")]
--   :}
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--    unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
--        == fromList [(3, "B3"), (5, "A3"), (7, "C")]
--   :}
--   True
--   </pre>
unions :: PartialOrd k => [POMap k v] -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of maps, with a combining operation: (<tt><a>unionsWith</a> f ==
--   <a>foldl</a> (<a>unionWith</a> f) <a>empty</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; :{
--    unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--        == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
--   :}
--   True
--   </pre>
unionsWith :: PartialOrd k => (v -> v -> v) -> [POMap k v] -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference of two
--   maps. Return elements of the first map not existing in the second map.
--   
--   <pre>
--   &gt;&gt;&gt; difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(3,"b")]
--   </pre>
difference :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference with a
--   combining function. When two equal keys are encountered, the combining
--   function is applied to the values of these keys. If it returns
--   <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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
--   
--   &gt;&gt;&gt; differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
--   fromList [(3,"b:B")]
--   </pre>
differenceWith :: PartialOrd k => (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
--   
--   &gt;&gt;&gt; differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
--   fromList [(3,"3:b|B")]
--   </pre>
differenceWithKey :: PartialOrd k => (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection of two
--   maps. Return data in the first map for the keys existing in both maps.
--   (<tt><a>intersection</a> m1 m2 == <a>intersectionWith</a> <a>const</a>
--   m1 m2</tt>).
--   
--   <pre>
--   &gt;&gt;&gt; intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"a")]
--   </pre>
intersection :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"aA")]
--   </pre>
intersectionWith :: PartialOrd k => (a -> b -> c) -> POMap k a -> POMap k b -> POMap k c

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
--   
--   &gt;&gt;&gt; intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"5:a|A")]
--   </pre>
intersectionWithKey :: PartialOrd k => (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c
map :: SingIAreWeStrict s => Proxy# s -> (a -> b) -> POMap k a -> POMap k b
mapWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> b) -> POMap k a -> POMap k b
traverseWithKey :: (Applicative t, SingIAreWeStrict s) => Proxy# s -> (k -> a -> t b) -> POMap k a -> t (POMap k b)
mapAccum :: SingIAreWeStrict s => Proxy# s -> (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)
mapAccumWithKey :: SingIAreWeStrict s => Proxy# s -> (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

-- | &lt;math&gt;. <tt><a>mapKeys</a> 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 value at the
--   greatest of the original keys is retained.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
--   True
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(1,"c")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(3,"c")]
--   </pre>
mapKeys :: PartialOrd k2 => (k1 -> k2) -> POMap k1 v -> POMap k2 v
mapKeysWith :: (PartialOrd k2, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. <tt><a>mapKeysMonotonic</a> f s == <a>mapKeys</a> 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, for every chain <tt>ls</tt> in
--   <tt>s</tt> 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
--   </pre>
--   
--   This means that <tt>f</tt> maps distinct original keys to distinct
--   resulting keys. This function has better performance than
--   <a>mapKeys</a>.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeysMonotonic (\ k -&gt; k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
--   True
--   </pre>
mapKeysMonotonic :: (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. A strict version of <a>foldr</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   right-associative binary operator, such that <tt><a>foldrWithKey</a> f
--   z == <a>foldr</a> (<a>uncurry</a> f) z . <tt>toAscList</tt></tt>.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; keys map = foldrWithKey (\k x ks -&gt; k:ks) [] map
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   
--   &gt;&gt;&gt; foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
--   True
--   </pre>
foldrWithKey :: (k -> a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldrWithKey</a>. Each
--   application of the operator is evaluated before using the result in
--   the next application. This function is strict in the starting value.
foldrWithKey' :: (k -> a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldl</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   left-associative binary operator, such that <tt><a>foldlWithKey</a> f
--   z == <a>foldl</a> (\z' (kx, x) -&gt; f z' kx x) z .
--   <tt>toAscList</tt></tt>.
--   
--   <pre>
--   &gt;&gt;&gt; keys = reverse . foldlWithKey (\ks k x -&gt; k:ks) []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   
--   &gt;&gt;&gt; foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
--   True
--   </pre>
foldlWithKey :: (b -> k -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldlWithKey</a>. Each
--   application of the operator is evaluated before using the result in
--   the next application. This function is strict in the starting value.
foldlWithKey' :: (b -> k -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   monoid, such that
--   
--   <pre>
--   <a>foldMapWithKey</a> f = <a>fold</a> . <a>mapWithKey</a> f
--   </pre>
foldMapWithKey :: Monoid m => (k -> a -> m) -> POMap k a -> m

-- | &lt;math&gt;. Return all elements of the map in unspecified order.
--   
--   <pre>
--   &gt;&gt;&gt; elems (fromList [(5,"a"), (3,"b")])
--   ["b","a"]
--   
--   &gt;&gt;&gt; elems empty
--   []
--   </pre>
elems :: POMap k v -> [v]

-- | &lt;math&gt;. Return all keys of the map in unspecified order.
--   
--   <pre>
--   &gt;&gt;&gt; keys (fromList [(5,"a"), (3,"b")])
--   [3,5]
--   
--   &gt;&gt;&gt; keys empty
--   []
--   </pre>
keys :: POMap k v -> [k]

-- | &lt;math&gt;. Return all key/value pairs in the map in unspecified
--   order.
--   
--   <pre>
--   &gt;&gt;&gt; assocs (fromList [(5,"a"), (3,"b")])
--   [(3,"b"),(5,"a")]
--   
--   &gt;&gt;&gt; assocs empty
--   []
--   </pre>
assocs :: POMap k v -> [(k, v)]

-- | &lt;math&gt;. Return all key/value pairs in the map in unspecified
--   order.
--   
--   Currently, <tt>toList = <a>assocs</a></tt>.
toList :: POMap k v -> [(k, v)]

-- | Intentionally named this way, to disambiguate it from
--   <tt>fromList</tt>. This is so that we can doctest this module.
fromListImpl :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> [(k, v)] -> POMap k v
fromListWith :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (v -> v -> v) -> [(k, v)] -> POMap k v
fromListWithKey :: (PartialOrd k, SingIAreWeStrict s) => Proxy# s -> (k -> v -> v -> v) -> [(k, v)] -> POMap k v

-- | &lt;math&gt;. Filter all values that satisfy the predicate.
--   
--   <pre>
--   &gt;&gt;&gt; filter (&gt; "a") (fromList [(5,"a"), (3,"b")])
--   fromList [(3,"b")]
--   
--   &gt;&gt;&gt; filter (&gt; "x") (fromList [(5,"a"), (3,"b")])
--   fromList []
--   
--   &gt;&gt;&gt; filter (&lt; "a") (fromList [(5,"a"), (3,"b")])
--   fromList []
--   </pre>
filter :: (v -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Filter all keys/values that satisfy the predicate.
--   
--   <pre>
--   &gt;&gt;&gt; filterWithKey (\(Div k) _ -&gt; k &gt; 4) (fromList [(5,"a"), (3,"b")])
--   fromList [(5,"a")]
--   </pre>
filterWithKey :: (k -> v -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. 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 <tt>split</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; partition (&gt; "a") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b")], fromList [(5, "a")])
--   True
--   
--   &gt;&gt;&gt; partition (&lt; "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   True
--   
--   &gt;&gt;&gt; partition (&gt; "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--   True
--   </pre>
partition :: (v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. 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 <tt>split</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &gt; 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])
--   True
--   
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &lt; 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   True
--   
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &gt; 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--   True
--   </pre>
partitionWithKey :: (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. Take while a predicate on the keys holds. The user is
--   responsible for ensuring that for all keys <tt>j</tt> and <tt>k</tt>
--   in the map, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See note at
--   <a>spanAntitone</a>.
--   
--   <pre>
--   takeWhileAntitone p = <a>filterWithKey</a> (k _ -&gt; p k)
--   </pre>
takeWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Drop while a predicate on the keys holds. The user is
--   responsible for ensuring that for all keys <tt>j</tt> and <tt>k</tt>
--   in the map, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See note at
--   <a>spanAntitone</a>.
--   
--   <pre>
--   dropWhileAntitone p = <a>filterWithKey</a> (k -&gt; not (p k))
--   </pre>
dropWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Divide a map at the point where a predicate on the keys
--   stops holding. The user is responsible for ensuring that for all keys
--   <tt>j</tt> and <tt>k</tt> in the map, <tt>j &lt; k ==&gt; p j &gt;= p
--   k</tt>.
--   
--   <pre>
--   spanAntitone p xs = <a>partitionWithKey</a> (k _ -&gt; p k) xs
--   </pre>
--   
--   Note: if <tt>p</tt> is not actually antitone, then
--   <tt>spanAntitone</tt> will split the map at some <i>unspecified</i>
--   point where the predicate switches from holding to not holding (where
--   the predicate is seen to hold before the first key and to fail after
--   the last key).
spanAntitone :: (k -> Bool) -> POMap k v -> (POMap k v, POMap k v)
mapMaybe :: SingIAreWeStrict s => Proxy# s -> (a -> Maybe b) -> POMap k a -> POMap k b
mapMaybeWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> Maybe b) -> POMap k a -> POMap k b
traverseMaybeWithKey :: (Applicative f, SingIAreWeStrict s) => Proxy# s -> (k -> a -> f (Maybe b)) -> POMap k a -> f (POMap k b)
mapEither :: SingIAreWeStrict s => Proxy# s -> (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)
mapEitherWithKey :: SingIAreWeStrict s => Proxy# s -> (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

-- | &lt;math&gt;. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> (==)</tt>).
isSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

-- | &lt;math&gt;. 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 values. For example, the following expressions are
--   all <a>True</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
--   True
--   
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
--   True
--   </pre>
--   
--   But the following are all <a>False</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(2,'a')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isSubmapOfBy (&lt;)  (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
--   False
--   </pre>
isSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

-- | &lt;math&gt;. Is this a proper submap? (ie. a submap but not equal).
--   Defined as (<tt><a>isProperSubmapOf</a> = <a>isProperSubmapOfBy</a>
--   (==)</tt>).
isProperSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

-- | &lt;math&gt;. 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 values. For example, the
--   following expressions are all <a>True</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   </pre>
--   
--   But the following are all <a>False</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
--   False
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (&lt;)  (fromList [(1,'a')])         (fromList [(1,'a'),(2,'b')])
--   False
--   </pre>
isProperSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

-- | &lt;math&gt;. The minimal keys of the map.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupMin (fromList [(6,"a"), (3,"b")])
--   [(3,"b")]
--   
--   &gt;&gt;&gt; lookupMin empty
--   []
--   </pre>
lookupMin :: PartialOrd k => POMap k v -> [(k, v)]

-- | &lt;math&gt;. The maximal keys of the map.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupMax (fromList [(6,"a"), (3,"b")])
--   [(6,"a")]
--   
--   &gt;&gt;&gt; lookupMax empty
--   []
--   </pre>
lookupMax :: PartialOrd k => POMap k v -> [(k, v)]
instance GHC.Base.Functor Data.POMap.Internal.LookupResult
instance GHC.Show.Show a => GHC.Show.Show (Data.POMap.Internal.LookupResult a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.POMap.Internal.LookupResult a)
instance GHC.Show.Show Data.POMap.Internal.RelationalOperator
instance GHC.Classes.Ord Data.POMap.Internal.RelationalOperator
instance GHC.Classes.Eq Data.POMap.Internal.RelationalOperator
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.POMap.Internal.LookupResult a)
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Data.POMap.Internal.POMap k v)
instance (Algebra.PartialOrd.PartialOrd k, GHC.Read.Read k, GHC.Read.Read e) => GHC.Read.Read (Data.POMap.Internal.POMap k e)
instance (Algebra.PartialOrd.PartialOrd k, GHC.Classes.Eq v) => GHC.Classes.Eq (Data.POMap.Internal.POMap k v)
instance (Algebra.PartialOrd.PartialOrd k, Algebra.PartialOrd.PartialOrd v) => Algebra.PartialOrd.PartialOrd (Data.POMap.Internal.POMap k v)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData v) => Control.DeepSeq.NFData (Data.POMap.Internal.POMap k v)
instance Algebra.PartialOrd.PartialOrd k => GHC.Exts.IsList (Data.POMap.Internal.POMap k v)
instance GHC.Base.Functor (Data.POMap.Internal.POMap k)
instance Data.Foldable.Foldable (Data.POMap.Internal.POMap k)
instance Data.Traversable.Traversable (Data.POMap.Internal.POMap k)
instance Data.POMap.Internal.SingIAreWeStrict 'Data.Map.Internal.Strict
instance Data.POMap.Internal.SingIAreWeStrict 'Data.Map.Internal.Lazy


-- | A reasonably efficient implementation of partially ordered maps from
--   keys to values (dictionaries).
--   
--   The API of this module is lazy in both the keys and the values. If you
--   need value-strict maps, use <a>Data.POMap.Strict</a> instead. The
--   <a>POMap</a> type is shared between the lazy and strict modules,
--   meaning that the same <a>POMap</a> value can be passed to functions in
--   both modules (although that is rarely needed).
--   
--   These modules are intended to be imported qualified, to avoid name
--   clashes with Prelude functions, e.g.
--   
--   <pre>
--   import qualified Data.POMap.Lazy as POMap
--   </pre>
--   
--   The implementation of <a>POMap</a> is based on a decomposition of
--   chains (totally ordered submaps), inspired by <a>"Sorting and
--   Selection in Posets"</a>.
--   
--   Operation comments contain the operation time complexity in <a>Big-O
--   notation</a> and commonly refer to two characteristics of the poset
--   from which keys are drawn: The number of elements in the map
--   &lt;math&gt; and the <i>width</i> &lt;math&gt; of the poset, referring
--   to the size of the biggest anti-chain (set of incomparable elements).
--   
--   Generally speaking, lookup and mutation operations incur an additional
--   factor of &lt;math&gt; compared to their counter-parts in
--   <a>Data.Map.Lazy</a>.
--   
--   Note that for practical applications, the width of the poset should be
--   in the order of &lt;math&gt;, otherwise a simple lookup list is
--   asymptotically superior. Even if that holds, the constants might be
--   too big to be useful for any &lt;math&gt; that can can happen in
--   practice.
--   
--   The following examples assume the following definitions for a map on
--   the divisibility relation on <a>Int</a>egers:
--   
--   <pre>
--   {-# LANGUAGE GeneralizedNewtypeDeriving #-}
--   
--   import           Algebra.PartialOrd
--   import           Data.POMap.Lazy (POMap)
--   import qualified Data.POMap.Lazy as POMap
--   
--   newtype Divisibility
--     = Div Int
--     deriving (Eq, Read, Show, Num)
--   
--   default (Divisibility)
--   
--   instance <a>PartialOrd</a> Divisibility where
--     Div a `leq` Div b = b `mod` a == 0
--   
--   type DivMap a = POMap Divisibility a
--   
--   -- We want integer literals to be interpreted as <tt>Divisibility</tt>s
--   -- and default <tt>empty</tt>s to DivMap String.
--   default (Divisibility, DivMap String)
--   </pre>
--   
--   <tt>Divisility</tt> is actually an example for a <a>PartialOrd</a>
--   that should not be used as keys of <a>POMap</a>. Its width is
--   &lt;math&gt;!
module Data.POMap.Lazy

-- | A map from partially-ordered keys <tt>k</tt> to values <tt>v</tt>.
data POMap k v

-- | Test whether the structure is empty. The default implementation is
--   optimized for structures that are similar to cons-lists, because there
--   is no general way to do better.
null :: Foldable t => forall a. () => t a -> Bool

-- | &lt;math&gt;. The number of elements in this map.
size :: POMap k v -> Int

-- | &lt;math&gt;. The width &lt;math&gt; of the chain decomposition in the
--   internal data structure. This is always at least as big as the size of
--   the biggest possible anti-chain.
width :: POMap k v -> Int

-- | &lt;math&gt;. Is the key a member of the map? See also
--   <a>notMember</a>.
--   
--   <pre>
--   &gt;&gt;&gt; member 5 (fromList [(5,'a'), (3,'b')]) == True
--   True
--   
--   &gt;&gt;&gt; member 1 (fromList [(5,'a'), (3,'b')]) == False
--   True
--   </pre>
member :: PartialOrd k => k -> POMap k v -> Bool

-- | &lt;math&gt;. Is the key not a member of the map? See also
--   <a>member</a>.
--   
--   <pre>
--   &gt;&gt;&gt; notMember 5 (fromList [(5,'a'), (3,'b')]) == False
--   True
--   
--   &gt;&gt;&gt; notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--   True
--   </pre>
notMember :: PartialOrd k => k -> POMap k v -> Bool

-- | &lt;math&gt;. Is the key a member of the map?
lookup :: PartialOrd k => k -> POMap k v -> Maybe v

-- | &lt;math&gt;. 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.
--   
--   <pre>
--   &gt;&gt;&gt; findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   True
--   
--   &gt;&gt;&gt; findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--   True
--   </pre>
findWithDefault :: PartialOrd k => v -> k -> POMap k v -> v

-- | &lt;math&gt;. Find the largest set of keys smaller than the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLT 3  (fromList [(3,'a'), (5,'b')])
--   []
--   
--   &gt;&gt;&gt; lookupLT 9 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   </pre>
lookupLT :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the smallest key greater than the given one and
--   return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGT 5 (fromList [(3,'a'), (10,'b')])
--   [(10,'b')]
--   
--   &gt;&gt;&gt; lookupGT 5 (fromList [(3,'a'), (5,'b')])
--   []
--   </pre>
lookupGT :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the largest key smaller or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLE 2 (fromList [(3,'a'), (5,'b')])
--   []
--   
--   &gt;&gt;&gt; lookupLE 3 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   
--   &gt;&gt;&gt; lookupLE 10 (fromList [(3,'a'), (5,'b')])
--   [(5,'b')]
--   </pre>
lookupLE :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the smallest key greater or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGE 3 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   
--   &gt;&gt;&gt; lookupGE 5 (fromList [(3,'a'), (10,'b')])
--   [(10,'b')]
--   
--   &gt;&gt;&gt; lookupGE 6 (fromList [(3,'a'), (5,'b')])
--   []
--   </pre>
lookupGE :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. The empty map.
--   
--   <pre>
--   &gt;&gt;&gt; empty
--   fromList []
--   
--   &gt;&gt;&gt; size empty
--   0
--   </pre>
empty :: POMap k v

-- | &lt;math&gt;. A map with a single element.
--   
--   <pre>
--   &gt;&gt;&gt; singleton 1 'a'
--   fromList [(1,'a')]
--   
--   &gt;&gt;&gt; size (singleton 1 'a')
--   1
--   </pre>
singleton :: k -> v -> POMap k v

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'x')]
--   True
--   
--   &gt;&gt;&gt; insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'a'), (7,'x')]
--   True
--   
--   &gt;&gt;&gt; insert 5 'x' empty                         == singleton 5 'x'
--   True
--   </pre>
insert :: PartialOrd k => k -> v -> POMap k v -> POMap k v

-- | &lt;math&gt;. Insert with a function, combining new value and old
--   value. <tt><a>insertWith</a> f key value mp</tt> will insert the pair
--   (key, value) into <tt>mp</tt> if key does not exist in the map. If the
--   key does exist, the function will insert the pair <tt>(key, f
--   new_value old_value)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
--   True
--   
--   &gt;&gt;&gt; insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
--   True
--   
--   &gt;&gt;&gt; insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
--   True
--   </pre>
insertWith :: PartialOrd k => (v -> v -> v) -> k -> v -> POMap k v -> POMap k v

-- | &lt;math&gt;. Insert with a function, combining key, new value and old
--   value. <tt><a>insertWithKey</a> f key value mp</tt> will insert the
--   pair (key, value) into <tt>mp</tt> if key does not exist in the map.
--   If the key does exist, the function will insert the pair <tt>(key,f
--   key new_value old_value)</tt>. Note that the key passed to f is the
--   same key passed to <a>insertWithKey</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
--   True
--   
--   &gt;&gt;&gt; insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
--   True
--   
--   &gt;&gt;&gt; insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
--   True
--   </pre>
insertWithKey :: PartialOrd k => (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v

-- | &lt;math&gt;. 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>).
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
--   True
--   
--   &gt;&gt;&gt; insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
--   True
--   
--   &gt;&gt;&gt; insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")
--   True
--   </pre>
--   
--   This is how to define <tt>insertLookup</tt> using
--   <tt>insertLookupWithKey</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; let insertLookup kx x t = insertLookupWithKey (\_ a _ -&gt; a) kx x t
--   
--   &gt;&gt;&gt; insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
--   True
--   
--   &gt;&gt;&gt; insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])
--   True
--   </pre>
insertLookupWithKey :: PartialOrd k => (k -> v -> v -> v) -> k -> v -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. Delete a key and its value from the map. When the key is
--   not a member of the map, the original map is returned.
--   
--   <pre>
--   &gt;&gt;&gt; delete 5 (fromList [(5,"a"), (3,"b")])
--   fromList [(3,"b")]
--   
--   &gt;&gt;&gt; delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; delete 5 empty
--   fromList []
--   </pre>
delete :: PartialOrd k => k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Simultaneous <a>delete</a> and <a>lookup</a>.
deleteLookup :: PartialOrd k => k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. Adjust 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.
--   
--   <pre>
--   &gt;&gt;&gt; adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
--   True
--   
--   &gt;&gt;&gt; adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; adjust ("new " ++) 7 empty                         == empty
--   True
--   </pre>
adjust :: PartialOrd k => (v -> v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Adjust 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.
--   
--   <pre>
--   &gt;&gt;&gt; let f key x = (show key) ++ ":new " ++ x
--   
--   &gt;&gt;&gt; adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
--   True
--   
--   &gt;&gt;&gt; adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; adjustWithKey f 7 empty                         == empty
--   True
--   </pre>
adjustWithKey :: PartialOrd k => (k -> v -> v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Adjust a value at a specific key with the result of the
--   provided function and simultaneously look up the old value at that
--   key. When the key is not a member of the map, the original map is
--   returned.
--   
--   <pre>
--   &gt;&gt;&gt; let f key old_value = show key ++ ":" ++ show 42 ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; adjustLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:42|a")])
--   True
--   
--   &gt;&gt;&gt; adjustLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
--   True
--   
--   &gt;&gt;&gt; adjustLookupWithKey f 5 empty                         == (Nothing,  empty)
--   True
--   </pre>
adjustLookupWithKey :: PartialOrd k => (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f x = if x == "a" then Just "new a" else Nothing
--   
--   &gt;&gt;&gt; update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
--   True
--   
--   &gt;&gt;&gt; update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--   True
--   </pre>
update :: PartialOrd k => (v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
--   
--   &gt;&gt;&gt; updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
--   True
--   
--   &gt;&gt;&gt; updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--   True
--   </pre>
updateWithKey :: PartialOrd k => (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Lookup and update. See also <a>updateWithKey</a>.
--   <b>Warning</b>: Contrary to <a>Data.Map.Lazy</a>, the lookup does
--   <i>not</i> return the updated value, but the old value. This is
--   consistent with <a>insertLookupWithKey</a> and also
--   <tt>Data.IntMap.Lazy.<a>updateLookupWithKey</a></tt>.
--   
--   Re-apply the updating function to the looked-up value once more to get
--   the value in the map, like in the last example:
--   
--   <pre>
--   &gt;&gt;&gt; let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
--   
--   &gt;&gt;&gt; updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
--   True
--   
--   &gt;&gt;&gt; updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
--   True
--   
--   &gt;&gt;&gt; updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
--   True
--   
--   &gt;&gt;&gt; fst (updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])) &gt;&gt;= f 5
--   Just "5:new a"
--   </pre>
updateLookupWithKey :: PartialOrd k => (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f _ = Nothing
--   
--   &gt;&gt;&gt; alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--   True
--   
--   &gt;&gt;&gt; let f _ = Just "c"
--   
--   &gt;&gt;&gt; alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
--   True
--   
--   &gt;&gt;&gt; alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
--   True
--   </pre>
alter :: PartialOrd k => (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. The expression (<tt><a>alterWithKey</a> f k map</tt>)
--   alters the value <tt>x</tt> at <tt>k</tt>, or absence thereof.
--   <a>alterWithKey</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 k (<a>lookup</a> k m)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; let f _ _ = Nothing
--   
--   &gt;&gt;&gt; alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--   True
--   
--   &gt;&gt;&gt; let f k _ = Just (show k ++ ":c")
--   
--   &gt;&gt;&gt; alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "7:c")]
--   True
--   
--   &gt;&gt;&gt; alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:c")]
--   True
--   </pre>
alterWithKey :: PartialOrd k => (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Lookup and alteration. See also <a>alterWithKey</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let f k x = if x == Nothing then Just ((show k) ++ ":new a") else Nothing
--   
--   &gt;&gt;&gt; alterLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b")])
--   True
--   
--   &gt;&gt;&gt; alterLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "7:new a")])
--   True
--   
--   &gt;&gt;&gt; alterLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
--   True
--   </pre>
alterLookupWithKey :: PartialOrd k => (k -> Maybe v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. The expression (<tt><a>alterF</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alterF</a>
--   can be used to inspect, insert, delete, or update a value in a
--   <tt>Map</tt>. In short: <tt><a>lookup</a> k &lt;$&gt; <a>alterF</a> f
--   k m = f (<a>lookup</a> k m)</tt>.
--   
--   Example:
--   
--   <pre>
--   interactiveAlter :: Divibility -&gt; DivMap String -&gt; IO (DivMap String)
--   interactiveAlter k m = alterF f k m where
--     f Nothing -&gt; do
--        putStrLn $ show k ++
--            " was not found in the map. Would you like to add it?"
--        getUserResponse1 :: IO (Maybe String)
--     f (Just old) -&gt; do
--        putStrLn "The key is currently bound to " ++ show old ++
--            ". Would you like to change or delete it?"
--        getUserresponse2 :: IO (Maybe String)
--   </pre>
--   
--   <a>alterF</a> is the most general operation for working with an
--   individual key that may or may not be in a given map. When used with
--   trivial functors like <tt>Identity</tt> and <tt>Const</tt>, it is
--   often slightly slower than more specialized combinators like
--   <a>lookup</a> and <a>insert</a>. However, when the functor is
--   non-trivial and key comparison is not particularly cheap, it is the
--   fastest way.
alterF :: (Functor f, PartialOrd k) => (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v)

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. 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> == <a>unionWith</a>
--   <a>const</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--   True
--   </pre>
union :: PartialOrd k => POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Union with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--   True
--   </pre>
unionWith :: PartialOrd k => (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Union with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
--   
--   &gt;&gt;&gt; unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
--   True
--   </pre>
unionWithKey :: PartialOrd k => (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of maps: (<tt><a>unions</a> == <a>foldl</a> <a>union</a>
--   <a>empty</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--        == fromList [(3, "b"), (5, "a"), (7, "C")]
--   :}
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--    unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
--        == fromList [(3, "B3"), (5, "A3"), (7, "C")]
--   :}
--   True
--   </pre>
unions :: PartialOrd k => [POMap k v] -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of maps, with a combining operation: (<tt><a>unionsWith</a> f ==
--   <a>foldl</a> (<a>unionWith</a> f) <a>empty</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; :{
--    unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--        == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
--   :}
--   True
--   </pre>
unionsWith :: PartialOrd k => (v -> v -> v) -> [POMap k v] -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference of two
--   maps. Return elements of the first map not existing in the second map.
--   
--   <pre>
--   &gt;&gt;&gt; difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(3,"b")]
--   </pre>
difference :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference with a
--   combining function. When two equal keys are encountered, the combining
--   function is applied to the values of these keys. If it returns
--   <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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
--   
--   &gt;&gt;&gt; differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
--   fromList [(3,"b:B")]
--   </pre>
differenceWith :: PartialOrd k => (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
--   
--   &gt;&gt;&gt; differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
--   fromList [(3,"3:b|B")]
--   </pre>
differenceWithKey :: PartialOrd k => (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection of two
--   maps. Return data in the first map for the keys existing in both maps.
--   (<tt><a>intersection</a> m1 m2 == <a>intersectionWith</a> <a>const</a>
--   m1 m2</tt>).
--   
--   <pre>
--   &gt;&gt;&gt; intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"a")]
--   </pre>
intersection :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"aA")]
--   </pre>
intersectionWith :: PartialOrd k => (a -> b -> c) -> POMap k a -> POMap k b -> POMap k c

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
--   
--   &gt;&gt;&gt; intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"5:a|A")]
--   </pre>
intersectionWithKey :: PartialOrd k => (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c

-- | &lt;math&gt;. Map a function over all values in the map.
--   
--   <pre>
--   &gt;&gt;&gt; map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--   True
--   </pre>
map :: (a -> b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. Map a function over all values in the map.
--   
--   <pre>
--   &gt;&gt;&gt; let f key x = (show key) ++ ":" ++ x
--   
--   &gt;&gt;&gt; mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--   True
--   </pre>
mapWithKey :: (k -> a -> b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. <tt><a>traverseWithKey</a> f m == <a>fromList</a>
--   <a>$</a> <a>traverse</a> ((k, v) -&gt; (v' -&gt; v' <a>seq</a> (k,v'))
--   <a>$</a> f k v) (<tt>toList</tt> m)</tt> That is, it behaves much like
--   a regular <a>traverse</a> except that the traversing function also has
--   access to the key associated with a value and the values are forced
--   before they are installed in the result map.
--   
--   <pre>
--   &gt;&gt;&gt; traverseWithKey (\(Div k) v -&gt; if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])
--   True
--   
--   &gt;&gt;&gt; traverseWithKey (\(Div k) v -&gt; if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')])           == Nothing
--   True
--   </pre>
traverseWithKey :: Applicative t => (k -> a -> t b) -> POMap k a -> t (POMap k b)

-- | &lt;math&gt;. Traverse keys/values and collect the <a>Just</a>
--   results.
traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> POMap k a -> t (POMap k b)

-- | &lt;math&gt;. The function <a>mapAccum</a> threads an accumulating
--   argument through the map in ascending order of keys.
--   
--   <pre>
--   &gt;&gt;&gt; let f a b = (a ++ b, b ++ "X")
--   
--   &gt;&gt;&gt; mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--   True
--   </pre>
mapAccum :: (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

-- | &lt;math&gt;. The function <a>mapAccumWithKey</a> threads an
--   accumulating argument through the map in ascending order of keys.
--   
--   <pre>
--   &gt;&gt;&gt; let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
--   
--   &gt;&gt;&gt; mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
--   True
--   </pre>
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

-- | &lt;math&gt;. <tt><a>mapKeys</a> 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 value at the
--   greatest of the original keys is retained.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
--   True
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(1,"c")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(3,"c")]
--   </pre>
mapKeys :: PartialOrd k2 => (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. <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>.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeysWith (+) (\ _ -&gt; 1) (fromList [(1,1), (2,2), (3,3), (4,4)]) == singleton 1 10
--   True
--   
--   &gt;&gt;&gt; mapKeysWith (+) (\ _ -&gt; 3) (fromList [(1,1), (2,1), (3,1), (4,1)]) == singleton 3 4
--   True
--   </pre>
mapKeysWith :: PartialOrd k2 => (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. <tt><a>mapKeysMonotonic</a> f s == <a>mapKeys</a> 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, for every chain <tt>ls</tt> in
--   <tt>s</tt> 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
--   </pre>
--   
--   This means that <tt>f</tt> maps distinct original keys to distinct
--   resulting keys. This function has better performance than
--   <a>mapKeys</a>.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeysMonotonic (\ k -&gt; k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
--   True
--   </pre>
mapKeysMonotonic :: (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   right-associative binary operator, such that <tt><a>foldrWithKey</a> f
--   z == <a>foldr</a> (<a>uncurry</a> f) z . <tt>toAscList</tt></tt>.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; keys map = foldrWithKey (\k x ks -&gt; k:ks) [] map
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   
--   &gt;&gt;&gt; foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
--   True
--   </pre>
foldrWithKey :: (k -> a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   left-associative binary operator, such that <tt><a>foldlWithKey</a> f
--   z == <a>foldl</a> (\z' (kx, x) -&gt; f z' kx x) z .
--   <tt>toAscList</tt></tt>.
--   
--   <pre>
--   &gt;&gt;&gt; keys = reverse . foldlWithKey (\ks k x -&gt; k:ks) []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   
--   &gt;&gt;&gt; foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
--   True
--   </pre>
foldlWithKey :: (b -> k -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   monoid, such that
--   
--   <pre>
--   <a>foldMapWithKey</a> f = <a>fold</a> . <a>mapWithKey</a> f
--   </pre>
foldMapWithKey :: Monoid m => (k -> a -> m) -> POMap k a -> m

-- | &lt;math&gt;. A strict version of <a>foldr</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldl</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldrWithKey</a>. Each
--   application of the operator is evaluated before using the result in
--   the next application. This function is strict in the starting value.
foldrWithKey' :: (k -> a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldlWithKey</a>. Each
--   application of the operator is evaluated before using the result in
--   the next application. This function is strict in the starting value.
foldlWithKey' :: (b -> k -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Return all elements of the map in unspecified order.
--   
--   <pre>
--   &gt;&gt;&gt; elems (fromList [(5,"a"), (3,"b")])
--   ["b","a"]
--   
--   &gt;&gt;&gt; elems empty
--   []
--   </pre>
elems :: POMap k v -> [v]

-- | &lt;math&gt;. Return all keys of the map in unspecified order.
--   
--   <pre>
--   &gt;&gt;&gt; keys (fromList [(5,"a"), (3,"b")])
--   [3,5]
--   
--   &gt;&gt;&gt; keys empty
--   []
--   </pre>
keys :: POMap k v -> [k]

-- | &lt;math&gt;. Return all key/value pairs in the map in unspecified
--   order.
--   
--   <pre>
--   &gt;&gt;&gt; assocs (fromList [(5,"a"), (3,"b")])
--   [(3,"b"),(5,"a")]
--   
--   &gt;&gt;&gt; assocs empty
--   []
--   </pre>
assocs :: POMap k v -> [(k, v)]

-- | &lt;math&gt;. Return all key/value pairs in the map in unspecified
--   order.
--   
--   Currently, <tt>toList = <a>assocs</a></tt>.
toList :: POMap k v -> [(k, v)]

-- | &lt;math&gt;. Build a map from a list of key/value pairs. If the list
--   contains more than one value for the same key, the last value for the
--   key is retained.
--   
--   <pre>
--   &gt;&gt;&gt; fromList [] == (empty :: DivMap String)
--   True
--   
--   &gt;&gt;&gt; fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
--   True
--   
--   &gt;&gt;&gt; fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
--   True
--   </pre>
fromList :: PartialOrd k => [(k, v)] -> POMap k v

-- | &lt;math&gt;. Build a map from a list of key/value pairs with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
--   True
--   
--   &gt;&gt;&gt; fromListWith (++) [] == (empty :: DivMap String)
--   True
--   </pre>
fromListWith :: PartialOrd k => (v -> v -> v) -> [(k, v)] -> POMap k v

-- | &lt;math&gt;. Build a map from a list of key/value pairs with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f k a1 a2 = (show k) ++ a1 ++ a2
--   
--   &gt;&gt;&gt; fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
--   True
--   
--   &gt;&gt;&gt; fromListWithKey f [] == (empty :: DivMap String)
--   True
--   </pre>
fromListWithKey :: PartialOrd k => (k -> v -> v -> v) -> [(k, v)] -> POMap k v

-- | &lt;math&gt;. Filter all values that satisfy the predicate.
--   
--   <pre>
--   &gt;&gt;&gt; filter (&gt; "a") (fromList [(5,"a"), (3,"b")])
--   fromList [(3,"b")]
--   
--   &gt;&gt;&gt; filter (&gt; "x") (fromList [(5,"a"), (3,"b")])
--   fromList []
--   
--   &gt;&gt;&gt; filter (&lt; "a") (fromList [(5,"a"), (3,"b")])
--   fromList []
--   </pre>
filter :: (v -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Filter all keys/values that satisfy the predicate.
--   
--   <pre>
--   &gt;&gt;&gt; filterWithKey (\(Div k) _ -&gt; k &gt; 4) (fromList [(5,"a"), (3,"b")])
--   fromList [(5,"a")]
--   </pre>
filterWithKey :: (k -> v -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. 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 <tt>split</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; partition (&gt; "a") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b")], fromList [(5, "a")])
--   True
--   
--   &gt;&gt;&gt; partition (&lt; "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   True
--   
--   &gt;&gt;&gt; partition (&gt; "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--   True
--   </pre>
partition :: (v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. 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 <tt>split</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &gt; 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])
--   True
--   
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &lt; 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   True
--   
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &gt; 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--   True
--   </pre>
partitionWithKey :: (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. Take while a predicate on the keys holds. The user is
--   responsible for ensuring that for all keys <tt>j</tt> and <tt>k</tt>
--   in the map, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See note at
--   <a>spanAntitone</a>.
--   
--   <pre>
--   takeWhileAntitone p = <a>filterWithKey</a> (k _ -&gt; p k)
--   </pre>
takeWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Drop while a predicate on the keys holds. The user is
--   responsible for ensuring that for all keys <tt>j</tt> and <tt>k</tt>
--   in the map, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See note at
--   <a>spanAntitone</a>.
--   
--   <pre>
--   dropWhileAntitone p = <a>filterWithKey</a> (k -&gt; not (p k))
--   </pre>
dropWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Divide a map at the point where a predicate on the keys
--   stops holding. The user is responsible for ensuring that for all keys
--   <tt>j</tt> and <tt>k</tt> in the map, <tt>j &lt; k ==&gt; p j &gt;= p
--   k</tt>.
--   
--   <pre>
--   spanAntitone p xs = <a>partitionWithKey</a> (k _ -&gt; p k) xs
--   </pre>
--   
--   Note: if <tt>p</tt> is not actually antitone, then
--   <tt>spanAntitone</tt> will split the map at some <i>unspecified</i>
--   point where the predicate switches from holding to not holding (where
--   the predicate is seen to hold before the first key and to fail after
--   the last key).
spanAntitone :: (k -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. Map values and collect the <a>Just</a> results.
--   
--   <pre>
--   &gt;&gt;&gt; let f x = if x == "a" then Just "new a" else Nothing
--   
--   &gt;&gt;&gt; mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--   True
--   </pre>
mapMaybe :: (a -> Maybe b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. Map keys/values and collect the <a>Just</a> results.
--   
--   <pre>
--   &gt;&gt;&gt; let f k _ = if k == 3 then Just ("key : " ++ (show k)) else Nothing
--   
--   &gt;&gt;&gt; mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--   True
--   </pre>
mapMaybeWithKey :: (k -> a -> Maybe b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
--   
--   <pre>
--   &gt;&gt;&gt; let f a = if a &lt; "c" then Left a else Right a
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
--   :}
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEither (\ a -&gt; Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--   :}
--   True
--   </pre>
mapEither :: (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

-- | &lt;math&gt;. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> results.
--   
--   <pre>
--   &gt;&gt;&gt; let f (Div k) a = if k &lt; 5 then Left (k * 2) else Right (a ++ a)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
--   :}
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEitherWithKey (\_ a -&gt; Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
--   :}
--   True
--   </pre>
mapEitherWithKey :: (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

-- | &lt;math&gt;. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> (==)</tt>).
isSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

-- | &lt;math&gt;. 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 values. For example, the following expressions are
--   all <a>True</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
--   True
--   
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
--   True
--   </pre>
--   
--   But the following are all <a>False</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(2,'a')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isSubmapOfBy (&lt;)  (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
--   False
--   </pre>
isSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

-- | &lt;math&gt;. Is this a proper submap? (ie. a submap but not equal).
--   Defined as (<tt><a>isProperSubmapOf</a> = <a>isProperSubmapOfBy</a>
--   (==)</tt>).
isProperSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

-- | &lt;math&gt;. 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 values. For example, the
--   following expressions are all <a>True</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   </pre>
--   
--   But the following are all <a>False</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
--   False
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (&lt;)  (fromList [(1,'a')])         (fromList [(1,'a'),(2,'b')])
--   False
--   </pre>
isProperSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

-- | &lt;math&gt;. The minimal keys of the map.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupMin (fromList [(6,"a"), (3,"b")])
--   [(3,"b")]
--   
--   &gt;&gt;&gt; lookupMin empty
--   []
--   </pre>
lookupMin :: PartialOrd k => POMap k v -> [(k, v)]

-- | &lt;math&gt;. The maximal keys of the map.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupMax (fromList [(6,"a"), (3,"b")])
--   [(6,"a")]
--   
--   &gt;&gt;&gt; lookupMax empty
--   []
--   </pre>
lookupMax :: PartialOrd k => POMap k v -> [(k, v)]


-- | A reasonably efficient implementation of partially ordered maps from
--   keys to values (dictionaries).
--   
--   The API of this module is strict in both the keys and the values. If
--   you need value-lazy maps, use <a>Data.POMap.Lazy</a> instead. The
--   <a>POMap</a> type is shared between the lazy and strict modules,
--   meaning that the same <a>POMap</a> value can be passed to functions in
--   both modules (although that is rarely needed).
--   
--   A consequence of this is that the <a>Functor</a>, <a>Traversable</a>
--   and <tt>Data</tt> instances are the same as for the
--   <a>Data.POMap.Lazy</a> module, so if they are used on strict maps, the
--   resulting maps will be lazy.
--   
--   These modules are intended to be imported qualified, to avoid name
--   clashes with Prelude functions, e.g.
--   
--   <pre>
--   import qualified Data.POMap.Strict as POMap
--   </pre>
--   
--   The implementation of <a>POMap</a> is based on a decomposition of
--   chains (totally ordered submaps), inspired by <a>"Sorting and
--   Selection in Posets"</a>.
--   
--   Operation comments contain the operation time complexity in <a>Big-O
--   notation</a> and commonly refer to two characteristics of the poset
--   from which keys are drawn: The number of elements in the map
--   &lt;math&gt; and the <i>width</i> &lt;math&gt; of the poset, referring
--   to the size of the biggest anti-chain (set of incomparable elements).
--   
--   Generally speaking, lookup and mutation operations incur an additional
--   factor of &lt;math&gt; compared to their counter-parts in
--   <a>Data.Map.Strict</a>.
--   
--   Note that for practical applications, the width of the poset should be
--   in the order of &lt;math&gt;, otherwise a simple lookup list is
--   asymptotically superior. Even if that holds, the constants might be
--   too big to be useful for any &lt;math&gt; that can can happen in
--   practice.
--   
--   The following examples assume the following definitions for a map on
--   the divisibility relation on <a>Int</a>egers:
--   
--   <pre>
--   {-# LANGUAGE GeneralizedNewtypeDeriving #-}
--   
--   import           Algebra.PartialOrd
--   import           Data.POMap.Strict (POMap)
--   import qualified Data.POMap.Strict as POMap
--   
--   newtype Divisibility
--     = Div Int
--     deriving (Eq, Read, Show, Num)
--   
--   default (Divisibility)
--   
--   instance <a>PartialOrd</a> Divisibility where
--     Div a `leq` Div b = b `mod` a == 0
--   
--   type DivMap a = POMap Divisibility a
--   
--   -- We want integer literals to be interpreted as <tt>Divisibility</tt>s
--   -- and default <tt>empty</tt>s to DivMap String.
--   default (Divisibility, DivMap String)
--   </pre>
--   
--   <tt>Divisility</tt> is actually an example for a <a>PartialOrd</a>
--   that should not be used as keys of <a>POMap</a>. Its width is
--   &lt;math&gt;!
module Data.POMap.Strict

-- | A map from partially-ordered keys <tt>k</tt> to values <tt>v</tt>.
data POMap k v

-- | Test whether the structure is empty. The default implementation is
--   optimized for structures that are similar to cons-lists, because there
--   is no general way to do better.
null :: Foldable t => forall a. () => t a -> Bool

-- | &lt;math&gt;. The number of elements in this map.
size :: POMap k v -> Int

-- | &lt;math&gt;. The width &lt;math&gt; of the chain decomposition in the
--   internal data structure. This is always at least as big as the size of
--   the biggest possible anti-chain.
width :: POMap k v -> Int

-- | &lt;math&gt;. Is the key a member of the map? See also
--   <a>notMember</a>.
--   
--   <pre>
--   &gt;&gt;&gt; member 5 (fromList [(5,'a'), (3,'b')]) == True
--   True
--   
--   &gt;&gt;&gt; member 1 (fromList [(5,'a'), (3,'b')]) == False
--   True
--   </pre>
member :: PartialOrd k => k -> POMap k v -> Bool

-- | &lt;math&gt;. Is the key not a member of the map? See also
--   <a>member</a>.
--   
--   <pre>
--   &gt;&gt;&gt; notMember 5 (fromList [(5,'a'), (3,'b')]) == False
--   True
--   
--   &gt;&gt;&gt; notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--   True
--   </pre>
notMember :: PartialOrd k => k -> POMap k v -> Bool

-- | &lt;math&gt;. Is the key a member of the map?
lookup :: PartialOrd k => k -> POMap k v -> Maybe v

-- | &lt;math&gt;. 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.
--   
--   <pre>
--   &gt;&gt;&gt; findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   True
--   
--   &gt;&gt;&gt; findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--   True
--   </pre>
findWithDefault :: PartialOrd k => v -> k -> POMap k v -> v

-- | &lt;math&gt;. Find the largest set of keys smaller than the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLT 3  (fromList [(3,'a'), (5,'b')])
--   []
--   
--   &gt;&gt;&gt; lookupLT 9 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   </pre>
lookupLT :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the smallest key greater than the given one and
--   return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGT 5 (fromList [(3,'a'), (10,'b')])
--   [(10,'b')]
--   
--   &gt;&gt;&gt; lookupGT 5 (fromList [(3,'a'), (5,'b')])
--   []
--   </pre>
lookupGT :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the largest key smaller or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLE 2 (fromList [(3,'a'), (5,'b')])
--   []
--   
--   &gt;&gt;&gt; lookupLE 3 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   
--   &gt;&gt;&gt; lookupLE 10 (fromList [(3,'a'), (5,'b')])
--   [(5,'b')]
--   </pre>
lookupLE :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. Find the smallest key greater or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGE 3 (fromList [(3,'a'), (5,'b')])
--   [(3,'a')]
--   
--   &gt;&gt;&gt; lookupGE 5 (fromList [(3,'a'), (10,'b')])
--   [(10,'b')]
--   
--   &gt;&gt;&gt; lookupGE 6 (fromList [(3,'a'), (5,'b')])
--   []
--   </pre>
lookupGE :: PartialOrd k => k -> POMap k v -> [(k, v)]

-- | &lt;math&gt;. The empty map.
--   
--   <pre>
--   &gt;&gt;&gt; empty
--   fromList []
--   
--   &gt;&gt;&gt; size empty
--   0
--   </pre>
empty :: POMap k v

-- | &lt;math&gt;. A map with a single element.
--   
--   <pre>
--   &gt;&gt;&gt; singleton 1 'a'
--   fromList [(1,'a')]
--   
--   &gt;&gt;&gt; size (singleton 1 'a')
--   1
--   </pre>
singleton :: k -> v -> POMap k v

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'x')]
--   True
--   
--   &gt;&gt;&gt; insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'a'), (7,'x')]
--   True
--   
--   &gt;&gt;&gt; insert 5 'x' empty                         == singleton 5 'x'
--   True
--   </pre>
insert :: PartialOrd k => k -> v -> POMap k v -> POMap k v

-- | &lt;math&gt;. Insert with a function, combining new value and old
--   value. <tt><a>insertWith</a> f key value mp</tt> will insert the pair
--   (key, value) into <tt>mp</tt> if key does not exist in the map. If the
--   key does exist, the function will insert the pair <tt>(key, f
--   new_value old_value)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
--   True
--   
--   &gt;&gt;&gt; insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
--   True
--   
--   &gt;&gt;&gt; insertWith (++) 5 "xxx" empty                         == singleton 5 "xxx"
--   True
--   </pre>
insertWith :: PartialOrd k => (v -> v -> v) -> k -> v -> POMap k v -> POMap k v

-- | &lt;math&gt;. Insert with a function, combining key, new value and old
--   value. <tt><a>insertWithKey</a> f key value mp</tt> will insert the
--   pair (key, value) into <tt>mp</tt> if key does not exist in the map.
--   If the key does exist, the function will insert the pair <tt>(key,f
--   key new_value old_value)</tt>. Note that the key passed to f is the
--   same key passed to <a>insertWithKey</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
--   True
--   
--   &gt;&gt;&gt; insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
--   True
--   
--   &gt;&gt;&gt; insertWithKey f 5 "xxx" empty                         == singleton 5 "xxx"
--   True
--   </pre>
insertWithKey :: PartialOrd k => (k -> v -> v -> v) -> k -> v -> POMap k v -> POMap k v

-- | &lt;math&gt;. 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>).
--   
--   <pre>
--   &gt;&gt;&gt; let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
--   True
--   
--   &gt;&gt;&gt; insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "xxx")])
--   True
--   
--   &gt;&gt;&gt; insertLookupWithKey f 5 "xxx" empty                         == (Nothing,  singleton 5 "xxx")
--   True
--   </pre>
--   
--   This is how to define <tt>insertLookup</tt> using
--   <tt>insertLookupWithKey</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; let insertLookup kx x t = insertLookupWithKey (\_ a _ -&gt; a) kx x t
--   
--   &gt;&gt;&gt; insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])
--   True
--   
--   &gt;&gt;&gt; insertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "x")])
--   True
--   </pre>
insertLookupWithKey :: PartialOrd k => (k -> v -> v -> v) -> k -> v -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. Delete a key and its value from the map. When the key is
--   not a member of the map, the original map is returned.
--   
--   <pre>
--   &gt;&gt;&gt; delete 5 (fromList [(5,"a"), (3,"b")])
--   fromList [(3,"b")]
--   
--   &gt;&gt;&gt; delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; delete 5 empty
--   fromList []
--   </pre>
delete :: PartialOrd k => k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Simultaneous <a>delete</a> and <a>lookup</a>.
deleteLookup :: PartialOrd k => k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. Adjust 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.
--   
--   <pre>
--   &gt;&gt;&gt; adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
--   True
--   
--   &gt;&gt;&gt; adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; adjust ("new " ++) 7 empty                         == empty
--   True
--   </pre>
adjust :: PartialOrd k => (v -> v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Adjust 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.
--   
--   <pre>
--   &gt;&gt;&gt; let f key x = (show key) ++ ":new " ++ x
--   
--   &gt;&gt;&gt; adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
--   True
--   
--   &gt;&gt;&gt; adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; adjustWithKey f 7 empty                         == empty
--   True
--   </pre>
adjustWithKey :: PartialOrd k => (k -> v -> v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Adjust a value at a specific key with the result of the
--   provided function and simultaneously look up the old value at that
--   key. When the key is not a member of the map, the original map is
--   returned.
--   
--   <pre>
--   &gt;&gt;&gt; let f key old_value = show key ++ ":" ++ show 42 ++ "|" ++ old_value
--   
--   &gt;&gt;&gt; adjustLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:42|a")])
--   True
--   
--   &gt;&gt;&gt; adjustLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
--   True
--   
--   &gt;&gt;&gt; adjustLookupWithKey f 5 empty                         == (Nothing,  empty)
--   True
--   </pre>
adjustLookupWithKey :: PartialOrd k => (k -> v -> v) -> k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f x = if x == "a" then Just "new a" else Nothing
--   
--   &gt;&gt;&gt; update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
--   True
--   
--   &gt;&gt;&gt; update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--   True
--   </pre>
update :: PartialOrd k => (v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
--   
--   &gt;&gt;&gt; updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
--   True
--   
--   &gt;&gt;&gt; updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--   True
--   </pre>
updateWithKey :: PartialOrd k => (k -> v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Lookup and update. See also <a>updateWithKey</a>.
--   <b>Warning</b>: Contrary to <a>Data.Map.Strict</a>, the lookup does
--   <i>not</i> return the updated value, but the old value. This is
--   consistent with <a>insertLookupWithKey</a> and also
--   <tt>Data.IntMap.Strict.<a>updateLookupWithKey</a></tt>.
--   
--   Re-apply the updating function to the looked-up value once more to get
--   the value in the map, like in the last example:
--   
--   <pre>
--   &gt;&gt;&gt; let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
--   
--   &gt;&gt;&gt; updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])
--   True
--   
--   &gt;&gt;&gt; updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
--   True
--   
--   &gt;&gt;&gt; updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
--   True
--   
--   &gt;&gt;&gt; fst (updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])) &gt;&gt;= f 5
--   Just "5:new a"
--   </pre>
updateLookupWithKey :: PartialOrd k => (k -> v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f _ = Nothing
--   
--   &gt;&gt;&gt; alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--   True
--   
--   &gt;&gt;&gt; let f _ = Just "c"
--   
--   &gt;&gt;&gt; alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
--   True
--   
--   &gt;&gt;&gt; alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
--   True
--   </pre>
alter :: PartialOrd k => (Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. The expression (<tt><a>alterWithKey</a> f k map</tt>)
--   alters the value <tt>x</tt> at <tt>k</tt>, or absence thereof.
--   <a>alterWithKey</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 k (<a>lookup</a> k m)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; let f _ _ = Nothing
--   
--   &gt;&gt;&gt; alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   True
--   
--   &gt;&gt;&gt; alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--   True
--   
--   &gt;&gt;&gt; let f k _ = Just (show k ++ ":c")
--   
--   &gt;&gt;&gt; alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "7:c")]
--   True
--   
--   &gt;&gt;&gt; alterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:c")]
--   True
--   </pre>
alterWithKey :: PartialOrd k => (k -> Maybe v -> Maybe v) -> k -> POMap k v -> POMap k v

-- | &lt;math&gt;. Lookup and alteration. See also <a>alterWithKey</a>.
--   
--   <pre>
--   &gt;&gt;&gt; let f k x = if x == Nothing then Just ((show k) ++ ":new a") else Nothing
--   
--   &gt;&gt;&gt; alterLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b")])
--   True
--   
--   &gt;&gt;&gt; alterLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a"), (7, "7:new a")])
--   True
--   
--   &gt;&gt;&gt; alterLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
--   True
--   </pre>
alterLookupWithKey :: PartialOrd k => (k -> Maybe v -> Maybe v) -> k -> POMap k v -> (Maybe v, POMap k v)

-- | &lt;math&gt;. The expression (<tt><a>alterF</a> f k map</tt>) alters
--   the value <tt>x</tt> at <tt>k</tt>, or absence thereof. <a>alterF</a>
--   can be used to inspect, insert, delete, or update a value in a
--   <tt>Map</tt>. In short: <tt><a>lookup</a> k &lt;$&gt; <a>alterF</a> f
--   k m = f (<a>lookup</a> k m)</tt>.
--   
--   Example:
--   
--   <pre>
--   interactiveAlter :: Divibility -&gt; DivMap String -&gt; IO (DivMap String)
--   interactiveAlter k m = alterF f k m where
--     f Nothing -&gt; do
--        putStrLn $ show k ++
--            " was not found in the map. Would you like to add it?"
--        getUserResponse1 :: IO (Maybe String)
--     f (Just old) -&gt; do
--        putStrLn "The key is currently bound to " ++ show old ++
--            ". Would you like to change or delete it?"
--        getUserresponse2 :: IO (Maybe String)
--   </pre>
--   
--   <a>alterF</a> is the most general operation for working with an
--   individual key that may or may not be in a given map. When used with
--   trivial functors like <tt>Identity</tt> and <tt>Const</tt>, it is
--   often slightly slower than more specialized combinators like
--   <a>lookup</a> and <a>insert</a>. However, when the functor is
--   non-trivial and key comparison is not particularly cheap, it is the
--   fastest way.
alterF :: (Functor f, PartialOrd k) => (Maybe v -> f (Maybe v)) -> k -> POMap k v -> f (POMap k v)

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. 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> == <a>unionWith</a>
--   <a>const</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--   True
--   </pre>
union :: PartialOrd k => POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Union with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--   True
--   </pre>
unionWith :: PartialOrd k => (v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Union with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value
--   
--   &gt;&gt;&gt; unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
--   True
--   </pre>
unionWithKey :: PartialOrd k => (k -> v -> v -> v) -> POMap k v -> POMap k v -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of maps: (<tt><a>unions</a> == <a>foldl</a> <a>union</a>
--   <a>empty</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--        == fromList [(3, "b"), (5, "a"), (7, "C")]
--   :}
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--    unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]
--        == fromList [(3, "B3"), (5, "A3"), (7, "C")]
--   :}
--   True
--   </pre>
unions :: PartialOrd k => [POMap k v] -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of maps, with a combining operation: (<tt><a>unionsWith</a> f ==
--   <a>foldl</a> (<a>unionWith</a> f) <a>empty</a></tt>).
--   
--   <pre>
--   &gt;&gt;&gt; :{
--    unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]
--        == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]
--   :}
--   True
--   </pre>
unionsWith :: PartialOrd k => (v -> v -> v) -> [POMap k v] -> POMap k v

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference of two
--   maps. Return elements of the first map not existing in the second map.
--   
--   <pre>
--   &gt;&gt;&gt; difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(3,"b")]
--   </pre>
difference :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference with a
--   combining function. When two equal keys are encountered, the combining
--   function is applied to the values of these keys. If it returns
--   <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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
--   
--   &gt;&gt;&gt; differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
--   fromList [(3,"b:B")]
--   </pre>
differenceWith :: PartialOrd k => (a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. 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>.
--   
--   <pre>
--   &gt;&gt;&gt; let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
--   
--   &gt;&gt;&gt; differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
--   fromList [(3,"3:b|B")]
--   </pre>
differenceWithKey :: PartialOrd k => (k -> a -> b -> Maybe a) -> POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection of two
--   maps. Return data in the first map for the keys existing in both maps.
--   (<tt><a>intersection</a> m1 m2 == <a>intersectionWith</a> <a>const</a>
--   m1 m2</tt>).
--   
--   <pre>
--   &gt;&gt;&gt; intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"a")]
--   </pre>
intersection :: PartialOrd k => POMap k a -> POMap k b -> POMap k a

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"aA")]
--   </pre>
intersectionWith :: PartialOrd k => (a -> b -> c) -> POMap k a -> POMap k b -> POMap k c

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Intersection with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
--   
--   &gt;&gt;&gt; intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])
--   fromList [(5,"5:a|A")]
--   </pre>
intersectionWithKey :: PartialOrd k => (k -> a -> b -> c) -> POMap k a -> POMap k b -> POMap k c

-- | &lt;math&gt;. Map a function over all values in the map.
--   
--   <pre>
--   &gt;&gt;&gt; map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--   True
--   </pre>
map :: (a -> b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. Map a function over all values in the map.
--   
--   <pre>
--   &gt;&gt;&gt; let f key x = (show key) ++ ":" ++ x
--   
--   &gt;&gt;&gt; mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--   True
--   </pre>
mapWithKey :: (k -> a -> b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. <tt><a>traverseWithKey</a> f m == <a>fromList</a>
--   <a>$</a> <a>traverse</a> ((k, v) -&gt; (v' -&gt; v' <a>seq</a> (k,v'))
--   <a>$</a> f k v) (<tt>toList</tt> m)</tt> That is, it behaves much like
--   a regular <a>traverse</a> except that the traversing function also has
--   access to the key associated with a value and the values are forced
--   before they are installed in the result map.
--   
--   <pre>
--   &gt;&gt;&gt; traverseWithKey (\(Div k) v -&gt; if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])
--   True
--   
--   &gt;&gt;&gt; traverseWithKey (\(Div k) v -&gt; if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')])           == Nothing
--   True
--   </pre>
traverseWithKey :: Applicative t => (k -> a -> t b) -> POMap k a -> t (POMap k b)

-- | &lt;math&gt;. Traverse keys/values and collect the <a>Just</a>
--   results.
--   
--   Contrary to <a>traverse</a>, this is value-strict.
traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> POMap k a -> t (POMap k b)

-- | &lt;math&gt;. The function <a>mapAccum</a> threads an accumulating
--   argument through the map in ascending order of keys.
--   
--   <pre>
--   &gt;&gt;&gt; let f a b = (a ++ b, b ++ "X")
--   
--   &gt;&gt;&gt; mapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])
--   True
--   </pre>
mapAccum :: (a -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

-- | &lt;math&gt;. The function <a>mapAccumWithKey</a> threads an
--   accumulating argument through the map in ascending order of keys.
--   
--   <pre>
--   &gt;&gt;&gt; let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")
--   
--   &gt;&gt;&gt; mapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])
--   True
--   </pre>
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> POMap k b -> (a, POMap k c)

-- | &lt;math&gt;. <tt><a>mapKeys</a> 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 value at the
--   greatest of the original keys is retained.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
--   True
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(1,"c")]
--   
--   &gt;&gt;&gt; mapKeys (\ _ -&gt; 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])
--   fromList [(3,"c")]
--   </pre>
mapKeys :: PartialOrd k2 => (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. <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>.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeysWith (+) (\ _ -&gt; 1) (fromList [(1,1), (2,2), (3,3), (4,4)]) == singleton 1 10
--   True
--   
--   &gt;&gt;&gt; mapKeysWith (+) (\ _ -&gt; 3) (fromList [(1,1), (2,1), (3,1), (4,1)]) == singleton 3 4
--   True
--   </pre>
mapKeysWith :: PartialOrd k2 => (v -> v -> v) -> (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. <tt><a>mapKeysMonotonic</a> f s == <a>mapKeys</a> 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, for every chain <tt>ls</tt> in
--   <tt>s</tt> 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
--   </pre>
--   
--   This means that <tt>f</tt> maps distinct original keys to distinct
--   resulting keys. This function has better performance than
--   <a>mapKeys</a>.
--   
--   <pre>
--   &gt;&gt;&gt; mapKeysMonotonic (\ k -&gt; k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
--   True
--   </pre>
mapKeysMonotonic :: (k1 -> k2) -> POMap k1 v -> POMap k2 v

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   right-associative binary operator, such that <tt><a>foldrWithKey</a> f
--   z == <a>foldr</a> (<a>uncurry</a> f) z . <tt>toAscList</tt></tt>.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; keys map = foldrWithKey (\k x ks -&gt; k:ks) [] map
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   
--   &gt;&gt;&gt; foldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
--   True
--   </pre>
foldrWithKey :: (k -> a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   left-associative binary operator, such that <tt><a>foldlWithKey</a> f
--   z == <a>foldl</a> (\z' (kx, x) -&gt; f z' kx x) z .
--   <tt>toAscList</tt></tt>.
--   
--   <pre>
--   &gt;&gt;&gt; keys = reverse . foldlWithKey (\ks k x -&gt; k:ks) []
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   
--   &gt;&gt;&gt; foldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"
--   True
--   </pre>
foldlWithKey :: (b -> k -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Fold the keys and values in the map using the given
--   monoid, such that
--   
--   <pre>
--   <a>foldMapWithKey</a> f = <a>fold</a> . <a>mapWithKey</a> f
--   </pre>
foldMapWithKey :: Monoid m => (k -> a -> m) -> POMap k a -> m

-- | &lt;math&gt;. A strict version of <a>foldr</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldl</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldrWithKey</a>. Each
--   application of the operator is evaluated before using the result in
--   the next application. This function is strict in the starting value.
foldrWithKey' :: (k -> a -> b -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. A strict version of <a>foldlWithKey</a>. Each
--   application of the operator is evaluated before using the result in
--   the next application. This function is strict in the starting value.
foldlWithKey' :: (b -> k -> a -> b) -> b -> POMap k a -> b

-- | &lt;math&gt;. Return all elements of the map in unspecified order.
--   
--   <pre>
--   &gt;&gt;&gt; elems (fromList [(5,"a"), (3,"b")])
--   ["b","a"]
--   
--   &gt;&gt;&gt; elems empty
--   []
--   </pre>
elems :: POMap k v -> [v]

-- | &lt;math&gt;. Return all keys of the map in unspecified order.
--   
--   <pre>
--   &gt;&gt;&gt; keys (fromList [(5,"a"), (3,"b")])
--   [3,5]
--   
--   &gt;&gt;&gt; keys empty
--   []
--   </pre>
keys :: POMap k v -> [k]

-- | &lt;math&gt;. Return all key/value pairs in the map in unspecified
--   order.
--   
--   <pre>
--   &gt;&gt;&gt; assocs (fromList [(5,"a"), (3,"b")])
--   [(3,"b"),(5,"a")]
--   
--   &gt;&gt;&gt; assocs empty
--   []
--   </pre>
assocs :: POMap k v -> [(k, v)]

-- | &lt;math&gt;. Return all key/value pairs in the map in unspecified
--   order.
--   
--   Currently, <tt>toList = <a>assocs</a></tt>.
toList :: POMap k v -> [(k, v)]

-- | &lt;math&gt;. Build a map from a list of key/value pairs. If the list
--   contains more than one value for the same key, the last value for the
--   key is retained.
--   
--   This version is strict in its values, as opposed to the
--   <tt>IsList</tt> instance for <a>POMap</a>.
--   
--   <pre>
--   &gt;&gt;&gt; fromList [] == (empty :: DivMap String)
--   True
--   
--   &gt;&gt;&gt; fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
--   True
--   
--   &gt;&gt;&gt; fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
--   True
--   </pre>
fromList :: PartialOrd k => [(k, v)] -> POMap k v

-- | &lt;math&gt;. Build a map from a list of key/value pairs with a
--   combining function.
--   
--   This version is strict in its values, as opposed to the
--   <tt>IsList</tt> instance for <a>POMap</a>.
--   
--   <pre>
--   &gt;&gt;&gt; fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
--   True
--   
--   &gt;&gt;&gt; fromListWith (++) [] == (empty :: DivMap String)
--   True
--   </pre>
fromListWith :: PartialOrd k => (v -> v -> v) -> [(k, v)] -> POMap k v

-- | &lt;math&gt;. Build a map from a list of key/value pairs with a
--   combining function.
--   
--   <pre>
--   &gt;&gt;&gt; let f k a1 a2 = (show k) ++ a1 ++ a2
--   
--   &gt;&gt;&gt; fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
--   True
--   
--   &gt;&gt;&gt; fromListWithKey f [] == (empty :: DivMap String)
--   True
--   </pre>
fromListWithKey :: PartialOrd k => (k -> v -> v -> v) -> [(k, v)] -> POMap k v

-- | &lt;math&gt;. Filter all values that satisfy the predicate.
--   
--   <pre>
--   &gt;&gt;&gt; filter (&gt; "a") (fromList [(5,"a"), (3,"b")])
--   fromList [(3,"b")]
--   
--   &gt;&gt;&gt; filter (&gt; "x") (fromList [(5,"a"), (3,"b")])
--   fromList []
--   
--   &gt;&gt;&gt; filter (&lt; "a") (fromList [(5,"a"), (3,"b")])
--   fromList []
--   </pre>
filter :: (v -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Filter all keys/values that satisfy the predicate.
--   
--   <pre>
--   &gt;&gt;&gt; filterWithKey (\(Div k) _ -&gt; k &gt; 4) (fromList [(5,"a"), (3,"b")])
--   fromList [(5,"a")]
--   </pre>
filterWithKey :: (k -> v -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. 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 <tt>split</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; partition (&gt; "a") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b")], fromList [(5, "a")])
--   True
--   
--   &gt;&gt;&gt; partition (&lt; "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   True
--   
--   &gt;&gt;&gt; partition (&gt; "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--   True
--   </pre>
partition :: (v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. 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 <tt>split</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &gt; 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])
--   True
--   
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &lt; 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   True
--   
--   &gt;&gt;&gt; partitionWithKey (\ (Div k) _ -&gt; k &gt; 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--   True
--   </pre>
partitionWithKey :: (k -> v -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. Take while a predicate on the keys holds. The user is
--   responsible for ensuring that for all keys <tt>j</tt> and <tt>k</tt>
--   in the map, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See note at
--   <a>spanAntitone</a>.
--   
--   <pre>
--   takeWhileAntitone p = <a>filterWithKey</a> (k _ -&gt; p k)
--   </pre>
takeWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Drop while a predicate on the keys holds. The user is
--   responsible for ensuring that for all keys <tt>j</tt> and <tt>k</tt>
--   in the map, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See note at
--   <a>spanAntitone</a>.
--   
--   <pre>
--   dropWhileAntitone p = <a>filterWithKey</a> (k -&gt; not (p k))
--   </pre>
dropWhileAntitone :: (k -> Bool) -> POMap k v -> POMap k v

-- | &lt;math&gt;. Divide a map at the point where a predicate on the keys
--   stops holding. The user is responsible for ensuring that for all keys
--   <tt>j</tt> and <tt>k</tt> in the map, <tt>j &lt; k ==&gt; p j &gt;= p
--   k</tt>.
--   
--   <pre>
--   spanAntitone p xs = <a>partitionWithKey</a> (k _ -&gt; p k) xs
--   </pre>
--   
--   Note: if <tt>p</tt> is not actually antitone, then
--   <tt>spanAntitone</tt> will split the map at some <i>unspecified</i>
--   point where the predicate switches from holding to not holding (where
--   the predicate is seen to hold before the first key and to fail after
--   the last key).
spanAntitone :: (k -> Bool) -> POMap k v -> (POMap k v, POMap k v)

-- | &lt;math&gt;. Map values and collect the <a>Just</a> results.
--   
--   <pre>
--   &gt;&gt;&gt; let f x = if x == "a" then Just "new a" else Nothing
--   
--   &gt;&gt;&gt; mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--   True
--   </pre>
mapMaybe :: (a -> Maybe b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. Map keys/values and collect the <a>Just</a> results.
--   
--   <pre>
--   &gt;&gt;&gt; let f k _ = if k == 3 then Just ("key : " ++ (show k)) else Nothing
--   
--   &gt;&gt;&gt; mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--   True
--   </pre>
mapMaybeWithKey :: (k -> a -> Maybe b) -> POMap k a -> POMap k b

-- | &lt;math&gt;. Map values and separate the <a>Left</a> and <a>Right</a>
--   results.
--   
--   <pre>
--   &gt;&gt;&gt; let f a = if a &lt; "c" then Left a else Right a
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
--   :}
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEither (\ a -&gt; Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--   :}
--   True
--   </pre>
mapEither :: (a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

-- | &lt;math&gt;. Map keys/values and separate the <a>Left</a> and
--   <a>Right</a> results.
--   
--   <pre>
--   &gt;&gt;&gt; let f (Div k) a = if k &lt; 5 then Left (k * 2) else Right (a ++ a)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
--   :}
--   True
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--     mapEitherWithKey (\_ a -&gt; Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--       == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
--   :}
--   True
--   </pre>
mapEitherWithKey :: (k -> a -> Either b c) -> POMap k a -> (POMap k b, POMap k c)

-- | &lt;math&gt;. This function is defined as (<tt><a>isSubmapOf</a> =
--   <a>isSubmapOfBy</a> (==)</tt>).
isSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

-- | &lt;math&gt;. 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 values. For example, the following expressions are
--   all <a>True</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   
--   &gt;&gt;&gt; isSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])
--   True
--   
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
--   True
--   </pre>
--   
--   But the following are all <a>False</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(2,'a')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isSubmapOfBy (&lt;)  (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
--   False
--   </pre>
isSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

-- | &lt;math&gt;. Is this a proper submap? (ie. a submap but not equal).
--   Defined as (<tt><a>isProperSubmapOf</a> = <a>isProperSubmapOfBy</a>
--   (==)</tt>).
isProperSubmapOf :: (PartialOrd k, Eq v) => POMap k v -> POMap k v -> Bool

-- | &lt;math&gt;. 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 values. For example, the
--   following expressions are all <a>True</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (&lt;=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])
--   True
--   </pre>
--   
--   But the following are all <a>False</a>:
--   
--   <pre>
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])
--   False
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])
--   False
--   
--   &gt;&gt;&gt; isProperSubmapOfBy (&lt;)  (fromList [(1,'a')])         (fromList [(1,'a'),(2,'b')])
--   False
--   </pre>
isProperSubmapOfBy :: (PartialOrd k) => (a -> b -> Bool) -> POMap k a -> POMap k b -> Bool

-- | &lt;math&gt;. The minimal keys of the map.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupMin (fromList [(6,"a"), (3,"b")])
--   [(3,"b")]
--   
--   &gt;&gt;&gt; lookupMin empty
--   []
--   </pre>
lookupMin :: PartialOrd k => POMap k v -> [(k, v)]

-- | &lt;math&gt;. The maximal keys of the map.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupMax (fromList [(6,"a"), (3,"b")])
--   [(6,"a")]
--   
--   &gt;&gt;&gt; lookupMax empty
--   []
--   </pre>
lookupMax :: PartialOrd k => POMap k v -> [(k, v)]


-- | This module doesn't respect the PVP! Breaking changes may happen at
--   any minor version (&gt;= *.*.m.*)
module Data.POSet.Internal

-- | A set of partially ordered values <tt>k</tt>.
newtype POSet k
POSet :: (POMap k ()) -> POSet k

-- | &lt;math&gt;. The number of elements in this set.
size :: POSet k -> Int

-- | &lt;math&gt;. The width &lt;math&gt; of the chain decomposition in the
--   internal data structure. This is always at least as big as the size of
--   the biggest possible anti-chain.
width :: POSet k -> Int

-- | &lt;math&gt;. Is the key a member of the map? See also
--   <a>notMember</a>.
member :: PartialOrd k => k -> POSet k -> Bool

-- | &lt;math&gt;. Is the key not a member of the map? See also
--   <a>member</a>.
notMember :: PartialOrd k => k -> POSet k -> Bool

-- | &lt;math&gt;. Find the largest set of keys smaller than the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLT 3 (fromList [3, 5])
--   []
--   
--   &gt;&gt;&gt; lookupLT 6 (fromList [3, 5])
--   [3]
--   </pre>
lookupLT :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. Find the largest key smaller or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLE 2  (fromList [3, 5])
--   []
--   
--   &gt;&gt;&gt; lookupLE 3  (fromList [3, 5])
--   [3]
--   
--   &gt;&gt;&gt; lookupLE 10 (fromList [3, 5])
--   [5]
--   </pre>
lookupLE :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. Find the smallest key greater or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGE 3 (fromList [3, 5])
--   [3]
--   
--   &gt;&gt;&gt; lookupGE 5 (fromList [3, 10])
--   [10]
--   
--   &gt;&gt;&gt; lookupGE 6 (fromList [3, 5])
--   []
--   </pre>
lookupGE :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. Find the smallest key greater than the given one and
--   return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGT 3 (fromList [6, 5])
--   [6]
--   
--   &gt;&gt;&gt; lookupGT 5 (fromList [3, 5])
--   []
--   </pre>
lookupGT :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. <tt>(s1 <a>isSubsetOf</a> s2)</tt> tells whether
--   <tt>s1</tt> is a subset of <tt>s2</tt>.
isSubsetOf :: PartialOrd k => POSet k -> POSet k -> Bool

-- | &lt;math&gt;. Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: PartialOrd k => POSet k -> POSet k -> Bool

-- | &lt;math&gt;. The empty set.
empty :: POSet k

-- | &lt;math&gt;. A set with a single element.
singleton :: k -> POSet k

-- | &lt;math&gt;. 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><tt>insertWith</tt> <a>const</a></tt>.
insert :: (PartialOrd k) => k -> POSet k -> POSet k

-- | &lt;math&gt;. Delete an element from a set.
delete :: (PartialOrd k) => k -> POSet k -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of two
--   sets, preferring the first set when equal elements are encountered.
union :: PartialOrd k => POSet k -> POSet k -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of sets: (<tt><a>unions</a> == <a>foldl</a> <a>union</a>
--   <a>empty</a></tt>).
unions :: PartialOrd k => [POSet k] -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference of two
--   sets.
difference :: PartialOrd k => POSet k -> POSet k -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The intersection of
--   two sets. Elements of the result come from the first set, so for
--   example
--   
--   <pre>
--   &gt;&gt;&gt; data AB = A | B deriving Show
--   
--   &gt;&gt;&gt; instance Eq AB where _ == _ = True
--   
--   &gt;&gt;&gt; instance PartialOrd AB where _ `leq` _ = True
--   
--   &gt;&gt;&gt; singleton A `intersection` singleton B
--   fromList [A]
--   
--   &gt;&gt;&gt; singleton B `intersection` singleton A
--   fromList [B]
--   </pre>
intersection :: PartialOrd k => POSet k -> POSet k -> POSet k

-- | &lt;math&gt;. Filter all elements that satisfy the predicate.
filter :: (k -> Bool) -> POSet k -> POSet k

-- | &lt;math&gt;. Partition the set into two sets, one with all elements
--   that satisfy the predicate and one with all elements that don't
--   satisfy the predicate.
partition :: (k -> Bool) -> POSet k -> (POSet k, POSet k)

-- | &lt;math&gt;. Take while a predicate on the keys holds. The user is
--   responsible for ensuring that for all elements <tt>j</tt> and
--   <tt>k</tt> in the set, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See
--   note at <a>spanAntitone</a>.
--   
--   <pre>
--   takeWhileAntitone p = <a>filter</a> p
--   </pre>
takeWhileAntitone :: (k -> Bool) -> POSet k -> POSet k

-- | &lt;math&gt;. Drop while a predicate on the keys holds. The user is
--   responsible for ensuring that for all elements <tt>j</tt> and
--   <tt>k</tt> in the set, <tt>j &lt; k ==&gt; p j &gt;= p k</tt>. See
--   note at <a>spanAntitone</a>.
--   
--   <pre>
--   dropWhileAntitone p = <a>filter</a> (not . p)
--   </pre>
dropWhileAntitone :: (k -> Bool) -> POSet k -> POSet k

-- | &lt;math&gt;. Divide a set at the point where a predicate on the keys
--   stops holding. The user is responsible for ensuring that for all
--   elements <tt>j</tt> and <tt>k</tt> in the set, <tt>j &lt; k ==&gt; p j
--   &gt;= p k</tt>.
--   
--   <pre>
--   spanAntitone p xs = <a>partition</a> p xs
--   </pre>
--   
--   Note: if <tt>p</tt> is not actually antitone, then
--   <tt>spanAntitone</tt> will split the set at some <i>unspecified</i>
--   point where the predicate switches from holding to not holding (where
--   the predicate is seen to hold before the first element and to fail
--   after the last element).
spanAntitone :: (k -> Bool) -> POSet k -> (POSet k, POSet k)

-- | &lt;math&gt;. <tt><a>map</a> f s</tt> is the set obtained by applying
--   <tt>f</tt> to each element of <tt>s</tt>.
--   
--   It's worth noting that the size of the result may be smaller if, for
--   some <tt>(x,y)</tt>, <tt>x /= y &amp;&amp; f x == f y</tt>
map :: PartialOrd k2 => (k1 -> k2) -> POSet k1 -> POSet k2

-- | &lt;math&gt;. <tt><a>mapMonotonic</a> f s == <a>map</a> f s</tt>, but
--   works only when <tt>f</tt> is strictly increasing. <i>The precondition
--   is not checked.</i> Semi-formally, for every chain <tt>ls</tt> in
--   <tt>s</tt> we have:
--   
--   <pre>
--   and [x &lt; y ==&gt; f x &lt; f y | x &lt;- ls, y &lt;- ls]
--                       ==&gt; mapMonotonic f s == map f s
--   </pre>
mapMonotonic :: (k1 -> k2) -> POSet k1 -> POSet k2

-- | &lt;math&gt;. A strict version of <a>foldr</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> POSet a -> b

-- | &lt;math&gt;. A strict version of <a>foldl</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> POSet a -> b

-- | &lt;math&gt;. The minimal keys of the set.
lookupMin :: PartialOrd k => POSet k -> [k]

-- | &lt;math&gt;. The maximal keys of the set.
lookupMax :: PartialOrd k => POSet k -> [k]

-- | &lt;math&gt;. The elements of a set in unspecified order.
elems :: POSet k -> [k]

-- | &lt;math&gt;. The elements of a set in unspecified order.
toList :: POSet k -> [k]

-- | &lt;math&gt;. Build a set from a list of keys.
fromList :: (PartialOrd k) => [k] -> POSet k
instance Algebra.PartialOrd.PartialOrd k => GHC.Classes.Eq (Data.POSet.Internal.POSet k)
instance Algebra.PartialOrd.PartialOrd k => Algebra.PartialOrd.PartialOrd (Data.POSet.Internal.POSet k)
instance GHC.Show.Show a => GHC.Show.Show (Data.POSet.Internal.POSet a)
instance (GHC.Read.Read a, Algebra.PartialOrd.PartialOrd a) => GHC.Read.Read (Data.POSet.Internal.POSet a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.POSet.Internal.POSet a)
instance Data.Foldable.Foldable Data.POSet.Internal.POSet
instance Algebra.PartialOrd.PartialOrd k => GHC.Exts.IsList (Data.POSet.Internal.POSet k)


-- | A reasonably efficient implementation of partially ordered sets.
--   
--   These modules are intended to be imported qualified, to avoid name
--   clashes with Prelude functions, e.g.
--   
--   <pre>
--   import qualified Data.POSet as POSet
--   </pre>
--   
--   The implementation of <tt>POSet</tt> is based on a decomposition of
--   chains (totally ordered submaps), inspired by <a>"Sorting and
--   Selection in Posets"</a>.
--   
--   Operation comments contain the operation time complexity in <a>Big-O
--   notation</a> and commonly refer to two characteristics of the poset
--   from which keys are drawn: The number of elements in the set
--   &lt;math&gt; and the <i>width</i> &lt;math&gt; of the poset, referring
--   to the size of the biggest anti-chain (set of incomparable elements).
--   
--   Generally speaking, lookup and mutation operations incur an additional
--   factor of &lt;math&gt; compared to their counter-parts in
--   <a>Data.Set</a>.
--   
--   Note that for practical applications, the width of the poset should be
--   in the order of &lt;math&gt;, otherwise a simple lookup list is
--   asymptotically superior. Even if that holds, the constants might be
--   too big to be useful for any &lt;math&gt; that can can happen in
--   practice.
--   
--   The following examples assume the following definitions for a set on
--   the divisibility relation on <a>Int</a>egers:
--   
--   <pre>
--   {-# LANGUAGE GeneralizedNewtypeDeriving #-}
--   
--   import           Algebra.PartialOrd
--   import           Data.POSet (POSet)
--   import qualified Data.POSet as POSet
--   
--   newtype Divisibility
--     = Div Int
--     deriving (Eq, Read, Show, Num)
--   
--   default (Divisibility)
--   
--   instance <tt>PartialOrd</tt> Divisibility where
--     Div a `leq` Div b = b `mod` a == 0
--   
--   type DivSet = POSet Divisibility
--   
--   -- We want integer literals to be interpreted as <tt>Divisibility</tt>s
--   -- and default <tt>empty</tt>s to DivSet.
--   default (Divisibility, DivSet)
--   </pre>
--   
--   <tt>Divisility</tt> is actually an example for a <tt>PartialOrd</tt>
--   that should not be used as keys of <tt>POSet</tt>. Its width is
--   &lt;math&gt;!
module Data.POSet

-- | A set of partially ordered values <tt>k</tt>.
data POSet k

-- | Test whether the structure is empty. The default implementation is
--   optimized for structures that are similar to cons-lists, because there
--   is no general way to do better.
null :: Foldable t => forall a. () => t a -> Bool

-- | &lt;math&gt;. The number of elements in this set.
size :: POSet k -> Int

-- | &lt;math&gt;. Is the key a member of the map? See also
--   <a>notMember</a>.
member :: PartialOrd k => k -> POSet k -> Bool

-- | &lt;math&gt;. Is the key not a member of the map? See also
--   <a>member</a>.
notMember :: PartialOrd k => k -> POSet k -> Bool

-- | &lt;math&gt;. Find the largest set of keys smaller than the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLT 3 (fromList [3, 5])
--   []
--   
--   &gt;&gt;&gt; lookupLT 6 (fromList [3, 5])
--   [3]
--   </pre>
lookupLT :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. Find the smallest key greater than the given one and
--   return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGT 3 (fromList [6, 5])
--   [6]
--   
--   &gt;&gt;&gt; lookupGT 5 (fromList [3, 5])
--   []
--   </pre>
lookupGT :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. Find the largest key smaller or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupLE 2  (fromList [3, 5])
--   []
--   
--   &gt;&gt;&gt; lookupLE 3  (fromList [3, 5])
--   [3]
--   
--   &gt;&gt;&gt; lookupLE 10 (fromList [3, 5])
--   [5]
--   </pre>
lookupLE :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. Find the smallest key greater or equal to the given one
--   and return the corresponding list of (key, value) pairs.
--   
--   Note that the following examples assume the <tt>Divisibility</tt>
--   partial order defined at the top.
--   
--   <pre>
--   &gt;&gt;&gt; lookupGE 3 (fromList [3, 5])
--   [3]
--   
--   &gt;&gt;&gt; lookupGE 5 (fromList [3, 10])
--   [10]
--   
--   &gt;&gt;&gt; lookupGE 6 (fromList [3, 5])
--   []
--   </pre>
lookupGE :: PartialOrd k => k -> POSet k -> [k]

-- | &lt;math&gt;. <tt>(s1 <a>isSubsetOf</a> s2)</tt> tells whether
--   <tt>s1</tt> is a subset of <tt>s2</tt>.
isSubsetOf :: PartialOrd k => POSet k -> POSet k -> Bool

-- | &lt;math&gt;. Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: PartialOrd k => POSet k -> POSet k -> Bool

-- | &lt;math&gt;. The empty set.
empty :: POSet k

-- | &lt;math&gt;. A set with a single element.
singleton :: k -> POSet k

-- | &lt;math&gt;. 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><tt>insertWith</tt> <a>const</a></tt>.
insert :: (PartialOrd k) => k -> POSet k -> POSet k

-- | &lt;math&gt;. Delete an element from a set.
delete :: (PartialOrd k) => k -> POSet k -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of two
--   sets, preferring the first set when equal elements are encountered.
union :: PartialOrd k => POSet k -> POSet k -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The union of a list
--   of sets: (<tt><a>unions</a> == <a>foldl</a> <a>union</a>
--   <a>empty</a></tt>).
unions :: PartialOrd k => [POSet k] -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. Difference of two
--   sets.
difference :: PartialOrd k => POSet k -> POSet k -> POSet k

-- | &lt;math&gt;, where &lt;math&gt; and &lt;math&gt;. The intersection of
--   two sets. Elements of the result come from the first set, so for
--   example
--   
--   <pre>
--   &gt;&gt;&gt; data AB = A | B deriving Show
--   
--   &gt;&gt;&gt; instance Eq AB where _ == _ = True
--   
--   &gt;&gt;&gt; instance PartialOrd AB where _ `leq` _ = True
--   
--   &gt;&gt;&gt; singleton A `intersection` singleton B
--   fromList [A]
--   
--   &gt;&gt;&gt; singleton B `intersection` singleton A
--   fromList [B]
--   </pre>
intersection :: PartialOrd k => POSet k -> POSet k -> POSet k

-- | &lt;math&gt;. Filter all elements that satisfy the predicate.
filter :: (k -> Bool) -> POSet k -> POSet k

-- | &lt;math&gt;. Partition the set into two sets, one with all elements
--   that satisfy the predicate and one with all elements that don't
--   satisfy the predicate.
partition :: (k -> Bool) -> POSet k -> (POSet k, POSet k)

-- | &lt;math&gt;. <tt><a>map</a> f s</tt> is the set obtained by applying
--   <tt>f</tt> to each element of <tt>s</tt>.
--   
--   It's worth noting that the size of the result may be smaller if, for
--   some <tt>(x,y)</tt>, <tt>x /= y &amp;&amp; f x == f y</tt>
map :: PartialOrd k2 => (k1 -> k2) -> POSet k1 -> POSet k2

-- | &lt;math&gt;. <tt><a>mapMonotonic</a> f s == <a>map</a> f s</tt>, but
--   works only when <tt>f</tt> is strictly increasing. <i>The precondition
--   is not checked.</i> Semi-formally, for every chain <tt>ls</tt> in
--   <tt>s</tt> we have:
--   
--   <pre>
--   and [x &lt; y ==&gt; f x &lt; f y | x &lt;- ls, y &lt;- ls]
--                       ==&gt; mapMonotonic f s == map f s
--   </pre>
mapMonotonic :: (k1 -> k2) -> POSet k1 -> POSet k2

-- | Right-associative fold of a structure.
--   
--   In the case of lists, <a>foldr</a>, when applied to a binary operator,
--   a starting value (typically the right-identity of the operator), and a
--   list, reduces the list using the binary operator, from right to left:
--   
--   <pre>
--   foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
--   </pre>
--   
--   Note that, since the head of the resulting expression is produced by
--   an application of the operator to the first element of the list,
--   <a>foldr</a> can produce a terminating expression from an infinite
--   list.
--   
--   For a general <a>Foldable</a> structure this should be semantically
--   identical to,
--   
--   <pre>
--   foldr f z = <a>foldr</a> f z . <a>toList</a>
--   </pre>
foldr :: Foldable t => forall a b. () => (a -> b -> b) -> b -> t a -> b

-- | Left-associative fold of a structure.
--   
--   In the case of lists, <a>foldl</a>, when applied to a binary operator,
--   a starting value (typically the left-identity of the operator), and a
--   list, reduces the list using the binary operator, from left to right:
--   
--   <pre>
--   foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--   </pre>
--   
--   Note that to produce the outermost application of the operator the
--   entire input list must be traversed. This means that <a>foldl'</a>
--   will diverge if given an infinite list.
--   
--   Also note that if you want an efficient left-fold, you probably want
--   to use <a>foldl'</a> instead of <a>foldl</a>. The reason for this is
--   that latter does not force the "inner" results (e.g. <tt>z <tt>f</tt>
--   x1</tt> in the above example) before applying them to the operator
--   (e.g. to <tt>(<tt>f</tt> x2)</tt>). This results in a thunk chain
--   <tt>O(n)</tt> elements long, which then must be evaluated from the
--   outside-in.
--   
--   For a general <a>Foldable</a> structure this should be semantically
--   identical to,
--   
--   <pre>
--   foldl f z = <a>foldl</a> f z . <a>toList</a>
--   </pre>
foldl :: Foldable t => forall b a. () => (b -> a -> b) -> b -> t a -> b

-- | &lt;math&gt;. A strict version of <a>foldr</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldr' :: (a -> b -> b) -> b -> POSet a -> b

-- | &lt;math&gt;. A strict version of <a>foldl</a>. Each application of
--   the operator is evaluated before using the result in the next
--   application. This function is strict in the starting value.
foldl' :: (b -> a -> b) -> b -> POSet a -> b

-- | &lt;math&gt;. The minimal keys of the set.
lookupMin :: PartialOrd k => POSet k -> [k]

-- | &lt;math&gt;. The maximal keys of the set.
lookupMax :: PartialOrd k => POSet k -> [k]

-- | &lt;math&gt;. The elements of a set in unspecified order.
elems :: POSet k -> [k]

-- | &lt;math&gt;. The elements of a set in unspecified order.
toList :: POSet k -> [k]

-- | &lt;math&gt;. Build a set from a list of keys.
fromList :: (PartialOrd k) => [k] -> POSet k
