Z      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXY <Dependent maps: f is a GADT-like thing with a facility for M rediscovering its type parameter, elements of which function as identifiers F tagged with the type of the thing they identify. Real GADTs are one  useful instantiation of f , as are Tags from Data.Dependent.Tag. Semantically,   f is equivalent to a set of  f where no two  elements have the same tag. More informally,   is to dependent products as M.Map is to (->). @ Thus it could also be thought of as a partial (in the sense of "partial  function") dependent product. Z[ A  ) is just a wrapper for the true key type f which hides / the associated value type and presents the key' s GADT-level   instance as a vanilla \. instance so it can be used in cases where we  don'#t care about the associated value. O(1). The empty map.  empty == fromList []  size empty == 0 O(1). A map with a single element. / singleton 1 'a' == fromList [(1, 'a')]  size (singleton 1 'a') == 1 O(1). Is the map empty? O(1)%. The number of elements in the map. O(log n)(. 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. _`abcdO(log n)'. 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 O(log n)'. Delete and find the maximal element. b deleteFindMax (fromList [(5,"a"), (3,"b"), (10,"c")]) == ((10,"c"), fromList [(3,"b"), (5,"a")]) t deleteFindMax empty Error: can not return the maximal element of an empty map efghijklmnopqr Z[ _`abcdefghijklmnopqr [ZZ[  _`abcdefghijklmnopqrYO(log n). Find the value at a key.  Calls s$ when the element can not be found. B fromList [(5,'a'), (3,'b')] ! 1 Error: element not in the map ( fromList [(5,'a'), (3,'b')] ! 5 == 'a' Same as 7. O(log n)+. Is the key a member of the map? See also . O(log n)/. Is the key not a member of the map? See also . tO(log n). Find the value at a key.  Calls s$ when the element can not be found.  Consider using # when elements may not be present. O(log n). The expression ( def k map) returns  the value at key k or returns default value def ! when the key is not in the map. O(log n)). 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   u. O(log n)=. Insert with a function, combining new value and old value.   f key value mp  will insert the entry  key :=> value into mp if key does @ not exist in the map. If the key does exist, the function will  insert the entry key :=> f new_value old_value. Same as 2, but the combining function is applied strictly. , This is often the most desirable behavior. O(log n)B. Insert with a function, combining key, new value and old value.   f key value mp  will insert the entry  key :=> value into mp if key does @ not exist in the map. If the key does exist, the function will  insert the entry !key :=> f key new_value old_value. 9 Note that the key passed to f is the same key passed to . Same as 2, but the combining function is applied strictly. O(log n)6. Combines 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). O(log n). A strict version of . O(log n)?. 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. O(log n)M. Update a value at a specific key with the result of the provided function.  When the key is not 4 a member of the map, the original map is returned. !O(log n)8. Adjust a value at a specific key. When the key is not 4 a member of the map, the original map is returned. "O(log n). 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. #O(log n). 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. $O(log n). Lookup and update. See also #. 7 The function returns changed value, if it is updated. > Returns the original key value if the map entry is deleted. %O(log n). 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 Map.  In short :  k (% f k m) = f ( k m). &O(log n) . Return the index& of a key. The index is a number from  0 up to, but not including, the  of the map. Calls s when  the key is not a  of the map. 'O(log n) . Lookup the index& of a key. The index is a number from  0 up to, but not including, the  of the map. (O(log n). Retrieve an element by index. Calls s when an  invalid index is used. )O(log n). Update the element at index. Calls s when an  invalid index is used. *O(log n). Delete the element at index.  Defined as (* i map = ) (k x -> ^) i map). +O(log n)$. The minimal key of the map. Calls s is the map is empty. ,O(log n)$. The maximal key of the map. Calls s is the map is empty. -O(log n)D. Delete the minimal key. Returns an empty map if the map is empty. .O(log n)D. Delete the maximal key. Returns an empty map if the map is empty. /O(log n)'. Update the value at the minimal key. 0O(log n)'. Update the value at the maximal key. 1O(log n)>. Retrieves the minimal (key :=> value) entry of the map, and & the map stripped of that element, or ^ if passed an empty map. 2O(log n)>. Retrieves the maximal (key :=> value) entry of the map, and & the map stripped of that element, or ^ if passed an empty map. 3The union of a list of maps:  (3 == v 5  ). 49The union of a list of maps, with a combining operation:  (4 f == v (6 f)  ). 5O(n+m).  The expression (5 t1 t2!) takes the left-biased union of t1 and t2.  It prefers t1& when duplicate keys are encountered,  i.e. (5 ==  unionWith u). ' The implementation uses the efficient  hedge-union algorithm. * Hedge-union is more efficient on (bigset `5` smallset). w6O(n+m). H Union with a combining function. The implementation uses the efficient  hedge-union algorithm. * Hedge-union is more efficient on (bigset `5` smallset). x7O(n+m). 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. y8O(n+m)@. 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. z9O(n+m). Intersection of two maps. B Return data in the first map for the keys existing in both maps.  (9 m1 m2 == intersectionWith u m1 m2). :O(n+m)*. Intersection with a combining function. + Intersection is more efficient on (bigset `9` smallset). ;O(n+m).  This function is defined as (; = < {)). <O(n+m).  The expression (< f t1 t2 ) returns | if  all keys in t1 are in tree t2 , and when f returns | when . applied to their respective keys and values. }=O(n+m):. Is this a proper submap? (ie. a submap but not equal).  Defined as (= = > {). >O(n+m)9. Is this a proper submap? (ie. a submap but not equal).  The expression (> f m1 m2 ) returns | when  m1 and m2 are not equal,  all keys in m1 are in m2 , and when f returns | when / applied to their respective keys and values. ?O(n). Filter all keys/#values that satisfy the predicate. @O(n)8. Partition 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 U. AO(n) . Map keys/values and collect the ] results. BO(n) . Map keys/values and separate the ~ and  results. CO(n)-. Map a function over all values in the map. DO(n). The function D threads an accumulating 7 argument throught the map in ascending order of keys. EO(n). The function E threads an accumulating 7 argument through the map in descending order of keys. F O(n*log n).  F 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. GO(n).  G 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 f9 maps distinct original keys to distinct resulting keys. + This function has better performance than mapKeys. HO(n)1. Fold the keys and values in the map, such that  H f z ==  ( f) z . P. This is identical to I), and you should use that one instead of : this one. This name is kept for backward compatibility. IO(n)A. Post-order fold. The function will be applied from the lowest  value to the highest. JO(n)A. Pre-order fold. The function will be applied from the highest  value to the lowest. KO(n)1. Return all keys of the map in ascending order. - keys (fromList [(5,"a"), (3,"b")]) == [3,5]  keys empty == [] LO(n). Return all key//value pairs in the map in ascending key order. M O(n*log n) . Build a map from a list of key/value pairs. See also R. K If the list contains more than one value for the same key, the last value  for the key is retained. N O(n*log n) . Build a map from a list of key/0value pairs with a combining function. See also S. OO(n). Convert to a list of key/ value pairs. PO(n) . Convert to an ascending list. QO(n) . Convert to a descending list. RO(n)5. Build a map from an ascending list in linear time.  :The precondition (input list is ascending) is not checked. SO(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. TO(n)J. Build a map from an ascending list of distinct elements in linear time.   The precondition is not checked. UO(log n). The expression (U 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. VO(log n). The expression (V k map) splits a map just  like U but also returns  k map. O(log n). WO(n);. Show the tree that implements the map. The tree is shown & in a compressed, hanging format. See X. XO(n). The expression (X showelem hang wide map) shows @ the tree that implements the map. Elements are shown using the showElem function. If hang is  |, a hanging5 tree is shown otherwise a rotated tree is shown. If  wide is |", an extra wide version is shown. YO(n)/. Test if the internal map structure is valid. Exported only for Debug.QuickCheck Z  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ    !"#$%5634789:CDEFGHIJKLOMNPQRST?@ABUV;<=>'&()*+,-./012WXYG !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXY           !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefeghijklmnopqrstuvwxyz{|}~dependent-map-0.1.1Data.Dependent.MapData.Dependent.Map.InternalbaseGHC.Listfilterdependent-sum-0.2Data.Dependent.Sum:=>DSumData.GADT.CompareGLTGEQGGT GOrderinggcompareGCompareDMapKeyempty singletonnullsizelookup deleteFindMin deleteFindMax!\\member notMemberfindWithDefaultinsert insertWith insertWith' insertWithKeyinsertWithKey'insertLookupWithKeyinsertLookupWithKey'deleteadjust adjustWithKeyupdate updateWithKeyupdateLookupWithKeyalter findIndex lookupIndexelemAtupdateAtdeleteAtfindMinfindMax deleteMin deleteMaxupdateMinWithKeyupdateMaxWithKeyminViewWithKeymaxViewWithKeyunions unionsWithKeyunion unionWithKey differencedifferenceWithKey intersectionintersectionWithKey isSubmapOf isSubmapOfByisProperSubmapOfisProperSubmapOfBy filterWithKeypartitionWithKeymapMaybeWithKeymapEitherWithKey mapWithKeymapAccumLWithKeymapAccumRWithKey mapKeysWithmapKeysMonotonic foldWithKey foldrWithKey foldlWithKeykeysassocsfromListfromListWithKeytoList toAscList toDescList fromAscListfromAscListWithKeyfromDistinctAscListsplit splitLookupshowTree showTreeWithvalidBinTip GHC.ClassesOrd Data.MaybeJustNothing lookupAssocjoin insertMax insertMinmergegluedeltaratiobalancerotateLrotateRsingleLsingleRdoubleLdoubleRbintrim trimLookupLofilterGtfilterLtGHC.ErrerrorfindGHC.Baseconstfoldl hedgeUnionLhedgeUnionWithKey hedgeDiffhedgeDiffWithKeyeqTaggedghc-primGHC.BoolTruesubmap' Data.EitherLeftRightfoldr Data.TupleuncurrysplitLookupWithKey showsTree showsTreeHangshowWide showsBarsnodewithBar withEmptyorderedbalanced validsize foldlStrict