-- 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. @package TrieMap @version 1.5.0 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.TH -- | Given the name of a type constructor, automatically generates an -- efficient Repr instance. genRepr :: 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.Representation class Repr a where { type family Rep a; } toRep :: Repr a => a -> Rep a fromRep :: Repr a => Rep a -> a instance Repr CDouble instance Repr CFloat instance Repr CTime instance Repr CClock instance Repr CULLong instance Repr CLLong instance Repr CULong instance Repr CLong instance Repr CUInt instance Repr CUShort instance Repr CShort instance Repr CUChar instance Repr CSChar instance Repr CChar instance Repr CInt instance RealFloat a[ayGS] => Repr (Complex a[ayGS]) instance Repr (Maybe a[a5pX]) instance Integral a[ayFA] => Repr (Ratio a[ayFA]) instance Repr (Tree a[ayEL]) instance Repr Bool instance Repr Double instance Repr Float instance (TKey k, Repr a) => Repr (TMap k a) module Data.TrieMap class (Repr k, TrieKey (Rep k)) => TKey k 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: -- --
    --
  1. 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).
    2. --
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) module Data.TrieSet data TSet a (\\) :: TKey a => TSet a -> TSet a -> TSet a null :: TKey a => TSet a -> Bool size :: TKey a => TSet a -> Int member :: TKey a => a -> TSet a -> Bool notMember :: TKey a => a -> TSet a -> Bool isSubsetOf :: TKey a => TSet a -> TSet a -> Bool isProperSubsetOf :: TKey a => TSet a -> TSet a -> Bool empty :: TKey a => TSet a singleton :: TKey a => a -> TSet a insert :: TKey a => a -> TSet a -> TSet a delete :: TKey a => a -> TSet a -> TSet a union :: TKey a => TSet a -> TSet a -> TSet a symmetricDifference :: TKey a => TSet a -> TSet a -> TSet a intersection :: TKey a => TSet a -> TSet a -> TSet a difference :: TKey a => TSet a -> TSet a -> TSet a filter :: TKey a => (a -> Bool) -> TSet a -> TSet a partition :: TKey a => (a -> Bool) -> TSet a -> (TSet a, TSet a) split :: TKey a => a -> TSet a -> (TSet a, TSet a) splitMember :: TKey a => a -> TSet a -> (TSet a, Bool, TSet a) map :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet b mapMonotonic :: (TKey a, TKey b) => (a -> b) -> TSet a -> TSet b fold :: TKey a => (a -> b -> b) -> b -> TSet a -> b foldl :: TKey b => (a -> b -> a) -> a -> TSet b -> a foldr :: TKey a => (a -> b -> b) -> b -> TSet a -> b findMin :: TKey a => TSet a -> a findMax :: TKey a => TSet a -> a deleteMin :: TKey a => TSet a -> TSet a deleteMax :: TKey a => TSet a -> TSet a deleteFindMin :: TKey a => TSet a -> (a, TSet a) deleteFindMax :: TKey a => TSet a -> (a, TSet a) minView :: TKey a => TSet a -> Maybe (a, TSet a) maxView :: TKey a => TSet a -> Maybe (a, TSet a) elems :: TKey a => TSet a -> [a] toList :: TKey a => TSet a -> [a] fromList :: TKey a => [a] -> TSet a toAscList :: TKey a => TSet a -> [a] fromAscList :: TKey a => [a] -> TSet a 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)