iȕ      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~None &'-3DFGJT]m6 "A map from partially-ordered keys k to values v.Allows us to abstract over value-strictness in a zero-cost manner. GHC should always be able to specialise the two instances of this and consequently inline .NIt's a little sad we can't just use regular singletons, for reasons outlined  Shttps://stackoverflow.com/questions/45734362/specialization-of-singleton-parametershere.4Should be inlined and specialised at all call sites.Internal smart constructor so that we can be sure that we are always spine-strict, discard empty maps and have appropriate size information.\mathcal{O}(1)%. The number of elements in this map.\mathcal{O}(w) . The width w of the chain decomposition in the internal data structure. This is always at least as big as the size of the biggest possible anti-chain.\mathcal{O}(w\log n)". Is the key a member of the map?\mathcal{O}(w\log n),. Is the key a member of the map? See also ..member 5 (fromList [(5,'a'), (3,'b')]) == TrueTrue/member 1 (fromList [(5,'a'), (3,'b')]) == FalseTrue\mathcal{O}(w\log n)0. Is the key not a member of the map? See also .2notMember 5 (fromList [(5,'a'), (3,'b')]) == FalseTrue1notMember 1 (fromList [(5,'a'), (3,'b')]) == TrueTrue\mathcal{O}(w\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.:findWithDefault 'x' 1 (fromList [(5,'a'), (3,'b')]) == 'x'True:findWithDefault 'x' 5 (fromList [(5,'a'), (3,'b')]) == 'a'True"\mathcal{O}(w\log n)t. Find the largest set of keys smaller than the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.)lookupLT 3 (fromList [(3,'a'), (5,'b')])[](lookupLT 9 (fromList [(3,'a'), (5,'b')]) [(3,'a')]#\mathcal{O}(w\log n)s. Find the largest key smaller or equal to the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.(lookupLE 2 (fromList [(3,'a'), (5,'b')])[](lookupLE 3 (fromList [(3,'a'), (5,'b')]) [(3,'a')])lookupLE 10 (fromList [(3,'a'), (5,'b')]) [(5,'b')]$\mathcal{O}(w\log n)t. Find the smallest key greater or equal to the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.(lookupGE 3 (fromList [(3,'a'), (5,'b')]) [(3,'a')])lookupGE 5 (fromList [(3,'a'), (10,'b')]) [(10,'b')](lookupGE 6 (fromList [(3,'a'), (5,'b')])[]%\mathcal{O}(w\log n)m. Find the smallest key greater than the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.)lookupGT 5 (fromList [(3,'a'), (10,'b')]) [(10,'b')](lookupGT 5 (fromList [(3,'a'), (5,'b')])[]&\mathcal{O}(1). The empty map.empty fromList [] size empty0.\mathcal{O}(w\log n)s. 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")])fromList [(3,"b")]Gdelete 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]Truedelete 5 empty fromList []/\mathcal{O}(w\log n). Simultaneous . and .=\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2). The expression (= t1 t2!) takes the left-biased union of t1 and t2. It prefers t1- when duplicate keys are encountered, i.e. (= == > ).punion (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "a"), (7, "C")]True>\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)#. Union with a combining function.zunionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")]) == fromList [(3, "b"), (5, "aA"), (7, "C")]True?\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)#. Union with a combining function.Xlet 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")]True@\mathcal{O}(wn\log n), where  n=\max_i n_i and  w=\max_i w_i$. The union of a list of maps: (@ ==  = &).:{n unions [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]/ == fromList [(3, "b"), (5, "a"), (7, "C")]:}True:{m unions [(fromList [(5, "A3"), (3, "B3")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "a"), (3, "b")])]1 == fromList [(3, "B3"), (5, "A3"), (7, "C")]:}TrueA\mathcal{O}(wn\log n), where  n=\max_i n_i and  w=\max_i w_i@. The union of a list of maps, with a combining operation: (A f ==  (> f) &).:{v unionsWith (++) [(fromList [(5, "a"), (3, "b")]), (fromList [(5, "A"), (7, "C")]), (fromList [(5, "A3"), (3, "B3")])]4 == fromList [(3, "bB3"), (5, "aAA3"), (7, "C")]:}TrueB\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)\. Difference of two maps. Return elements of the first map not existing in the second map.Jdifference (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])fromList [(3,"b")]C\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2). 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 D, the element is discarded (proper set difference). If it returns ( y+), the element is updated with a new value y.Clet f al ar = if al == "b" then Just (al ++ ":" ++ ar) else NothingZdifferenceWith f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (3, "B"), (7, "C")])fromList [(3,"b:B")]D\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2). 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 D, the element is discarded (proper set difference). If it returns ( y+), the element is updated with a new value y.Xlet 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")])fromList [(3,"3:b|B")]E\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)a. Intersection of two maps. Return data in the first map for the keys existing in both maps. (E m1 m2 == F  m1 m2).Lintersection (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])fromList [(5,"a")]F\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)*. Intersection with a combining function.UintersectionWith (++) (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])fromList [(5,"aA")]G\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)*. Intersection with a combining function.2let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ arUintersectionWithKey f (fromList [(5, "a"), (3, "b")]) (fromList [(5, "A"), (7, "C")])fromList [(5,"5:a|A")]M\mathcal{O}(wn\log n). M 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 greatest of the original keys is retained.LmapKeys (+ 1) (fromList [(5,"a"), (3,"b")]) == fromList [(4, "b"), (6, "a")]TrueBmapKeys (\ _ -> 1) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])fromList [(1,"c")]BmapKeys (\ _ -> 3) (fromList [(1,"b"), (2,"a"), (3,"d"), (4,"c")])fromList [(3,"c")]O\mathcal{O}(n). O f s == M f s, but works only when f2 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, for every chain ls in s we have: hand [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f sThis means that fd maps distinct original keys to distinct resulting keys. This function has better performance than M._mapKeysMonotonic (\ k -> k * 2) (fromList [(5,"a"), (3,"b")]) == fromList [(6, "b"), (10, "a")]TrueP\mathcal{O}(n). A strict version of . Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.Q\mathcal{O}(n)f. Fold the keys and values in the map using the given right-associative binary operator, such that Q f z ==  ( f) z .  toAscList. For example,0keys map = foldrWithKey (\k x ks -> k:ks) [] map?let f k a result = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"IfoldrWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (5:a)(3:b)"TrueR\mathcal{O}(n). A strict version of Q. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.S\mathcal{O}(n). A strict version of . Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.T\mathcal{O}(n)e. Fold the keys and values in the map using the given left-associative binary operator, such that T f z ==  (\z' (kx, x) -> f z' kx x) z .  toAscList.2keys = reverse . foldlWithKey (\ks k x -> k:ks) []?let f result k a = result ++ "(" ++ (show k) ++ ":" ++ a ++ ")"IfoldlWithKey f "Map: " (fromList [(5,"a"), (3,"b")]) == "Map: (3:b)(5:a)"TrueU\mathcal{O}(n). A strict version of T. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.V\mathcal{O}(n)H. Fold the keys and values in the map using the given monoid, such that V f =  . I fW\mathcal{O}(n)7. Return all elements of the map in unspecified order.#elems (fromList [(5,"a"), (3,"b")]) ["b","a"] elems empty[]X\mathcal{O}(n)3. Return all keys of the map in unspecified order."keys (fromList [(5,"a"), (3,"b")])[3,5] keys empty[]Y\mathcal{O}(n)?. Return all key/value pairs in the map in unspecified order.$assocs (fromList [(5,"a"), (3,"b")])[(3,"b"),(5,"a")] assocs empty[]Z\mathcal{O}(n)?. Return all key/value pairs in the map in unspecified order. Currently,  toList = Y.[6Intentionally named this way, to disambiguate it from fromList.. This is so that we can doctest this module.^\mathcal{O}(n)0. Filter all values that satisfy the predicate.,filter (> "a") (fromList [(5,"a"), (3,"b")])fromList [(3,"b")],filter (> "x") (fromList [(5,"a"), (3,"b")]) fromList [],filter (< "a") (fromList [(5,"a"), (3,"b")]) fromList []_\mathcal{O}(n)5. Filter all keys/values that satisfy the predicate.AfilterWithKey (\(Div k) _ -> k > 4) (fromList [(5,"a"), (3,"b")])fromList [(5,"a")]`\mathcal{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. See also split.]partition (> "a") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b")], fromList [(5, "a")])TrueYpartition (< "x") (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)TrueYpartition (> "x") (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])Truea\mathcal{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. See also split.spartitionWithKey (\ (Div k) _ -> k > 3) (fromList [(5,"a"), (3,"b")]) == (fromList [(5, "a")], fromList [(3, "b")])TrueopartitionWithKey (\ (Div k) _ -> k < 7) (fromList [(5,"a"), (3,"b")]) == (fromList [(3, "b"), (5, "a")], empty)TrueopartitionWithKey (\ (Div k) _ -> k > 7) (fromList [(5,"a"), (3,"b")]) == (empty, fromList [(3, "b"), (5, "a")])Trueg!\mathcal{O}(n_2 w_1 n_1 \log n_1) . This function is defined as (g = h (==)).h!\mathcal{O}(n_2 w_1 n_1 \log n_1). The expression (h f t1 t2 ) returns  if all keys in t1 are in tree t2 , and when f returns [ when applied to their respective values. For example, the following expressions are all :CisSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])TrueCisSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'b'),(2,'c')])TrueKisSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])TrueBut the following are all :CisSubmapOfBy (==) (fromList [(2,'a')]) (fromList [(1,'a'),(2,'b')])FalseCisSubmapOfBy (<) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])FalseCisSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])Falsei!\mathcal{O}(n_2 w_1 n_1 \log n_1)G. Is this a proper submap? (ie. a submap but not equal). Defined as (i = j (==)).j!\mathcal{O}(n_2 w_1 n_1 \log n_1)K. Is this a proper submap? (ie. a submap but not equal). The expression (j 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 values. For example, the following expressions are all :IisProperSubmapOfBy (==) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])TrueIisProperSubmapOfBy (<=) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])TrueBut the following are all :QisProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a'),(2,'b')])FalseIisProperSubmapOfBy (==) (fromList [(1,'a'),(2,'b')]) (fromList [(1,'a')])FalseQisProperSubmapOfBy (<) (fromList [(1,'a')]) (fromList [(1,'a'),(2,'b')])Falsek\mathcal{O}(w\log n). The minimal keys of the map.,Note that the following examples assume the  Divisibility# partial order defined at the top.'lookupMin (fromList [(6,"a"), (3,"b")]) [(3,"b")]lookupMin empty[]l\mathcal{O}(w\log n). The maximal keys of the map.,Note that the following examples assume the  Divisibility# partial order defined at the top.'lookupMax (fromList [(6,"a"), (3,"b")]) [(6,"a")]lookupMax empty[]t\mathcal{O}(wn\log n), where !w=\max(w_1,w_2)), n=\max(n_1,n_2).u\mathcal{O}(wn\log n), where !w=\max(w_1,w_2)), n=\max(n_1,n_2).j   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklvnm wvutsrqpo  !"#$%&'()*+,x-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijkl (c) Sebastian Graf 2017 MIT sgraf1337@gmail.com  portable None-D\mathcal{O}(1). A map with a single element.singleton 1 'a'fromList [(1,'a')]size (singleton 1 'a')1\mathcal{O}(w\log n). 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.  is equivalent to  .Iinsert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'x')]TrueRinsert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'a'), (7,'x')]True=insert 5 'x' empty == singleton 5 'x'True\mathcal{O}(w\log n)>. 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).YinsertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]TruebinsertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]TrueJinsertWith (++) 5 "xxx" empty == singleton 5 "xxx"True\mathcal{O}(w\log n)C. 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);. Note that the key passed to f is the same key passed to .Rlet 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")]TruebinsertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]TrueJinsertWithKey f 5 "xxx" empty == singleton 5 "xxx"True\mathcal{O}(w\log n)G. Combines insert operation with old value retrieval. The expression ( f k x map2) is a pair where the first element is equal to ( k map$) and the second element equal to ( f k x map).Rlet f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_valueninsertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])TruetinsertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "xxx")])True\insertLookupWithKey f 5 "xxx" empty == (Nothing, singleton 5 "xxx")TrueThis is how to define  insertLookup using insertLookupWithKey:Blet insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t]insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])TrueginsertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "x")])True\mathcal{O}(w\log n). Adjust 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.Wadjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]TrueSadjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True;adjust ("new " ++) 7 empty == emptyTrue\mathcal{O}(w\log n). Adjust 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.(let f key x = (show key) ++ ":new " ++ xVadjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]TruePadjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True8adjustWithKey f 7 empty == emptyTrue\mathcal{O}(w\log n). Adjust a value at a specific key with the result of the provided function and simultaneously look up the old value at that key. When the key is not a member of the map, the original map is returned.Dlet f key old_value = show key ++ ":" ++ show 42 ++ "|" ++ old_valuegadjustLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:42|a")])TruebadjustLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a")])TrueJadjustLookupWithKey f 5 empty == (Nothing, empty)True\mathcal{O}(w\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.4let f x = if x == "a" then Just "new a" else NothingMupdate f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]TrueIupdate f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True;update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"True\mathcal{O}(w\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.Elet f k x = if x == "a" then Just ((show k) ++ ":new a") else NothingVupdateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]TruePupdateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]TrueBupdateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"True\mathcal{O}(w\log n). Lookup and update. See also . Warning: Contrary to  Data.Map.Lazy, the lookup does notG return the updated value, but the old value. This is consistent with  and also Data.IntMap.Lazy. .wRe-apply the updating function to the looked-up value once more to get the value in the map, like in the last example:Elet f k x = if x == "a" then Just ((show k) ++ ":new a") else NothinghupdateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])TruebupdateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a")])TrueTupdateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")TrueCfst (updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])) >>= f 5Just "5:new a"\mathcal{O}(w\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).let f _ = NothingHalter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True:alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"Truelet f _ = Just "c"Ralter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]TrueHalter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]True\mathcal{O}(w\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 ( k m).let f _ _ = NothingOalterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]TrueAalterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"True!let f k _ = Just (show k ++ ":c")[alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "7:c")]TrueQalterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:c")]True\mathcal{O}(w\log n)". Lookup and alteration. See also .Ilet f k x = if x == Nothing then Just ((show k) ++ ":new a") else NothingWalterLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b")])TrueqalterLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "7:new a")])TrueSalterLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")True\mathcal{O}(w\log n). The expression ( f k map) alters the value x at k, or absence thereof. @ can be used to inspect, insert, delete, or update a value in a Map . In short:  k <$>  f k m = f ( k m).Example: interactiveAlter :: Divibility -> DivMap String -> IO (DivMap String) interactiveAlter k m = alterF f k m where f Nothing -> do putStrLn $ show k ++ " was not found in the map. Would you like to add it?" getUserResponse1 :: IO (Maybe String) f (Just old) -> do putStrLn "The key is currently bound to " ++ show old ++ ". Would you like to change or delete it?" getUserresponse2 :: IO (Maybe String)  is the most general operation for working with an individual key that may or may not be in a given map. When used with trivial functors like Identity and ConstF, it is often slightly slower than more specialized combinators like  and q. However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.\mathcal{O}(wn\log n). Build a map from a list of key/value pairs. If the list contains more than one value for the same key, the last value for the key is retained.'fromList [] == (empty :: DivMap String)TrueDfromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]TrueDfromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]True\mathcal{O}(wn\log n)H. Build a map from a list of key/value pairs with a combining function.cfromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]True0fromListWith (++) [] == (empty :: DivMap String)True\mathcal{O}(wn\log n)H. Build a map from a list of key/value pairs with a combining function.$let f k a1 a2 = (show k) ++ a1 ++ a2ffromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]True0fromListWithKey f [] == (empty :: DivMap String)True\mathcal{O}(n),. Map a function over all values in the map.Mmap (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]True\mathcal{O}(n),. Map a function over all values in the map.$let f key x = (show key) ++ ":" ++ xOmapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]True\mathcal{O}(n).  f m ==   $  ((k, v) -> (v' -> v'  (k,v'))  $ f k v) (toList m)* That is, it behaves much like a regular  except that the traversing function also has access to the key associated with a value and the values are forced before they are installed in the result map.traverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])TruestraverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')]) == NothingTrue\mathcal{O}(n). The function N threads an accumulating argument through the map in ascending order of keys.let f a b = (a ++ b, b ++ "X")nmapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])True\mathcal{O}(n). The function N threads an accumulating argument through the map in ascending order of keys.:let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")ymapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])True\mathcal{O}(wn\log n).  c f s! is the map obtained by applying f to each key of s.)The size of the result may be smaller if fr maps two or more distinct keys to the same new key. In this case the associated values will be combined using c.TmapKeysWith (+) (\ _ -> 1) (fromList [(1,1), (2,2), (3,3), (4,4)]) == singleton 1 10TrueSmapKeysWith (+) (\ _ -> 3) (fromList [(1,1), (2,1), (3,1), (4,1)]) == singleton 3 4True\mathcal{O}(n)(. Traverse keys/values and collect the  results.\mathcal{O}(n). Map values and collect the  results.4let f x = if x == "a" then Just "new a" else Nothing?mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"True\mathcal{O}(n)#. Map keys/values and collect the  results.Clet f k _ = if k == 3 then Just ("key : " ++ (show k)) else NothingHmapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"True\mathcal{O}(n). Map 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")])A == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")]):}True:{L mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])= == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]):}True\mathcal{O}(n)$. Map keys/values and separate the  and  results.@let f (Div 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")])? == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")]):}True:{T mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])= == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")]):}TrueN "#$%&./=>?@ABCDEFGMOPQRSTUVWXYZ^_`aghijklN "%#$&./=>?@ABCDEFGMOQTVPSRUWXYZ^_`aghijkl(c) Sebastian Graf 2017 MIT sgraf1337@gmail.com  portable None-D,\mathcal{O}(1). A map with a single element.singleton 1 'a'fromList [(1,'a')]size (singleton 1 'a')1\mathcal{O}(w\log n). 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.  is equivalent to  .Iinsert 5 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'x')]TrueRinsert 7 'x' (fromList [(5,'a'), (3,'b')]) == fromList [(3,'b'), (5,'a'), (7,'x')]True=insert 5 'x' empty == singleton 5 'x'True\mathcal{O}(w\log n)>. 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).YinsertWith (++) 5 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "xxxa")]TruebinsertWith (++) 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]TrueJinsertWith (++) 5 "xxx" empty == singleton 5 "xxx"True\mathcal{O}(w\log n)C. 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);. Note that the key passed to f is the same key passed to .Rlet 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")]TruebinsertWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "xxx")]TrueJinsertWithKey f 5 "xxx" empty == singleton 5 "xxx"True\mathcal{O}(w\log n)G. Combines insert operation with old value retrieval. The expression ( f k x map2) is a pair where the first element is equal to ( k map$) and the second element equal to ( f k x map).Rlet f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_valueninsertLookupWithKey f 5 "xxx" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:xxx|a")])TruetinsertLookupWithKey f 7 "xxx" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "xxx")])True\insertLookupWithKey f 5 "xxx" empty == (Nothing, singleton 5 "xxx")TrueThis is how to define  insertLookup using insertLookupWithKey:Blet insertLookup kx x t = insertLookupWithKey (\_ a _ -> a) kx x t]insertLookup 5 "x" (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "x")])TrueginsertLookup 7 "x" (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "x")])True\mathcal{O}(w\log n). Adjust 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.Wadjust ("new " ++) 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]TrueSadjust ("new " ++) 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True;adjust ("new " ++) 7 empty == emptyTrue\mathcal{O}(w\log n). Adjust 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.(let f key x = (show key) ++ ":new " ++ xVadjustWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]TruePadjustWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True8adjustWithKey f 7 empty == emptyTrue\mathcal{O}(w\log n). Adjust a value at a specific key with the result of the provided function and simultaneously look up the old value at that key. When the key is not a member of the map, the original map is returned.Dlet f key old_value = show key ++ ":" ++ show 42 ++ "|" ++ old_valuegadjustLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:42|a")])TruebadjustLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a")])TrueJadjustLookupWithKey f 5 empty == (Nothing, empty)True\mathcal{O}(w\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.4let f x = if x == "a" then Just "new a" else NothingMupdate f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "new a")]TrueIupdate f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True;update f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"True\mathcal{O}(w\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.Elet f k x = if x == "a" then Just ((show k) ++ ":new a") else NothingVupdateWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:new a")]TruePupdateWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]TrueBupdateWithKey f 3 (fromList [(5,"a"), (3,"b")]) == singleton 5 "a"True\mathcal{O}(w\log n). Lookup and update. See also . Warning: Contrary to Data.Map.Strict, the lookup does notG return the updated value, but the old value. This is consistent with  and also Data.IntMap.Strict. .wRe-apply the updating function to the looked-up value once more to get the value in the map, like in the last example:Elet f k x = if x == "a" then Just ((show k) ++ ":new a") else NothinghupdateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b"), (5, "5:new a")])TruebupdateLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a")])TrueTupdateLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")TrueCfst (updateLookupWithKey f 5 (fromList [(5,"a"), (3,"b")])) >>= f 5Just "5:new a"\mathcal{O}(w\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).let f _ = NothingHalter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]True:alter f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"Truelet f _ = Just "c"Ralter f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "c")]TrueHalter f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "c")]True\mathcal{O}(w\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 ( k m).let f _ _ = NothingOalterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a")]TrueAalterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == singleton 3 "b"True!let f k _ = Just (show k ++ ":c")[alterWithKey f 7 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "a"), (7, "7:c")]TrueQalterWithKey f 5 (fromList [(5,"a"), (3,"b")]) == fromList [(3, "b"), (5, "5:c")]True\mathcal{O}(w\log n)". Lookup and alteration. See also .Ilet f k x = if x == Nothing then Just ((show k) ++ ":new a") else NothingWalterLookupWithKey f 5 (fromList [(5,"a"), (3,"b")]) == (Just "a", fromList [(3, "b")])TrueqalterLookupWithKey f 7 (fromList [(5,"a"), (3,"b")]) == (Nothing, fromList [(3, "b"), (5, "a"), (7, "7:new a")])TrueSalterLookupWithKey f 3 (fromList [(5,"a"), (3,"b")]) == (Just "b", singleton 5 "a")True\mathcal{O}(w\log n). The expression ( f k map) alters the value x at k, or absence thereof. @ can be used to inspect, insert, delete, or update a value in a Map . In short:  k <$>  f k m = f ( k m).Example: interactiveAlter :: Divibility -> DivMap String -> IO (DivMap String) interactiveAlter k m = alterF f k m where f Nothing -> do putStrLn $ show k ++ " was not found in the map. Would you like to add it?" getUserResponse1 :: IO (Maybe String) f (Just old) -> do putStrLn "The key is currently bound to " ++ show old ++ ". Would you like to change or delete it?" getUserresponse2 :: IO (Maybe String)  is the most general operation for working with an individual key that may or may not be in a given map. When used with trivial functors like Identity and ConstF, it is often slightly slower than more specialized combinators like  and q. However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.\mathcal{O}(wn\log n). Build a map from a list of key/value pairs. If the list contains more than one value for the same key, the last value for the key is retained.8This version is strict in its values, as opposed to the IsList instance for  .'fromList [] == (empty :: DivMap String)TrueDfromList [(5,"a"), (3,"b"), (5, "c")] == fromList [(5,"c"), (3,"b")]TrueDfromList [(5,"c"), (3,"b"), (5, "a")] == fromList [(5,"a"), (3,"b")]True\mathcal{O}(wn\log n)H. Build a map from a list of key/value pairs with a combining function.8This version is strict in its values, as opposed to the IsList instance for  .cfromListWith (++) [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "ab"), (5, "aba")]True0fromListWith (++) [] == (empty :: DivMap String)True\mathcal{O}(wn\log n)H. Build a map from a list of key/value pairs with a combining function.$let f k a1 a2 = (show k) ++ a1 ++ a2ffromListWithKey f [(5,"a"), (5,"b"), (3,"b"), (3,"a"), (5,"a")] == fromList [(3, "3ab"), (5, "5a5ba")]True0fromListWithKey f [] == (empty :: DivMap String)True\mathcal{O}(n),. Map a function over all values in the map.Mmap (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]True\mathcal{O}(n),. Map a function over all values in the map.$let f key x = (show key) ++ ":" ++ xOmapWithKey f (fromList [(5,"a"), (3,"b")]) == fromList [(3, "3:b"), (5, "5:a")]True\mathcal{O}(n).  f m ==   $  ((k, v) -> (v' -> v'  (k,v'))  $ f k v) (toList m)* That is, it behaves much like a regular  except that the traversing function also has access to the key associated with a value and the values are forced before they are installed in the result map.traverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(1, 'a'), (5, 'e')]) == Just (fromList [(1, 'b'), (5, 'f')])TruestraverseWithKey (\(Div k) v -> if odd k then Just (succ v) else Nothing) (fromList [(2, 'c')]) == NothingTrue\mathcal{O}(n). The function N threads an accumulating argument through the map in ascending order of keys.let f a b = (a ++ b, b ++ "X")nmapAccum f "Everything: " (fromList [(5,"a"), (3,"b")]) == ("Everything: ba", fromList [(3, "bX"), (5, "aX")])True\mathcal{O}(n). The function N threads an accumulating argument through the map in ascending order of keys.:let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X")ymapAccumWithKey f "Everything:" (fromList [(5,"a"), (3,"b")]) == ("Everything: 3-b 5-a", fromList [(3, "bX"), (5, "aX")])True\mathcal{O}(wn\log n).  c f s! is the map obtained by applying f to each key of s.)The size of the result may be smaller if fr maps two or more distinct keys to the same new key. In this case the associated values will be combined using c.TmapKeysWith (+) (\ _ -> 1) (fromList [(1,1), (2,2), (3,3), (4,4)]) == singleton 1 10TrueSmapKeysWith (+) (\ _ -> 3) (fromList [(1,1), (2,1), (3,1), (4,1)]) == singleton 3 4True\mathcal{O}(n)(. Traverse keys/values and collect the  results. Contrary to , this is value-strict.\mathcal{O}(n). Map values and collect the  results.4let f x = if x == "a" then Just "new a" else Nothing?mapMaybe f (fromList [(5,"a"), (3,"b")]) == singleton 5 "new a"True\mathcal{O}(n)#. Map keys/values and collect the  results.Clet f k _ = if k == 3 then Just ("key : " ++ (show k)) else NothingHmapMaybeWithKey f (fromList [(5,"a"), (3,"b")]) == singleton 3 "key : 3"True\mathcal{O}(n). Map 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")])A == (fromList [(3,"b"), (5,"a")], fromList [(1,"x"), (7,"z")]):}True:{L mapEither (\ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])= == (empty, fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")]):}True\mathcal{O}(n)$. Map keys/values and separate the  and  results.@let f (Div 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")])? == (fromList [(1,2), (3,6)], fromList [(5,"aa"), (7,"zz")]):}True:{T mapEitherWithKey (\_ a -> Right a) (fromList [(5,"a"), (3,"b"), (1,"x"), (7,"z")])= == (empty, fromList [(1,"x"), (3,"b"), (5,"a"), (7,"z")]):}TrueN "#$%&./=>?@ABCDEFGMOPQRSTUVWXYZ^_`aghijklN "%#$&./=>?@ABCDEFGMOQTVPSRUWXYZ^_`aghijklNoneFThR"A set of partially ordered values k.\mathcal{O}(1)%. The number of elements in this set.\mathcal{O}(w) . The width w of the chain decomposition in the internal data structure. This is always at least as big as the size of the biggest possible anti-chain.\mathcal{O}(w\log n),. Is the key a member of the map? See also .\mathcal{O}(w\log n)0. Is the key not a member of the map? See also .\mathcal{O}(w\log n)t. Find the largest set of keys smaller than the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.lookupLT 3 (fromList [3, 5])[]lookupLT 6 (fromList [3, 5])[3]\mathcal{O}(w\log n)s. Find the largest key smaller or equal to the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.lookupLE 2 (fromList [3, 5])[]lookupLE 3 (fromList [3, 5])[3]lookupLE 10 (fromList [3, 5])[5]\mathcal{O}(w\log n)t. Find the smallest key greater or equal to the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.lookupGE 3 (fromList [3, 5])[3]lookupGE 5 (fromList [3, 10])[10]lookupGE 6 (fromList [3, 5])[]\mathcal{O}(w\log n)m. Find the smallest key greater than the given one and return the corresponding list of (key, value) pairs.,Note that the following examples assume the  Divisibility# partial order defined at the top.lookupGT 3 (fromList [6, 5])[6]lookupGT 5 (fromList [3, 5])[]!\mathcal{O}(n_2 w_1 n_1 \log n_1). (s1  s2) tells whether s1 is a subset of s2.!\mathcal{O}(n_2 w_1 n_1 \log n_1)9. Is this a proper subset? (ie. a subset but not equal).\mathcal{O}(1). The empty set.\mathcal{O}(1). A set with a single element.\mathcal{O}(w\log n)h. If the key is already present in the map, the associated value is replaced with the supplied value.  is equivalent to  insertWith .\mathcal{O}(w\log n) . Delete an element from a set.\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)X. The union of two sets, preferring the first set when equal elements are encountered.\mathcal{O}(wn\log n), where  n=\max_i n_i and  w=\max_i w_i!. The union of a list of sets: ( ==   ).\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2). Difference of two sets.\mathcal{O}(wn\log n), where n=\max(n_1,n_2) and w=\max(w_1,w_2)`. The intersection of two sets. Elements of the result come from the first set, so for exampledata AB = A | B deriving Show"instance Eq AB where _ == _ = True-instance PartialOrd AB where _ `leq` _ = True&singleton A `intersection` singleton B fromList [A]&singleton B `intersection` singleton A fromList [B]\mathcal{O}(n)2. Filter all elements that satisfy the predicate.\mathcal{O}(n). Partition the set into two sets, one with all elements that satisfy the predicate and one with all elements that don't satisfy the predicate.\mathcal{O}(wn\log n).  f s! is the set obtained by applying f to each element of s.KIt's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f y\mathcal{O}(n).  f s ==  f s, but works only when f is strictly increasing.  The precondition is not checked.! Semi-formally, for every chain ls in s we have: `and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapMonotonic f s == map f s\mathcal{O}(n). A strict version of . Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.\mathcal{O}(n). A strict version of . Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.\mathcal{O}(w\log n). The minimal keys of the set.\mathcal{O}(w\log n). The maximal keys of the set.\mathcal{O}(n).. The elements of a set in unspecified order.\mathcal{O}(n).. The elements of a set in unspecified order.\mathcal{O}(wn\log n)#. Build a set from a list of keys.&(c) Sebastian Graf 2017 MIT sgraf1337@gmail.com  portable NoneǏ     !"#$%&'()*+,-./0123456789:;<=>?@ ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~34567<=>?@ ABDFghSTUVWYomnpq34567<=>?@ ABDFghSTUVWYomnpq!"%&./01234:HKMPikS[^vwbe    $  %pomaps-0.0.0.4-DrSy57Iycg9ECHlNFPRdQoData.POMap.Lazy Data.POSetData.POMap.InternalData.POMap.StrictData.POSet.InternalPreludefoldData.IntMap.LazyupdateLookupWithKeyData.IntMap.Strictbase Data.Foldablenullfoldlfoldr LookupResult IncomparableNotFoundFoundRelationalOperatorLessThan LessEqualEqual GreaterEqual GreaterThanPOMapSingIAreWeStrict areWeStrictseq'seqListmkPOMapchainDecompositionsizewidth foldEntrylookupmember notMemberfindWithDefaultflipRelationalOperatorcontainsOrderingcomparePartialaddToAntichaindedupAntichainlookupXlookupLTlookupLElookupGElookupGTempty singletoninsert insertWith insertWithKeyinsertLookupWithKeykeyedInsertAsAlter overChainsdelete deleteLookupadjust adjustWithKeyadjustLookupWithKeyupdate updateWithKeyalter alterWithKey alterChainalterLookupWithKeyalterLookupChainalterF alterFChainunion unionWith unionWithKeyunions unionsWith differencedifferenceWithdifferenceWithKey intersectionintersectionWithintersectionWithKeymap mapWithKeytraverseWithKeymapAccummapAccumWithKeymapKeys mapKeysWithmapKeysMonotonicfoldr' foldrWithKey foldrWithKey'foldl' foldlWithKey foldlWithKey'foldMapWithKeyelemskeysassocstoList fromListImpl fromListWithfromListWithKeyfilter filterWithKey partitionpartitionWithKeymapMaybemapMaybeWithKeytraverseMaybeWithKey mapEithermapEitherWithKey isSubmapOf isSubmapOfByisProperSubmapOfisProperSubmapOfBy lookupMin lookupMax$fSingIAreWeStrictLazy$fSingIAreWeStrictStrict$fTraversablePOMap$fFoldablePOMap$fFunctorPOMap $fIsListPOMap $fNFDataPOMap$fPartialOrdPOMap $fEqPOMap $fReadPOMap $fShowPOMap$fOrdLookupResult$fEqRelationalOperator$fOrdRelationalOperator$fShowRelationalOperator$fEqLookupResult$fShowLookupResult$fFunctorLookupResultfromListPOSet isSubsetOfisProperSubsetOf mapMonotonic $fIsListPOSet$fFoldablePOSet $fNFDataPOSet $fReadPOSet $fShowPOSet$fPartialOrdPOSet $fEqPOSetGHC.BaseconstNothingJust Data.Tupleuncurryghc-prim GHC.TypesTrueFalseGHC.ListData.TraversabletraverseGHC.Primseq Data.EitherLeftRight