-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Automatic type inference of generalized tries with Template Haskell.
--
-- Provides a efficient and compact implementation of generalized tries,
-- and Template Haskell tools to generate the necessary translation code.
-- This is meant as a drop-in replacement for Data.Map. The most recent
-- release combines zipper-based ideas from recently proposed changes to
-- Data.Map, as well as heavily optimized ByteString and Vector instances
-- based on the vector package. Since version 2, unit tests and
-- benchmarks have been taken much more seriously, and major
-- optimizations have been made. Compared to Data.Map and Data.Set, on
-- e.g. ByteStrings, TrieMaps support 6-12x faster
-- union, intersection, and difference
-- operations, 2x faster lookup, but 2x slower toList,
-- and 4x slower filter. Other operations are closely tied.
-- TrieMaps tend to use somewhat more memory, and frequently perform
-- better with increased heap space and allocation area.
@package TrieMap
@version 3.0.1
module Data.TrieMap.Modifiers
newtype Ordered a
Ord :: a -> Ordered a
unOrd :: Ordered a -> a
newtype Rev k
Rev :: k -> Rev k
getRev :: Rev k -> k
newtype Key k
Key :: k -> Key k
getKey :: Key k -> k
instance Eq k => Eq (Rev k)
instance Eq a => Eq (Ordered a)
instance Ord a => Ord (Ordered a)
instance Repr k => Repr (Key k)
instance (Repr k, Ord (Rep k)) => Ord (Key k)
instance (Repr k, Eq (Rep k)) => Eq (Key k)
instance Functor Rev
instance Functor Ordered
instance Ord k => Ord (Rev k)
module Data.TrieMap.Representation
-- | The Repr type class denotes that a type can be decomposed to
-- a representation built out of pieces for which the TrieKey
-- class defines a generalized trie structure.
--
-- It is required that, if (Repr a, Eq a), and
-- x, y :: a, then x == y if and only if
-- toRep x == toRep y. It is typically the
-- case that compare x y == compare (toRep x)
-- (toRep y), as well, but this is not strictly required. (It
-- is, however, the case for all instances built into the package.)
--
-- As an additional note, the Key modifier is used for
-- "bootstrapping" Repr instances, allowing a type to be used in
-- its own Repr definition when wrapped in a Key
-- modifier.
class Repr a where { type family Rep a; type family RepList a; }
toRep :: Repr a => a -> Rep a
toRepList :: Repr a => [a] -> RepList a
-- | Given the name of a type constructor, automatically generates an
-- efficient Repr instance. If you have several mutually dependent
-- (or even mutually recursive) types, genRepr will construct
-- instances for all of them.
--
-- genRepr guarantees that any instances it generates are
-- consistent with the ordering that would be generated by deriving
-- (Ord) in the data declaration. That is, if genRepr
-- generates an instance Repr a, then it is guaranteed that if
-- x, y :: a, and a has a derived Ord instance,
-- then compare x y == compare (toRep x) (toRep y).
genRepr :: Name -> Q [Dec]
-- | Given the name of a type constructor, automatically generates an
-- efficient Repr instance. If you have several mutually dependent
-- (or even mutually recursive) types, genOptRepr will construct
-- instances for all of them. The instance generated by genOptRepr
-- may, in some cases, be more efficient than the instance generated by
-- genRepr -- in particular, arguments common to several
-- constructors may be factored out, reducing the complexity of the
-- associated TrieKey instance, but leaving an ordering
-- inconsistent with Ord.
--
-- Therefore, genOptRepr guarantees that any instances it
-- generates are consistent with the ordering that would be generated by
-- deriving (Eq) in the data declaration. That is, if
-- genOptRepr generates an instance Repr a, then it is
-- guaranteed that if x, y :: a, and a has a derived
-- Eq instance, then (x == y) == (toRep x == toRep y).
genOptRepr :: Name -> Q [Dec]
-- | Given a type with an associated Ord instance, generates a
-- representation that will cause its TMap implementation to be
-- essentially equivalent to Data.Map.
genOrdRepr :: Name -> Q [Dec]
module Data.TrieMap.Class
-- | A map from keys k to values a, backed by a trie.
newtype TMap k a
TMap :: TrieMap (Rep k) (Assoc k a) -> TMap k a
getTMap :: TMap k a -> TrieMap (Rep k) (Assoc k a)
-- | A set of values a, backed by a trie.
newtype TSet a
TSet :: TrieMap (Rep a) (Elem a) -> TSet a
getTSet :: TSet a -> TrieMap (Rep a) (Elem a)
-- | TKey k is a handy alias for (Repr k,
-- TrieKey (Rep k)). To make a type an instance of
-- TKey, create a Repr instance that will satisfy
-- TrieKey (Rep k), possibly using the Template
-- Haskell methods provided by Data.TrieMap.Representation.
class (Repr k, TrieKey (Rep k)) => TKey k
-- | A TrieKey k instance implies that k is a
-- standardized representation for which a generalized trie structure can
-- be derived.
class (Ord k, Foldable (TrieMap k)) => TrieKey k where { data family TrieMap k :: * -> *; { sizeM# m = unbox (inline sizeM m) indexM# i# m = case inline indexM (I# i#) m of { (# I# i'#, a, hole #) -> (# i'#, a, hole #) } firstHoleM m = inline extractHoleM m lastHoleM m = inline extractHoleM m insertWithM f k a m = inline searchMC k m (assignM a) (assignM . f) fromListM f = foldl' (\ m (k, a) -> insertWithM (f a) k a m) emptyM fromAscListM = fromListM fromDistAscListM = fromAscListM const unifierM k' k a = searchMC k' (singletonM k a) Just (\ _ _ -> Nothing) } }
instance TKey k => Traversable (TMap k)
instance TKey k => Foldable (TMap k)
instance TKey k => Functor (TMap k)
instance (Repr k, TrieKey (Rep k)) => TKey k
module Data.TrieSet
-- | A set of values a, backed by a trie.
data TSet a
-- | See difference.
(\\) :: TKey a => TSet a -> TSet a -> TSet a
-- | O(1). Is this the empty set?
null :: TKey a => TSet a -> Bool
-- | O(1). The number of elements in the set.
size :: TKey a => TSet a -> Int
-- | Is the element in the set?
member :: TKey a => a -> TSet a -> Bool
-- | Is the element not in the set?
notMember :: TKey a => a -> TSet a -> Bool
-- | Is this a subset? (s1 isSubsetOf s2) tells whether
-- s1 is a subset of s2.
isSubsetOf :: TKey a => TSet a -> TSet a -> Bool
-- | Is this a proper subset? (ie. a subset but not equal).
isProperSubsetOf :: TKey a => TSet a -> TSet a -> Bool
-- | The empty TSet.
empty :: TKey a => TSet a
-- | O(1). Create a singleton set.
singleton :: TKey a => a -> TSet a
-- | Insert an element into the TSet.
insert :: TKey a => a -> TSet a -> TSet a
-- | Delete an element from the TSet.
delete :: TKey a => a -> TSet a -> TSet a
-- | The union of two TSets, preferring the first set when equal
-- elements are encountered.
union :: TKey a => TSet a -> TSet a -> TSet a
-- | The symmetric difference of two TSets.
symmetricDifference :: TKey a => TSet a -> TSet a -> TSet a
-- | Intersection of two TSets. Elements of the result come from the
-- first set.
intersection :: TKey a => TSet a -> TSet a -> TSet a
-- | Difference of two TSets.
difference :: TKey a => TSet a -> TSet a -> TSet a
-- | Filter all elements that satisfy the predicate.
filter :: TKey a => (a -> Bool) -> TSet a -> TSet a
-- | 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. See also split.
partition :: TKey a => (a -> Bool) -> TSet a -> (TSet a, TSet a)
-- | The expression (split x set) is a pair
-- (set1,set2) where set1 comprises the elements of
-- set less than x and set2 comprises the
-- elements of set greater than x.
split :: TKey a => a -> TSet a -> (TSet a, TSet a)
-- | Performs a split but also returns whether the pivot element was
-- found in the original set.
splitMember :: TKey a => a -> TSet a -> (TSet a, Bool, TSet a)
-- | map f s is the set obtained by applying f to
-- each element of s.
--
-- It's worth noting that the size of the result may be smaller if, for
-- some (x,y), x /= y && f x == f y
map :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet b
-- | mapMonotonic f s == map f s, but works only
-- when f is monotonic. The precondition is not checked.
-- Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapMonotonic f s == map f s
-- where ls = toList s
--
mapMonotonic :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet b
-- | Pre-order fold.
foldl :: TKey b => (a -> b -> a) -> a -> TSet b -> a
-- | Post-order fold.
foldr :: TKey a => (a -> b -> b) -> b -> TSet a -> b
-- | The minimal element of the set.
findMin :: TKey a => TSet a -> a
-- | The maximal element of the set.
findMax :: TKey a => TSet a -> a
-- | Delete the minimal element.
deleteMin :: TKey a => TSet a -> TSet a
-- | Delete the maximal element.
deleteMax :: TKey a => TSet a -> TSet a
-- | Delete and find the minimal element.
--
--
-- 'deleteFindMin' set = ('findMin' set, 'deleteMin' set)
--
deleteFindMin :: TKey a => TSet a -> (a, TSet a)
-- | Delete and find the maximal element.
--
--
-- 'deleteFindMax' set = ('findMax' set, 'deleteMax' set)
--
deleteFindMax :: TKey a => TSet a -> (a, TSet a)
-- | Retrieves the minimal key of the set, and the set stripped of that
-- element, or Nothing if passed an empty set.
minView :: TKey a => TSet a -> Maybe (a, TSet a)
-- | Retrieves the maximal key of the set, and the set stripped of that
-- element, or Nothing if passed an empty set.
maxView :: TKey a => TSet a -> Maybe (a, TSet a)
-- | Generate a TMap by mapping on the elements of a TSet.
mapSet :: TKey a => (a -> b) -> TSet a -> TMap a b
-- | See toAscList.
elems :: TKey a => TSet a -> [a]
-- | See toAscList.
toList :: TKey a => TSet a -> [a]
-- | Create a set from a list of elements.
fromList :: TKey a => [a] -> TSet a
-- | Convert the set to an ascending list of elements.
toAscList :: TKey a => TSet a -> [a]
-- | Build a set from an ascending list in linear time. The precondition
-- (input list is ascending) is not checked.
fromAscList :: TKey a => [a] -> TSet a
-- | O(n). Build a set from an ascending list of distinct elements
-- in linear time. The precondition (input list is strictly ascending)
-- is not checked.
fromDistinctAscList :: TKey a => [a] -> TSet a
instance TKey a => Monoid (TSet a)
instance (TKey a, Show a) => Show (TSet a)
instance (TKey a, Ord a) => Ord (TSet a)
instance TKey a => Eq (TSet a)
module Data.TrieMap
-- | TKey k is a handy alias for (Repr k,
-- TrieKey (Rep k)). To make a type an instance of
-- TKey, create a Repr instance that will satisfy
-- TrieKey (Rep k), possibly using the Template
-- Haskell methods provided by Data.TrieMap.Representation.
class (Repr k, TrieKey (Rep k)) => TKey k
-- | A map from keys k to values a, backed by a trie.
data TMap k a
-- | A TLocation represents a TMap with a "hole" at a
-- particular key position.
--
-- TLocations are used for element-wise operations on maps
-- (insertion, deletion and update) in a two-stage process:
--
--
-- - A TLocation (and the value at that position, if any) is
-- obtained from a TMap by searching or indexing. 2. A new
-- TMap is made from a TLocation by either filling the hole
-- with a value (assign) or erasing it (clear).
--
data TLocation k a
-- | O(1). The key marking the position of the "hole" in the map.
key :: TKey k => TLocation k a -> k
-- | before loc is the submap with keys less than
-- key loc.
before :: TKey k => TLocation k a -> TMap k a
-- | after loc is the submap with keys greater than
-- key loc.
after :: TKey k => TLocation k a -> TMap k a
-- | Search the map for the given key, returning the corresponding value
-- (if any) and an updatable location for that key.
--
-- Properties:
--
--
-- case search k m of
-- (Nothing, loc) -> key loc == k && clear loc == m
-- (Just v, loc) -> key loc == k && assign v loc == m
--
--
--
-- lookup k m == fst (search k m)
--
search :: TKey k => k -> TMap k a -> (Maybe a, TLocation k a)
-- | Return the value and an updatable location for the ith key in
-- the map. Calls error if i is out of range.
--
-- Properties:
--
--
-- 0 <= i && i < size m ==>
-- let (v, loc) = index i m in
-- size (before loc) == i && assign v loc == m
--
--
--
-- elemAt i m == let (v, loc) = index i m in (key loc, v)
--
index :: TKey k => Int -> TMap k a -> (a, TLocation k a)
-- | O(log n). Return the value and an updatable location for the
-- least key in the map, or Nothing if the map is empty.
--
-- Properties:
--
--
-- size m > 0 ==>
-- let Just (v, loc) = minLocation i m in
-- size (before loc) == 0 && assign v loc == m
--
--
--
-- findMin m == let Just (v, loc) = minLocation i m in (key loc, v)
--
minLocation :: TKey k => TMap k a -> Maybe (a, TLocation k a)
-- | Return the value and an updatable location for the greatest key in the
-- map, or Nothing if the map is empty.
--
-- Properties:
--
--
-- size m > 0 ==>
-- let Just (v, loc) = maxLocation i m in
-- size (after loc) == 0 && assign v loc == m
--
--
--
-- findMax m == let Just (v, loc) = maxLocation i m in (key loc, v)
--
maxLocation :: TKey k => TMap k a -> Maybe (a, TLocation k a)
-- | Return a map obtained by placing the given value at the location
-- (replacing an existing value, if any).
--
--
-- assign v loc == before loc union singleton (key loc) v union after loc
--
assign :: TKey k => a -> TLocation k a -> TMap k a
-- | Return a map obtained by erasing the location.
--
--
-- clear loc == before loc union after loc
--
clear :: TKey k => TLocation k a -> TMap k a
-- | Find the value at a key. Calls error when the element can not
-- be found.
(!) :: TKey k => TMap k a -> k -> a
-- | Same as difference.
(\\) :: TKey k => TMap k a -> TMap k b -> TMap k a
-- | O(1). Is the map empty?
null :: TKey k => TMap k a -> Bool
-- | O(1). The number of elements in the map.
--
--
-- size empty == 0
-- size (singleton 1 'a') == 1
-- size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3
--
size :: TKey k => TMap k a -> Int
-- | Is the key a member of the map? See also notMember.
--
--
-- member 5 (fromList [(5,'a'), (3,'b')]) == True
-- member 1 (fromList [(5,'a'), (3,'b')]) == False
--
member :: TKey k => k -> TMap k a -> Bool
-- | Is the key not a member of the map? See also member.
--
--
-- notMember 5 (fromList [(5,'a'), (3,'b')]) == False
-- notMember 1 (fromList [(5,'a'), (3,'b')]) == True
--
notMember :: TKey k => k -> TMap k a -> Bool
-- | Lookup the value at a key in the map.
--
-- The function will return the corresponding value as (Just
-- value), or Nothing if the key isn't in the map.
lookup :: TKey k => k -> TMap k a -> Maybe a
-- | The expression (findWithDefault def k map) returns the
-- value at key k or returns default value def when the
-- key is not in the map.
findWithDefault :: TKey k => a -> k -> TMap k a -> a
-- | O(1). The empty map.
empty :: TKey k => TMap k a
-- | O(1). A map with a single element.
singleton :: TKey k => k -> a -> TMap k a
-- | Insert a new key and value in the map. If the key is already present
-- in the map, the associated value is replaced with the supplied value.
-- insert is equivalent to insertWith
-- const.
--
--
-- insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')]
-- insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')]
-- insert 5 'x' empty == singleton 5 'x'
--
insert :: TKey k => k -> a -> TMap k a -> TMap k a
-- | Insert with a function, combining new value and old value.
-- insertWith f key value mp will insert the pair (key,
-- value) into mp if key does not exist in the map. If the key
-- does exist, the function will insert the pair (key, f new_value
-- old_value).
--
--
-- insertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]
-- insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
-- insertWith (++) 5 "xxx" empty == singleton 5 "xxx"
--
insertWith :: TKey k => (a -> a -> a) -> k -> a -> TMap k a -> TMap k a
-- | Insert with a function, combining key, new value and old value.
-- insertWithKey f key value mp will insert the pair
-- (key, value) into mp if key does not exist in the map. If the
-- key does exist, the function will insert the pair (key,f key
-- new_value old_value). Note that the key passed to f is the same
-- key passed to insertWithKey.
--
--
-- let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
-- insertWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:xxx|a")]
-- insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]
-- insertWithKey f 5 "xxx" empty == singleton 5 "xxx"
--
insertWithKey :: TKey k => (k -> a -> a -> a) -> k -> a -> TMap k a -> TMap k a
-- | Combines insert operation with old value retrieval. The expression
-- (insertLookupWithKey f k x map) is a pair where the
-- first element is equal to (lookup k map) and the
-- second element equal to (insertWithKey f k x map).
--
--
-- let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value
-- insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])
-- insertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "xxx")])
-- insertLookupWithKey f 5 "xxx" empty == (Nothing, singleton 5 "xxx")
--
insertLookupWithKey :: TKey k => (k -> a -> a -> a) -> k -> a -> TMap k a -> (Maybe a, TMap k a)
-- | Delete a key and its value from the map. When the key is not a member
-- of the map, the original map is returned.
--
--
-- delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
-- delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
-- delete 5 empty == empty
--
delete :: TKey k => k -> TMap k a -> TMap k a
-- | Update a value at a specific key with the result of the provided
-- function. When the key is not a member of the map, the original map is
-- returned.
--
--
-- adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
-- adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
-- adjust ("new " ++) 7 empty == empty
--
adjust :: TKey k => (a -> a) -> k -> TMap k a -> TMap k a
-- | Adjust a value at a specific key. When the key is not a member of the
-- map, the original map is returned.
--
--
-- let f key x = (show key) ++ ":new " ++ x
-- adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
-- adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
-- adjustWithKey f 7 empty == empty
--
adjustWithKey :: TKey k => (k -> a -> a) -> k -> TMap k a -> TMap k a
-- | The expression (update f k map) updates the value
-- x at k (if it is in the map). If (f x) is
-- Nothing, the element is deleted. If it is (Just
-- y), the key k is bound to the new value y.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing
-- update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]
-- update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
-- update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
update :: TKey k => (a -> Maybe a) -> k -> TMap k a -> TMap k a
-- | The expression (updateWithKey f k map) updates the
-- value x at k (if it is in the map). If (f k
-- x) is Nothing, the element is deleted. If it is
-- (Just y), the key k is bound to the new value
-- y.
--
--
-- let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
-- updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]
-- updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
-- updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
updateWithKey :: TKey k => (k -> a -> Maybe a) -> k -> TMap k a -> TMap k a
-- | The expression (alter f k map) alters the value
-- x at k, or absence thereof. alter can be used
-- to insert, delete, or update a value in a TMap. In short:
-- lookup k (alter f k m) = f (lookup k m).
alter :: TKey k => (Maybe a -> Maybe a) -> k -> TMap k a -> TMap k a
-- | The expression (union t1 t2) takes the left-biased
-- union of t1 and t2. It prefers t1 when
-- duplicate keys are encountered, i.e. (union ==
-- unionWith const). The implementation uses the
-- efficient hedge-union algorithm. Hedge-union is more efficient
-- on (bigset `union` smallset).
--
--
-- union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--
union :: TKey k => TMap k a -> TMap k a -> TMap k a
-- | O(n+m). Union with a combining function. The implementation
-- uses the efficient hedge-union algorithm.
--
--
-- unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--
unionWith :: TKey k => (a -> a -> a) -> TMap k a -> TMap k a -> TMap k a
unionWithKey :: TKey k => (k -> a -> a -> a) -> TMap k a -> TMap k a -> TMap k a
-- | Union with a combining function. The implementation uses the efficient
-- hedge-union algorithm.
unionMaybeWith :: TKey k => (a -> a -> Maybe a) -> TMap k a -> TMap k a -> TMap k a
-- | Union with a combining function. The implementation uses the efficient
-- hedge-union algorithm. Hedge-union is more efficient on (bigset
-- `union` smallset).
--
--
-- let f key left_value right_value = Just ((show key) ++ ":" ++ left_value ++ "|" ++ right_value)
-- unionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "5:a|A"), (7, "C")]
--
unionMaybeWithKey :: TKey k => (k -> a -> a -> Maybe a) -> TMap k a -> TMap k a -> TMap k a
-- | symmetricDifference is equivalent to unionMaybeWith
-- ( _ _ -> Nothing).
symmetricDifference :: TKey k => TMap k a -> TMap k a -> TMap k a
-- | Difference of two maps. Return elements of the first map not existing
-- in the second map. The implementation uses an efficient hedge
-- algorithm comparable with hedge-union.
--
--
-- difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
--
difference :: TKey k => TMap k a -> TMap k b -> TMap k a
-- | 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 Nothing, the element is discarded (proper
-- set difference). If it returns (Just y), the element
-- is updated with a new value y. The implementation uses an
-- efficient hedge algorithm comparable with hedge-union.
--
--
-- let f al ar = if al == "b" then Just (al ++ ":" ++ ar) else Nothing
-- differenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])
-- == singleton 3 "b:B"
--
differenceWith :: TKey k => (a -> b -> Maybe a) -> TMap k a -> TMap k b -> TMap k a
-- | Difference with a combining function. When two equal keys are
-- encountered, the combining function is applied to the key and both
-- values. If it returns Nothing, the element is discarded (proper
-- set difference). If it returns (Just y), the element
-- is updated with a new value y. The implementation uses an
-- efficient hedge algorithm comparable with hedge-union.
--
--
-- let f k al ar = if al == "b" then Just ((show k) ++ ":" ++ al ++ "|" ++ ar) else Nothing
-- differenceWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (10, "C")])
-- == singleton 3 "3:b|B"
--
differenceWithKey :: TKey k => (k -> a -> b -> Maybe a) -> TMap k a -> TMap k b -> TMap k a
-- | Intersection of two maps. Return data in the first map for the keys
-- existing in both maps. (intersection m1 m2 ==
-- intersectionWith const m1 m2).
--
--
-- intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a"
--
intersection :: TKey k => TMap k a -> TMap k b -> TMap k a
-- | Intersection with a combining function.
--
--
-- intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
--
intersectionWith :: TKey k => (a -> b -> c) -> TMap k a -> TMap k b -> TMap k c
-- | Intersection with a combining function. Intersection is more efficient
-- on (bigset `intersection` smallset).
--
--
-- let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar
-- intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A"
--
intersectionWithKey :: TKey k => (k -> a -> b -> c) -> TMap k a -> TMap k b -> TMap k c
-- | intersectionMaybeWith f m1 m2 is equivalent to
-- mapMaybe id (intersectionWith f m1 m2).
intersectionMaybeWith :: TKey k => (a -> b -> Maybe c) -> TMap k a -> TMap k b -> TMap k c
-- | intersectionMaybeWithKey f m1 m2 is equivalent to
-- mapMaybe id (intersectionWithKey f m1
-- m2).
intersectionMaybeWithKey :: TKey k => (k -> a -> b -> Maybe c) -> TMap k a -> TMap k b -> TMap k c
-- | Map a function over all values in the map.
--
--
-- map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--
map :: TKey k => (a -> b) -> TMap k a -> TMap k b
-- | Map a function over all values in the map.
--
--
-- let f key x = (show key) ++ ":" ++ x
-- mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]
--
mapWithKey :: TKey k => (k -> a -> b) -> TMap k a -> TMap k b
-- | mapKeys f s is the map obtained by applying f
-- to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the value at the
-- smallest of these keys is retained.
--
--
-- mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]
-- mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c"
-- mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c"
--
mapKeys :: (TKey k, TKey k') => (k -> k') -> TMap k a -> TMap k' a
-- | mapKeysWith c f s is the map obtained by applying
-- f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the associated values
-- will be combined using c.
--
--
-- mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab"
-- mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab"
--
mapKeysWith :: (TKey k, TKey k') => (a -> a -> a) -> (k -> k') -> TMap k a -> TMap k' a
-- | mapKeysMonotonic f s == mapKeys f s, but works
-- only when f is strictly monotonic. That is, for any values
-- x and y, if x < y then f
-- x < f y. The precondition is not checked.
-- Semi-formally, we have:
--
--
-- and [x < y ==> f x < f y | x <- ls, y <- ls]
-- ==> mapKeysMonotonic f s == mapKeys f s
-- where ls = keys s
--
--
-- This means that f maps distinct original keys to distinct
-- resulting keys. This function has better performance than
-- mapKeys.
--
--
-- mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]
--
mapKeysMonotonic :: (TKey k, TKey k') => (k -> k') -> TMap k a -> TMap k' a
-- | Map each key/element pair to an action, evaluate these actions from
-- left to right, and collect the results.
traverseWithKey :: (TKey k, Applicative f) => (k -> a -> f b) -> TMap k a -> f (TMap k b)
-- | Post-order fold. The function will be applied from the lowest value to
-- the highest.
foldrWithKey :: TKey k => (k -> a -> b -> b) -> b -> TMap k a -> b
-- | Pre-order fold. The function will be applied from the highest value to
-- the lowest.
foldlWithKey :: TKey k => (b -> k -> a -> b) -> b -> TMap k a -> b
-- | Return all elements of the map in the ascending order of their keys.
--
--
-- elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
-- elems empty == []
--
elems :: TKey k => TMap k a -> [a]
-- | Return all keys of the map in ascending order.
--
--
-- keys (fromList [(5,"a"), (3,"b")]) == [3,5]
-- keys empty == []
--
keys :: TKey k => TMap k a -> [k]
-- | The set of all keys of the map.
--
--
-- keysSet (fromList [(5,"a"), (3,"b")]) == Data.TrieSet.fromList [3,5]
-- keysSet empty == Data.TrieSet.empty
--
keysSet :: TKey k => TMap k a -> TSet k
-- | Return all key/value pairs in the map in ascending key order.
--
--
-- assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]
-- assocs empty == []
--
assocs :: TKey k => TMap k a -> [(k, a)]
-- | Build a map from a list of key/value pairs. See also
-- fromAscList. If the list contains more than one value for the
-- same key, the last value for the key is retained.
--
--
-- fromList [] == empty
-- fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]
-- fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]
--
fromList :: TKey k => [(k, a)] -> TMap k a
-- | Build a map from a list of key/value pairs with a combining function.
-- See also fromAscListWith.
--
--
-- fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
-- fromListWith (++) [] == empty
--
fromListWith :: TKey k => (a -> a -> a) -> [(k, a)] -> TMap k a
-- | Build a map from a list of key/value pairs with a combining function.
-- See also fromAscListWith.
--
--
-- fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]
-- fromListWith (++) [] == empty
--
fromListWithKey :: TKey k => (k -> a -> a -> a) -> [(k, a)] -> TMap k a
-- | Build a map from an ascending list in linear time. The precondition
-- (input list is ascending) is not checked.
--
--
-- fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
-- fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
--
fromAscList :: TKey k => [(k, a)] -> TMap k a
-- | Build a map from an ascending list in linear time with a combining
-- function for equal keys. The precondition (input list is ascending)
-- is not checked.
--
--
-- fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")]
--
fromAscListWith :: TKey k => (a -> a -> a) -> [(k, a)] -> TMap k a
-- | Build a map from an ascending list in linear time. The precondition
-- (input list is ascending) is not checked.
--
--
-- fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
-- fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")]
--
fromAscListWithKey :: TKey k => (k -> a -> a -> a) -> [(k, a)] -> TMap k a
-- | Build a map from an ascending list of distinct elements in linear
-- time. The precondition is not checked.
--
--
-- fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")]
--
fromDistinctAscList :: TKey k => [(k, a)] -> TMap k a
-- | Filter all values that satisfy the predicate.
--
--
-- filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
-- filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty
-- filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty
--
filter :: TKey k => (a -> Bool) -> TMap k a -> TMap k a
-- | Filter all keys/values that satisfy the predicate.
--
--
-- filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
filterWithKey :: TKey k => (k -> a -> Bool) -> TMap k a -> TMap k a
-- | Partition the map according to a predicate. The first map contains all
-- elements that satisfy the predicate, the second all elements that fail
-- the predicate. See also split.
--
--
-- partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
-- partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
-- partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--
partition :: TKey k => (a -> Bool) -> TMap k a -> (TMap k a, TMap k a)
-- | Partition the map according to a predicate. The first map contains all
-- elements that satisfy the predicate, the second all elements that fail
-- the predicate. See also split.
--
--
-- partition (> "a") (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
-- partition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
-- partition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--
partitionWithKey :: TKey k => (k -> a -> Bool) -> TMap k a -> (TMap k a, TMap k a)
-- | O(n). Map values and collect the Just results.
--
--
-- let f x = if x == "a" then Just "new a" else Nothing
-- mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"
--
mapMaybe :: TKey k => (a -> Maybe b) -> TMap k a -> TMap k b
-- | Map keys/values and collect the Just results.
--
--
-- let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing
-- mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"
--
mapMaybeWithKey :: TKey k => (k -> a -> Maybe b) -> TMap k a -> TMap k b
-- | Map values and separate the Left and Right results.
--
--
-- let f a = if a < "c" then Left a else Right a
-- mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
-- == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])
--
-- mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
-- == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
--
mapEither :: TKey k => (a -> Either b c) -> TMap k a -> (TMap k b, TMap k c)
-- | Map keys/values and separate the Left and Right results.
--
--
-- let f k a = if k < 5 then Left (k * 2) else Right (a ++ a)
-- mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
-- == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])
--
-- mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])
-- == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")])
--
mapEitherWithKey :: TKey k => (k -> a -> Either b c) -> TMap k a -> (TMap k b, TMap k c)
-- | The expression (split k map) is a pair
-- (map1,map2) where the keys in map1 are smaller than
-- k and the keys in map2 larger than k. Any
-- key equal to k is found in neither map1 nor
-- map2.
--
--
-- split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")])
-- split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a")
-- split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a")
-- split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty)
-- split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty)
--
split :: TKey k => k -> TMap k a -> (TMap k a, TMap k a)
-- | The expression (splitLookup k map) splits a map just
-- like split but also returns lookup k map.
--
--
-- splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")])
-- splitLookup 3 (fromList [(5,"a"), (3,"b")]) == (empty, Just "b", singleton 5 "a")
-- splitLookup 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Nothing, singleton 5 "a")
-- splitLookup 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", Just "a", empty)
-- splitLookup 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], Nothing, empty)
--
splitLookup :: TKey k => k -> TMap k a -> (TMap k a, Maybe a, TMap k a)
-- | This function is defined as (isSubmapOf =
-- isSubmapOfBy (==)).
isSubmapOf :: (TKey k, Eq a) => TMap k a -> TMap k a -> Bool
-- | The expression (isSubmapOfBy f t1 t2) returns
-- True if all keys in t1 are in tree t2, and
-- when f returns True when applied to their respective
-- values. For example, the following expressions are all True:
--
--
-- isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)])
--
--
-- But the following are all False:
--
--
-- isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)])
-- isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)])
--
isSubmapOfBy :: TKey k => (a -> b -> Bool) -> TMap k a -> TMap k b -> Bool
-- | Lookup the index of a key. The index is a number from 0
-- up to, but not including, the size of the map.
--
--
-- lookupIndex 2 (fromList [(5,"a"), (3,"b")]) == Nothing
-- lookupIndex 3 (fromList [(5,"a"), (3,"b")]) == Just 0
-- lookupIndex 5 (fromList [(5,"a"), (3,"b")]) == Just 1
-- lookupIndex 6 (fromList [(5,"a"), (3,"b")]) == Nothing
--
lookupIndex :: TKey k => k -> TMap k a -> Maybe Int
-- | Return the index of a key. The index is a number from 0
-- up to, but not including, the size of the map. Calls
-- error when the key is not a member of the map.
--
--
-- findIndex 2 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map
-- findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0
-- findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1
-- findIndex 6 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map
--
findIndex :: TKey k => k -> TMap k a -> Int
-- | Retrieve an element by index. Calls error when an
-- invalid index is used.
--
--
-- elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b")
-- elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a")
-- elemAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range
--
elemAt :: TKey k => Int -> TMap k a -> (k, a)
-- | Update the element at index. Calls error when an invalid
-- index is used.
--
--
-- updateAt (\ _ _ -> Just "x") 0 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")]
-- updateAt (\ _ _ -> Just "x") 1 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "x")]
-- updateAt (\ _ _ -> Just "x") 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range
-- updateAt (\ _ _ -> Just "x") (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range
-- updateAt (\_ _ -> Nothing) 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
-- updateAt (\_ _ -> Nothing) 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
-- updateAt (\_ _ -> Nothing) 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range
-- updateAt (\_ _ -> Nothing) (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range
--
updateAt :: TKey k => (k -> a -> Maybe a) -> Int -> TMap k a -> TMap k a
-- | Delete the element at index. Defined as (deleteAt i
-- map = updateAt (k x -> Nothing) i map).
--
--
-- deleteAt 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
-- deleteAt 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
-- deleteAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range
-- deleteAt (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range
--
deleteAt :: TKey k => Int -> TMap k a -> TMap k a
-- | The minimal key of the map. Calls error if the map is empty.
--
--
-- findMin (fromList [(5,"a"), (3,"b")]) == (3,"b")
-- findMin empty Error: empty map has no minimal element
--
findMin :: TKey k => TMap k a -> (k, a)
-- | The maximal key of the map. Calls error if the map is empty.
--
--
-- findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
-- findMax empty Error: empty map has no maximal element
--
findMax :: TKey k => TMap k a -> (k, a)
-- | Delete the minimal key. Returns an empty map if the map is empty.
--
--
-- deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")]
-- deleteMin empty == empty
--
deleteMin :: TKey k => TMap k a -> TMap k a
-- | Delete the maximal key. Returns an empty map if the map is empty.
--
--
-- deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]
-- deleteMax empty == empty
--
deleteMax :: TKey k => TMap k a -> TMap k a
-- | Delete and find the minimal element.
--
--
-- deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
-- deleteFindMin Error: can not return the minimal element of an empty map
--
deleteFindMin :: TKey k => TMap k a -> ((k, a), TMap k a)
-- | Delete and find the minimal element.
--
--
-- deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")])
-- deleteFindMin Error: can not return the minimal element of an empty map
--
deleteFindMax :: TKey k => TMap k a -> ((k, a), TMap k a)
-- | Update the value at the minimal key.
--
--
-- updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")]
-- updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
updateMin :: TKey k => (a -> Maybe a) -> TMap k a -> TMap k a
-- | Update the value at the maximal key.
--
--
-- updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")]
-- updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--
updateMax :: TKey k => (a -> Maybe a) -> TMap k a -> TMap k a
-- | Update the value at the minimal key.
--
--
-- updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")]
-- updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
updateMinWithKey :: TKey k => (k -> a -> Maybe a) -> TMap k a -> TMap k a
-- | Update the value at the maximal key.
--
--
-- updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")]
-- updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--
updateMaxWithKey :: TKey k => (k -> a -> Maybe a) -> TMap k a -> TMap k a
-- | Retrieves the value associated with minimal key of the map, and the
-- map stripped of that element, or Nothing if passed an empty
-- map.
--
--
-- minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")
-- minView empty == Nothing
--
minView :: TKey k => TMap k a -> Maybe (a, TMap k a)
-- | Retrieves the value associated with maximal key of the map, and the
-- map stripped of that element, or Nothing if passed an
--
--
-- maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")
-- maxView empty == Nothing
--
maxView :: TKey k => TMap k a -> Maybe (a, TMap k a)
-- | Retrieves the minimal (key,value) pair of the map, and the map
-- stripped of that element, or Nothing if passed an empty map.
--
--
-- minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a")
-- minViewWithKey empty == Nothing
--
minViewWithKey :: TKey k => TMap k a -> Maybe ((k, a), TMap k a)
-- | O(log n). Retrieves the maximal (key,value) pair of the map,
-- and the map stripped of that element, or Nothing if passed an
-- empty map.
--
--
-- maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b")
-- maxViewWithKey empty == Nothing
--
maxViewWithKey :: TKey k => TMap k a -> Maybe ((k, a), TMap k a)
instance TKey k => Monoid (TMap k a)
instance (Ord k, TKey k, Ord a) => Ord (TMap k a)
instance (Eq k, TKey k, Eq a) => Eq (TMap k a)
instance (Show k, Show a, TKey k) => Show (TMap k a)