*      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~  The ReprF 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 ( a,  a), and  x, y :: a, then x  y  if and only if  x   y!. It is typically the case that   x y ==  ( x) ( y), as well, but this is not Z 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"  instances, ' allowing a type to be used in its own  definition when wrapped in a Key modifier.           Given a type with an associated : instance, generates a representation that will cause its TMap 0 implementation to be essentially equivalent to Data.Map.  KGiven the name of a type constructor, automatically generates an efficient  instance. L If you have several mutually dependent (or even mutually recursive) types,   will ( construct instances for all of them.  R guarantees that any instances it generates are consistent with the ordering that  would be generated by  deriving ()' in the data declaration. That is, if    generates an instance Repr a , then it is guaranteed that if  x, y :: a, and a  has a derived  instance, then *compare x y == compare (toRep x) (toRep y). KGiven the name of a type constructor, automatically generates an efficient  instance. L If you have several mutually dependent (or even mutually recursive) types,  will A construct instances for all of them. The instance generated by  may, in some 9 cases, be more efficient than the instance generated by   -- in particular, ^ arguments common to several constructors may be factored out, reducing the complexity of the  associated TrieKey5 instance, but leaving an ordering inconsistent with .  Therefore, D guarantees that any instances it generates are consistent with the % ordering that would be generated by  deriving ()' in the data declaration. That is, if   generates an instance Repr a , then it is guaranteed that if  x, y :: a, and  a has a derived  instance, then  (x == y) == (toRep x == toRep y).       DWe embed IntN into WordN, but we have to be careful about overflow.            !"#$%  !"#$%  !"!"#$%@A  TrieKey k instance implies that k. is a standardized representation for which a , generalized trie structure can be derived. &'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abc@&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abc@'()*+,-./0123456789:&;<=>?@AB&'()*+,-./0123456789:;<=>?@ABCFEDDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abc(defghijklmnopqrstuvwxyz{|}~  a is based on  Data.IntMap. / ( k) a is based on Data.Map.  () a is implemented as  a.  (k1, k2) a is implemented as a  k1 ( k2 a).  ( k1 k2) a is essentially a (TrieMap k1 a, TrieMap k2 a), but = specialized for the cases where one or both maps are empty.  ( k) a is a wrapper around a  k a, that reverses the order of the operations. ### ( Word) a: is a traditional radix trie specialized for word arrays.  ( k) a is a traditional radix trie.  k is a handy alias for ( k,  ( k))!. To make a type an instance of ,  use the methods available in Data.TrieMap.Representation.TH to generate a  instance that will  satisfy  ( k).   (  k) a is a wrapper around a TrieMap (Rep k) a.  bA  represents a  with a "hole" at a particular key position. hs are used for element-wise operations on maps (insertion, deletion and update) in a two-stage process:  A = (and the value at that position, if any) is obtained from a  by searching or indexing.  2. A new  is made from a * by either filling the hole with a value (n) or erasing it (o). O(1). The empty map. O(1). A map with a single element. O(1). Is the map empty? &Lookup the value at a key in the map. 4The function will return the corresponding value as ( value), or  if the key isn't in the map. The expression ( def k map) returns the value at key k or returns default value def ! when the key is not in the map. Find the value at a key. Calls $ when the element can not be found. The expression ( f k map) alters the value x at k, or absence thereof.  7 can be used to insert, delete, or update a value in a  . In short:   k ( f k m) = f ( k m). 'Insert a new key and value in the map. C If the key is already present in the map, the associated value is # replaced with the supplied value.  is equivalent to    . M insert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'x')] W insert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3, 'b'), (5, 'a'), (7, 'x')] ? insert 5 'x' empty == singleton 5 'x' ;Insert with a function, combining new value and old value.    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")] d insertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")] L insertWith (++) 5 "xxx" empty == singleton 5 "xxx" !@Insert with a function, combining key, new value and old value.  ! 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). 9 Note that the key passed to f is the same key passed to !. T 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")] d insertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")] L insertWithKey f 5 "xxx" empty == singleton 5 "xxx" "4Combines insert operation with old value retrieval.  The expression (" f k x map) 0 is a pair where the first element is equal to ( k map) " and the second element equal to (! f k x map). T let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value p insertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")]) v 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") #=Delete a key and its value from the map. When the key is not 4 a member of the map, the original map is returned. ; delete 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" I delete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] 1 delete 5 empty == empty $KUpdate a value at a specific key with the result of the provided function. H When the key is not a member of the map, the original map is returned. Y adjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")] U adjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] = adjust ("new " ++) 7 empty == empty %6Adjust a value at a specific key. When the key is not 4 a member of the map, the original map is returned. * let f key x = (show key) ++ ":new " ++ x X adjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")] R adjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] : adjustWithKey f 7 empty == empty &The expression (& f k map) updates the value x  at k (if it is in the map). If (f x) is , the element is  deleted. If it is ( y ), the key k is bound to the new value y. 6 let f x = if x == "a" then Just "new a" else Nothing O update f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")] K update f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] = update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" 'The expression (' f k map) updates the  value x at k (if it is in the map). If (f k x) is , # the element is deleted. If it is ( y ), the key k is bound  to the new value y. G let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing X updateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")] R updateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")] D updateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" (?Post-order fold. The function will be applied from the lowest  value to the highest. )?Pre-order fold. The function will be applied from the highest  value to the lowest. * Map each key/_element pair to an action, evaluate these actions from left to right, and collect the results. ++Map a function over all values in the map. O map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")] ,+Map a function over all values in the map. & let f key x = (show key) ++ ":" ++ x Q mapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")] -- 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 F keys to the same new key. In this case the value at the smallest of  these keys is retained. e mapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")] W mapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "c" W mapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "c" .. 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 G keys to the same new key. In this case the associated values will be  combined using c. c mapKeysWith (++) (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 1 "cdab" c mapKeysWith (++) (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")]) == singleton 3 "cdab" // f s == - 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 f9 maps distinct original keys to distinct resulting keys. + This function has better performance than -. a mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")] 0The expression (0 t1 t2!) takes the left-biased union of t1 and t2.  It prefers t1& when duplicate keys are encountered,  i.e. (0 == 1 ). ' The implementation uses the efficient  hedge-union algorithm. * Hedge-union is more efficient on (bigset `0` smallset). r union (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")] 1O(n+m)I. 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")] 23GUnion with a combining function. The implementation uses the efficient  hedge-union algorithm. 4GUnion with a combining function. The implementation uses the efficient  hedge-union algorithm. * Hedge-union is more efficient on (bigset `0` smallset). a 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")] 55 is equivalent to 3 ( _ _ -> Nothing). 6Intersection of two maps. B Return data in the first map for the keys existing in both maps.  (6 m1 m2 == 7  m1 m2). a intersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "a" 7(Intersection with a combining function. k intersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "aA" 8(Intersection with a combining function. + Intersection is more efficient on (bigset `6` smallset). 4 let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar n intersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == singleton 5 "5:a|A" 99 f m1 m2 is equivalent to  R  (7 f m1 m2). :: f m1 m2 is equivalent to  R  (8 f m1 m2). ;Difference of two maps. B 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" <Same as ;. ='Difference with a combining function.  When two equal keys are M encountered, the combining function is applied to the values of these keys.  If it returns 7, the element is discarded (proper set difference). If  it returns ( y+), the element is updated with a new value y. & The implementation uses an efficient hedge algorithm comparable with  hedge-union. E 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" >>Difference with a combining function. When two equal keys are L encountered, the combining function is applied to the key and both values.  If it returns 7, the element is discarded (proper set difference). If  it returns ( y+), the element is updated with a new value y. & The implementation uses an efficient hedge algorithm comparable with  hedge-union. Z 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" ?7Retrieves the value associated with minimal key of the / map, and the map stripped of that element, or  if passed an  empty map. F minView (fromList [(5,"a"), (3,"b")]) == Just ("b", singleton 5 "a")  minView empty == Nothing @7Retrieves the value associated with maximal key of the / map, and the map stripped of that element, or  if passed an F maxView (fromList [(5,"a"), (3,"b")]) == Just ("a", singleton 3 "b")  maxView empty == Nothing A"The minimal key of the map. Calls  if the map is empty. 2 findMin (fromList [(5,"a"), (3,"b")]) == (3,"b") R findMin empty Error: empty map has no minimal element B"The maximal key of the map. Calls  if the map is empty. 2 findMax (fromList [(5,"a"), (3,"b")]) == (5,"a") R findMax empty Error: empty map has no maximal element CBDelete the minimal key. Returns an empty map if the map is empty. Q deleteMin (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(5,"a"), (7,"c")]  deleteMin empty == empty DBDelete the maximal key. Returns an empty map if the map is empty. Q deleteMax (fromList [(5,"a"), (3,"b"), (7,"c")]) == fromList [(3,"b"), (5,"a")]  deleteMax empty == empty E%Update the value at the minimal key. d updateMin (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "Xb"), (5, "a")] U updateMin (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" F%Update the value at the maximal key. d updateMax (\ a -> Just ("X" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "Xa")] U updateMax (\ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" G%Update the value at the minimal key. x updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"3:b"), (5,"a")] j updateMinWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" H%Update the value at the maximal key. x updateMaxWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList [(5,"a"), (3,"b")]) == fromList [(3,"b"), (5,"5:a")] j updateMaxWithKey (\ _ _ -> Nothing) (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" I%Delete and find the minimal element. b deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) t deleteFindMin Error: can not return the minimal element of an empty map J%Delete and find the minimal element. b deleteFindMin (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((3,"b"), fromList[(5,"a"), (10,"c")]) t deleteFindMin Error: can not return the minimal element of an empty map K7Retrieves the minimal (key,value) pair of the map, and & the map stripped of that element, or  if passed an empty map. Q minViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((3,"b"), singleton 5 "a") ! minViewWithKey empty == Nothing LO(log n)9. Retrieves the maximal (key,value) pair of the map, and & the map stripped of that element, or  if passed an empty map. Q maxViewWithKey (fromList [(5,"a"), (3,"b")]) == Just ((5,"a"), singleton 3 "b") ! maxViewWithKey empty == Nothing MEReturn all elements of the map in the ascending order of their keys. 2 elems (fromList [(5,"a"), (3,"b")]) == ["b","a"]  elems empty == [] N/Return all keys of the map in ascending order. - keys (fromList [(5,"a"), (3,"b")]) == [3,5]  keys empty == [] OReturn all key//value pairs in the map in ascending key order. < assocs (fromList [(5,"a"), (3,"b")]) == [(3,"b"), (5,"a")]  assocs empty == [] PMap values and separate the  and   results. / let f a = if a < "c" then Left a else Right a = mapEither f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) C == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")])  L mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) ? == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) QMap keys/values and separate the  and   results. < let f k a = if k < 5 then Left (k * 2) else Right (a ++ a) D mapEitherWithKey f (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) A == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")])  T mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]) ? == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")]) RO(n). Map values and collect the  results. 6 let f x = if x == "a" then Just "new a" else Nothing A mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a" SMap keys/values and collect the  results. D let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing J mapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3" T6Partition the map according to a predicate. The first F map contains all elements that satisfy the predicate, the second all , elements that fail the predicate. See also X. W 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")]) U6Partition the map according to a predicate. The first F map contains all elements that satisfy the predicate, the second all , elements that fail the predicate. See also X. W 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")]) V.Filter all values that satisfy the predicate. A filter (> "a") (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" 7 filter (> "x") (fromList [(5,"a"), (3,"b")]) == empty 7 filter (< "a") (fromList [(5,"a"), (3,"b")]) == empty WFilter all keys/#values that satisfy the predicate. P filterWithKey (\k _ -> k > 4) (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" XThe expression (X 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. O split 2 (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3,"b"), (5,"a")]) C split 3 (fromList [(5,"a"), (3,"b")]) == (empty, singleton 5 "a") M split 4 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", singleton 5 "a") C split 5 (fromList [(5,"a"), (3,"b")]) == (singleton 3 "b", empty) O split 6 (fromList [(5,"a"), (3,"b")]) == (fromList [(3,"b"), (5,"a")], empty) YThe expression (Y k map) splits a map just  like X but also returns  k map. ^ splitLookup 2 (fromList [(5,"a"), (3,"b")]) == (empty, Nothing, fromList [(3,"b"), (5,"a")]) S 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") S 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) ZThis function is defined as (Z = [ (==)). [The expression ([ f t1 t2 ) returns   if  all keys in t1 are in tree t2 , and when f returns   when A applied to their respective values. For example, the following  expressions are all  :  E isSubmapOfBy (==) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) E isSubmapOfBy (<=) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) M isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1),('b',2)]) But the following are all  : E isSubmapOfBy (==) (fromList [('a',2)]) (fromList [('a',1),('b',2)]) E isSubmapOfBy (<) (fromList [('a',1)]) (fromList [('a',1),('b',2)]) E isSubmapOfBy (==) (fromList [('a',1),('b',2)]) (fromList [('a',1)]) \Build a map from a list of key/value pairs. See also ]. K If the list contains more than one value for the same key, the last value  for the key is retained.  fromList [] == empty F fromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")] F fromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")] ]3Build a map from an ascending list in linear time.  :The precondition (input list is ascending) is not checked. J fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] J fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")] ^Build a map from a list of key/0value pairs with a combining function. See also _. e fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]  fromListWith (++) [] == empty _\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. T fromAscListWith (++) [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "ba")] `Build a map from a list of key/0value pairs with a combining function. See also _. e fromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]  fromListWith (++) [] == empty a3Build a map from an ascending list in linear time.  :The precondition (input list is ascending) is not checked. J fromAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] J fromAscList [(3,"b"), (5,"a"), (5,"b")] == fromList [(3, "b"), (5, "b")] bHBuild a map from an ascending list of distinct elements in linear time.   The precondition is not checked. I fromDistinctAscList [(3,"b"), (5,"a")] == fromList [(3, "b"), (5, "a")] cO(1)%. The number of elements in the map. 3 size empty == 0 3 size (singleton 1 'a') == 1 3 size (fromList([(1,'a'), (2,'c'), (3,'b')])) == 3 d)Is the key a member of the map? See also e. 0 member 5 (fromList [(5,'a'), (3,'b')]) == True 1 member 1 (fromList [(5,'a'), (3,'b')]) == False e-Is the key not a member of the map? See also d. 4 notMember 5 (fromList [(5,'a'), (3,'b')]) == False 3 notMember 1 (fromList [(5,'a'), (3,'b')]) == True f The set of all keys of the map. F keysSet (fromList [(5,"a"), (3,"b")]) == Data.TrieSet.fromList [3,5] % keysSet empty == Data.TrieSet.empty gO(1)'. The key marking the position of the "hole" in the map. hh loc# is the submap with keys less than g loc. ii loc& is the submap with keys greater than g loc. j0Search the map for the given key, returning the F corresponding value (if any) and an updatable location for that key.  Properties:    case j k m of  (Nothing, loc) -> g loc == k && o loc == m  (Just v, loc) -> g loc == k && n v loc == m   k m ==   (j k m)k3Return the value and an updatable location for the  ith key in the map. Calls  if i is out of range.  Properties:    0 <= i && i < c m ==>  let (v, loc) = k i m in  c (h loc) == i && n v loc == m  r i m == let (v, loc) = k i m in (g loc, v) lO(log n)5. Return the value and an updatable location for the  least key in the map, or  if the map is empty.  Properties:    c m > 0 ==>  let Just (v, loc) = l i m in  c (h loc) == 0 && n v loc == m  A m == let Just (v, loc) = l i m in (g loc, v)m3Return the value and an updatable location for the  greatest key in the map, or  if the map is empty.  Properties:    c m > 0 ==>  let Just (v, loc) = m i m in  c (i loc) == 0 && n v loc == m  B m == let Just (v, loc) = m i m in (g loc, v)n1Return a map obtained by placing the given value 8 at the location (replacing an existing value, if any). n v loc == h loc 0  (g loc) v 0 i loco/Return a map obtained by erasing the location. o loc == h loc 0 i locp Return the index& of a key. The index is a number from  0 up to, but not including, the c of the map. Calls  when  the key is not a d of the map. O findIndex 2 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map 0 findIndex 3 (fromList [(5,"a"), (3,"b")]) == 0 0 findIndex 5 (fromList [(5,"a"), (3,"b")]) == 1 O findIndex 6 (fromList [(5,"a"), (3,"b")]) Error: element is not in the map q Lookup the index& of a key. The index is a number from  0 up to, but not including, the c of the map. 8 lookupIndex 2 (fromList [(5,"a"), (3,"b")]) == Nothing 7 lookupIndex 3 (fromList [(5,"a"), (3,"b")]) == Just 0 7 lookupIndex 5 (fromList [(5,"a"), (3,"b")]) == Just 1 8 lookupIndex 6 (fromList [(5,"a"), (3,"b")]) == Nothing rRetrieve an element by index. Calls  when an  invalid index is used. 3 elemAt 0 (fromList [(5,"a"), (3,"b")]) == (3,"b") 4 elemAt 1 (fromList [(5,"a"), (3,"b")]) == (5, "a") E elemAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range sUpdate the element at index. Calls  when an  invalid index is used. b updateAt (\ _ _ -> Just "x") 0 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "x"), (5, "a")] b 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 T updateAt (\_ _ -> Nothing) 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" T 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 tDelete the element at index.  Defined as (t i map = s (k x -> ) i map). > deleteAt 0 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a" > deleteAt 1 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b" H deleteAt 2 (fromList [(5,"a"), (3,"b")]) Error: index out of range H deleteAt (-1) (fromList [(5,"a"), (3,"b")]) Error: index out of range ` !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrst`ghijklmno<cde !"#$%&'012345;=>6789:+,-./*()MNfO\^`]_abVWTURSPQXYZ[qprstABCDIJEFGH?@KL^ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrst&uvwxyz{|}~'uvwxyz{|}~'uxvwyz|{}~&uvwxyz{|}~ ! " #$%&'(()** + , -./011223456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~5<@6MRXSsquH^_`afg\]jyz7Y       !     %              !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^*_`abcdefg86hiIomNTZxjklmnopqrstuvwx`abchy86izomv{z|}~sfgtMc`y TrieMap-2.0.3Data.TrieMap.RepresentationData.TrieMap.ModifiersData.TrieMap.Class Data.TrieMap Data.TrieSetData.TrieMap.RadixTrie.Slice$Data.TrieMap.Representation.TH.UtilsData.TrieMap.Utils!Data.TrieMap.Representation.Class(Data.TrieMap.Representation.TH.ReprMonad-Data.TrieMap.Representation.TH.Representation)Data.TrieMap.Representation.TH.FactorizedData.TrieMap.Representation.TH*Data.TrieMap.Representation.Instances.Prim+Data.TrieMap.Representation.Instances.Basic-Data.TrieMap.Representation.Instances.Foreign-Data.TrieMap.Representation.Instances.Vectors0Data.TrieMap.Representation.Instances.ByteStringData.TrieMap.Sized%Data.TrieMap.Representation.InstancesData.TrieMap.ApplicativeData.TrieMap.TrieKeyData.TrieMap.IntMapData.TrieMap.OrdMapData.TrieMap.UnitMapData.TrieMap.ProdMapData.TrieMap.UnionMapData.TrieMap.ReverseMapData.TrieMap.RadixTrie.EdgeData.TrieMap.RadixTrieData.TrieMap.KeyData.TrieMap.Class.InstancesReprReptoRepunOrdOrdOrderedgetRevRevgetKeyKey genOrdReprgenRepr genOptReprTrieKeyTrieMapTKeyTSetTMapgetTMap TLocationempty singletonnulllookupfindWithDefault!alterinsert insertWith insertWithKeyinsertLookupWithKeydeleteadjust adjustWithKeyupdate updateWithKey foldrWithKey foldlWithKeytraverseWithKeymap mapWithKeymapKeys mapKeysWithmapKeysMonotonicunion unionWith unionWithKeyunionMaybeWithunionMaybeWithKeysymmetricDifference intersectionintersectionWithintersectionWithKeyintersectionMaybeWithintersectionMaybeWithKey difference\\differenceWithdifferenceWithKeyminViewmaxViewfindMinfindMax deleteMin deleteMax updateMin updateMaxupdateMinWithKeyupdateMaxWithKey deleteFindMin deleteFindMaxminViewWithKeymaxViewWithKeyelemskeysassocs mapEithermapEitherWithKeymapMaybemapMaybeWithKey partitionpartitionWithKeyfilter filterWithKeysplit splitLookup isSubmapOf isSubmapOfByfromList fromAscList fromListWithfromAscListWithfromListWithKeyfromAscListWithKeyfromDistinctAscListsizemember notMemberkeysSetkeybeforeaftersearchindex minLocation maxLocationassignclear findIndex lookupIndexelemAtupdateAtdeleteAt splitMember mapMonotonicfoldfoldrfoldltoList toAscList isSubsetOfisProperSubsetOfSlicesliceSrc_sliceIxlen splitSlice takeSlice dropSlice unDropSlices2Vv2S matchSliceV matchSlice iMatchSlice!$AlgCon decompose decompose'compose tyVarBndrVar tyVarBndrTypetyProdtySumfstExpsndExpleftNrightNleftExprightExpfstTysndTyisEnumTyalgCon substInAlgCon substInPred mergeWith toVectorN toVectorFbase GHC.ClassesEq==compare ReprMonad runReprMonad Instances liftQuasiinsNubrecurseoutputInstance getInstance mustBreak execReprMonadCaseinputoutputRepresentationreprTypecasesunitRepr vectorizeReprfstReprsndReprprodCase unifyProdCase mapCaseInput mapCaseOutputprodReprsumRepr unifySumRepr unifyProdRepr mapReprInputconify mapReprOutput checkEnumReprordRepr caseToClause outputRepr recursiveReprkeyReprFactored factorType fRestTypefCases FactorCaseFCasefInputfFactorfOutput factorRepr otherRepr factorCase otherCase caseFactor combFCase combFactorfactorsdistinctFactors factorWith factorOutunifydistributeManygetDataForNamegetDataForType mustBreakTy recurseTy genReprMainconReprtypeRepr bootstrapRepri2wOverhangquoPowremPow unsafeToPtr unsafeFromPtrElemAssocgetKgetValueSizedgetSize#getSizeunboxunrollDualrunDualDualPlus runDualPlus.:<.><.:>Hole=?cmpemptyM singletonM getSimpleMsizeMlookupMfmapM traverseMfoldrMfoldlM mapMaybeM mapEitherMunionMisectMdiffM isSubmapM fromListM fromAscListMfromDistAscListM singleHoleMbeforeMafterMsearchMindexM extractHoleMassignMunifyMSimple NonSimple SingletonNullUnifiedLEqonSndonThird singletonM' mapMaybeM' mapEitherM' mapEitherM''unionM'isectM'diffM'beforeM'afterM'searchM' extractHoleM'assignM'alterMnullM guardNullMsidesbothelemsM insertWithMmapEitherMaybe unionMaybe isectMaybe diffMaybesubMaybe indexFailNatPrefixMaskSizeRootLeftBinRightBinPath branchHole natFromInt intFromNatshiftRLsingletonMaybetraversemaskzeronomatchmatchzeroNmaskWshorter branchMaskhighestBitMaskjoinbin $fTrieKeyWordGHC.WordWordOrdMaprebuildfmapisSubmap hedgeUnionfilterGtfilterLttrim trimLookupLoisect hedgeDiff joinMaybe insertMax insertMinmergegluesize#balancerotateLrotateRsingleLsingleRdoubleLdoubleR$fTrieKeyOrdered $fTrieKey() Data.MaybeMaybeUnitgetUnitbreakFst $fTrieKey(,)UViewHole1Hole2HView&^ singletonL singletonRuViewhViewhole1hole2onPair partEithers$fTrieKeyEither Data.EitherEitherrevIndex $fTrieKeyRevMEdgeDeepEdgeLocLocEdgeBranch singleLoc singletonEdge getSimpleEdgeedgecompactdropEdge unDropEdge lookupEdge searchEdgemapEdge mapMaybeEdge mapEitherEdge traverseEdge foldrEdge foldlEdge fillHoleEdge unionEdge isectEdgediffEdge isSubEdge beforeEdge afterEdgeextractEdgeLoc indexEdge unifyEdgeWordVecvZipWith$fTrieKeyVectorvector-0.7.0.1Data.Vector.StorableVector$fTrieKeyVector0 Data.Vector $fTrieKeyKeyTLocJustNothingGHC.ErrerrorGHC.Baseconstid updateHelperLeftRightghc-primGHC.BoolTrueFalse Data.TuplefstextractfillHole