-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | An implementation of generalized tries with sophisticated map type inference. -- -- Generalized trie implementation that automatically infers map types. -- Keys must implement the class TrieMap.Algebraic.Algebraic, -- which declares that they are isomorphic to an algebraic type, -- defined recursively as follows: -- -- -- -- This package exports almost the entire collection of methods available -- in Data.Map, and several new methods as well. In addition, each method -- will automatically infer the correct map type. @package TrieMap @version 0.0.1.1 module TrieMap.Algebraic -- | Algebraic refers to a type with an algebraic representation, -- armed with methods to convert in each direction. toAlg and -- fromAlg should preserve equality and ordering. class Algebraic k where { type family Alg k; } toAlg :: (Algebraic k) => k -> Alg k fromAlg :: (Algebraic k) => Alg k -> k newtype Ordered k Ord :: k -> Ordered k unOrd :: Ordered k -> k instance Algebraic IntSet instance (Algebraic a) => Algebraic (Set a) instance (Algebraic v) => Algebraic (IntMap v) instance (Algebraic k, Algebraic v) => Algebraic (Map k v) instance Algebraic Rational instance Algebraic Double instance Algebraic Float instance Algebraic Char instance Algebraic Int instance Algebraic Bool instance (Algebraic a) => Algebraic (Maybe a) instance Algebraic () instance (Algebraic k) => Algebraic [k] instance (Algebraic k1, Algebraic k2) => Algebraic (Either k1 k2) instance (Algebraic a, Algebraic b, Algebraic c, Algebraic d, Algebraic e) => Algebraic (a, b, c, d, e) instance (Algebraic a, Algebraic b, Algebraic c, Algebraic d) => Algebraic (a, b, c, d) instance (Algebraic a, Algebraic b, Algebraic c) => Algebraic (a, b, c) instance (Algebraic k1, Algebraic k2) => Algebraic (k1, k2) -- | We will use the following terminology: -- -- An algebraic type is a type isomorphic to an algebraic type, as -- defined in the package description. This isomorphism is declared via -- the type class Algebraic, where Alg k is -- algebraic. It is assumed for purposes of ordering that this -- isomorphism is order- and equality-preserving. We also require that if -- k is algebraic, Alg k ~ k. -- -- These methods will automatically infer the correct type of a -- TrieMap on any given argument. For example, -- -- 
--   fromList [(("alphabet", Just (0.2 :: Double), True), "wxyz")]
--
-- -- returns a variable of type -- -- 
--   TrieMap (String, Double, Bool) (RadixTrie Int IntMap `ProdMap` UnionMap Maybe (Map Double) `ProdMap` UnionMap Maybe Maybe) String
--
-- -- The inference was done entirely automatically. Note also: -- -- -- -- (If you plan to use these maps in type arguments, it is strongly -- suggested that you either reproduce the context (Algebraic -- k, TrieKey (Alg k) m) => TrieMap k m a, or you -- create a type alias!) module TrieMap -- | A TrieMap is a size-tracking wrapper around a generalized trie -- map. data TrieMap k m a -- | TrieKey defines a bijection between map types and algebraic key types. class (Eq a, Foldable m, Traversable m) => TrieKey a m | a -> m, m -> a -- | Algebraic refers to a type with an algebraic representation, -- armed with methods to convert in each direction. toAlg and -- fromAlg should preserve equality and ordering. class Algebraic k where { type family Alg k; } toAlg :: (Algebraic k) => k -> Alg k fromAlg :: (Algebraic k) => Alg k -> k -- | ProdMap is used to hold a map on the product of two key types. data ProdMap m1 m2 v -- | UnionMap is used to hold a map on the sum of two key types. data UnionMap m1 m2 v -- | RadixTrie is used to hold a map on a list of keys. data RadixTrie k m v -- | Find the value at a key. Calls error when the element can not -- be found. -- -- 
--   fromList [(5,'a'), (3,'b')] ! 1    Error: element not in the map
--   fromList [(5,'a'), (3,'b')] ! 5 == 'a'
--
(!) :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> k -> a -- | Same as difference. (\\) :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m a -- | Check if the specified map is empty. null :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Bool -- | Returns the size of the specified map. size :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> Bool -- | Lookup the value of 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> Maybe a -- | Find the value at a key. Calls error when the element can not -- be found. find :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> 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 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'
--   findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'
--
findWithDefault :: (Algebraic k, TrieKey (Alg k) m) => a -> k -> TrieMap k m a -> a empty :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -- | O(1). A map with a single element. -- -- 
--   singleton 1 'a'        == fromList [(1, 'a')]
--
singleton :: (Algebraic k, TrieKey (Alg k) m) => k -> a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> a -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> TrieMap k m 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). insertLookupWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> k -> a -> TrieMap k m a -> (Maybe a, TrieMap k m 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 is equivalent to alter (const -- Nothing). delete :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m a -- | Lookup and update. See also updateWithKey. The function returns -- changed value, if it is updated. Returns the original key value if the -- map entry is deleted. -- -- 
--   let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing
--   updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "5:new a", fromList [(3, "b"), (5, "5:new a")])
--   updateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing,  fromList [(3, "b"), (5, "a")])
--   updateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")
--
updateLookupWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m 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 Map. In short : -- lookup k (alter f k m) = f (lookup k m). -- -- 
--   let f _ = Nothing
--   alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]
--   alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"
--   
--   let f _ = Just "c"
--   alter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]
--   alter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]
--
alter :: (Algebraic k, TrieKey (Alg k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> TrieMap k m a -- | The expression (alterLookup f k map) alters the value -- x at k, or absence thereof, and returns the old -- value. alterLookup can be used to insert, delete, or update a -- value in a Map. -- -- In short : alterLookup f k m = (lookup k m, alter f k m). alterLookup :: (Algebraic k, TrieKey (Alg k) m) => (Maybe a -> Maybe a) -> k -> TrieMap k m a -> (Maybe a, TrieMap k m a) -- | O(n+m). 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). -- -- 
--   union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]
--
union :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m a -- | O(n+m). Union with a combining function. -- -- 
--   unionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]
--
unionWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a -- | O(n+m). Union with a combining function. -- -- 
--   let f key left_value right_value = (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")]
--
unionWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a unions :: (Algebraic k, TrieKey (Alg k) m) => [TrieMap k m a] -> TrieMap k m a unionsWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [TrieMap k m a] -> TrieMap k m a unionsWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [TrieMap k m a] -> TrieMap k m a -- | O(n+m). Union with a combining function that may discard some -- elements. unionMaybeWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a -- | O(n+m). Union with a combining function that may discard some -- elements. unionMaybeWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -> TrieMap k m a -- | O(n+m). Symmetric difference. Equivalent to unionMaybeWith -- ( _ _ -> Nothing). symDifference :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m a -> TrieMap k m a -- | O(n+m). 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m a -- | O(n+m). Intersection with a combining function. -- -- 
--   intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA"
--
intersectionWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c -- | O(n+m). Intersection with a combining function. -- -- 
--   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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c -- | O(n+m). Intersection of two maps with a combining function that -- may discard some elements. intersectionMaybeWith :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c -- | O(n+m). Intersection of two maps with a combining function that -- may discard some elements. intersectionMaybeWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> Maybe c) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m c -- | O(n+m). Difference of two maps. Return elements of the first -- map not existing in the second map. -- -- 
--   difference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 3 "b"
--
difference :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m b -> TrieMap k m a -- | O(n+m). 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. -- -- 
--   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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m a -- | O(n+m). 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. -- -- 
--   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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> Maybe a) -> TrieMap k m a -> TrieMap k m b -> TrieMap k m a -- | O(n). Map a function over all values in the map. -- -- 
--   map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]
--
map :: (Algebraic k, TrieKey (Alg k) m) => (a -> b) -> TrieMap k m a -> TrieMap k m b -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b) -> TrieMap k m a -> TrieMap k m b -- | Equivalent to traverse. mapApp :: (Algebraic k, TrieKey (Alg k) m, Applicative f) => (a -> f b) -> TrieMap k m a -> f (TrieMap k m b) -- | Essentially equivalent to traverse with a function that takes -- both the key and the value as arguments. mapAppWithKey :: (Algebraic k, TrieKey (Alg k) m, Applicative f) => (k -> a -> f b) -> TrieMap k m a -> f (TrieMap k m b) -- | 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe b) -> TrieMap k m a -> TrieMap k m b -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe b) -> TrieMap k m a -> TrieMap k m b -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c) -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Either b c) -> TrieMap k m a -> (TrieMap k m b, TrieMap k m c) -- | 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 :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 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 :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (a -> a -> a) -> (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 a -- | O(n). 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")]
--   valid (mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")])) == True
--   valid (mapKeysMonotonic (\ _ -> 1)     (fromList [(5,"a"), (3,"b")])) == False
--
mapKeysMonotonic :: (Algebraic k1, Algebraic k2, TrieKey (Alg k1) m1, TrieKey (Alg k2) m2) => (k1 -> k2) -> TrieMap k1 m1 a -> TrieMap k2 m2 a -- | O(n). Fold the values in the map, such that fold f z -- == foldr f z . elems. For example, -- -- 
--   elems map = fold (:) [] map
--
-- -- 
--   let f a len = len + (length a)
--   fold f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
fold :: (TrieKey k m) => (a -> b -> b) -> b -> TrieMap k m a -> b -- | O(n). Fold the keys and values in the map, such that -- foldWithKey f z == foldr (uncurry f) z . -- assocs. For example, -- -- 
--   keys map = foldWithKey (\k x ks -> k:ks) [] map
--
-- -- 
--   let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"
--   foldWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"
--
foldWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> b -> b) -> b -> TrieMap k m a -> b -- | O(n). Return all elements of the map in the ascending order of -- their keys. -- -- 
--   elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]
--   elems empty == []
--
elems :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [a] -- | O(n). Return all keys of the map in ascending order. -- -- 
--   keys (fromList [(5,"a"), (3,"b")]) == [3,5]
--   keys empty == []
--
keys :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> [k] -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m a -- | Build a map from a list of key/value pairs with a combining function. -- See also fromAscListWithKey. -- -- 
--   let f k a1 a2 = (show k) ++ a1 ++ a2
--   fromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]
--   fromListWithKey f [] == empty
--
fromListWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m a -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m a -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> a -> a) -> [(k, a)] -> TrieMap k m a -- | O(n). 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. -- -- 
--   let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2
--   fromAscListWithKey f [(3,"b"), (5,"a"), (5,"b"), (5,"b")] == fromList [(3, "b"), (5, "5:b5:ba")]
--
fromAscListWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> a -> a) -> [(k, a)] -> TrieMap k m a -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => [(k, a)] -> TrieMap k m a -- | O(n). 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Bool) -> TrieMap k m a -> TrieMap k m a -- | O(n). Filter all keys/values that satisfy the predicate. -- -- 
--   filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"
--
filterWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Bool) -> TrieMap k m a -> TrieMap k m a -- | O(n). 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. -- -- 
--   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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a) -- | O(n). 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. -- -- 
--   partitionWithKey (\ k _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (singleton 5 "a", singleton 3 "b")
--   partitionWithKey (\ k _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)
--   partitionWithKey (\ k _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])
--
partitionWithKey :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Bool) -> TrieMap k m a -> (TrieMap k m a, TrieMap k m a) -- | 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> (TrieMap k m a, TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => k -> TrieMap k m a -> (TrieMap k m a, Maybe a, TrieMap k m a) -- | O(n+m). This function is defined as (isSubmapOf = -- isSubmapOfBy (==)). isSubmapOf :: (Algebraic k, TrieKey (Alg k) m, Eq a) => TrieMap k m a -> TrieMap k m a -> Bool -- | O(n+m). 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> b -> Bool) -> TrieMap k m a -> TrieMap k m b -> Bool -- | 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> (k, a) -- | The minimal key of the map, if any. Returns Nothing if the map -- is empty. -- -- 
--   getMin (fromList [(5,"a"), (3,"b")]) == Just (3,"b")
--   getMin empty                         == Nothing
--
getMin :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (k, a) -- | The maximal key of the map. Calls error is the map is empty. -- -- 
--   findMax (fromList [(5,"a"), (3,"b")]) == (5,"a")
--   findMax empty                            Error: empty map has no maximal element
--
findMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> (k, a) -- | The maximal key of the map, if any. Returns Nothing if the map -- is empty. -- -- 
--   getMax (fromList [(5,"a"), (3,"b")]) == Just (5,"a")
--   getMax empty                         == Nothing
--
getMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> ((k, a), TrieMap k m a) -- | Delete and find the maximal element. -- -- 
--   deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")])
--   deleteFindMax empty                                      Error: can not return the maximal element of an empty map
--
deleteFindMax :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> ((k, a), TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (a -> Maybe a) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => (k -> a -> Maybe a) -> TrieMap k m a -> TrieMap k m a -- | Retrieves the value associated with the 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (a, TrieMap k m a) -- | Retrieves the value associated with the 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe (a, TrieMap k m 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m a) -- | 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 :: (Algebraic k, TrieKey (Alg k) m) => TrieMap k m a -> Maybe ((k, a), TrieMap k m a) instance (Algebraic k, TrieKey (Alg k) m) => Monoid (TrieMap k m a) instance (Traversable m) => Traversable (TrieMap k m) instance (Foldable m) => Foldable (TrieMap k m) instance (Functor m) => Functor (TrieMap k m) instance (Algebraic k, Algebraic a, TrieKey (Alg k) m) => Algebraic (TrieMap k m a) instance (Show k, Show a, Algebraic k, TrieKey (Alg k) m) => Show (TrieMap k m a) instance (Ord k, Ord a, Algebraic k, TrieKey (Alg k) m) => Ord (TrieMap k m a) instance (Eq k, Eq a, Algebraic k, TrieKey (Alg k) m) => Eq (TrieMap k m a)