h$6&      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                                                                  (c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&39#nonempty-containers>A non-empty (by construction) map from integer keys to values a-. At least one key-value pair exists in an  v at all times.Functions that take an  can safely operate on it with the assumption that it has at least one key-value pair.Functions that return an  provide an assurance that the result has at least one key-value pair.Data.IntMap.NonEmpty re-exports the API of  Data.IntMap, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output maps are both non-empty (like   ) return , but functions that might potentially return an empty map (like   ) return a  instead.You can directly construct an  with the API from Data.IntMap.NonEmpty7; it's more or less the same as constructing a normal ", except you don't have access to .. There are also a few ways to construct an  from a : The " smart constructor will convert a  k a into a  ( k a) , returning  if the original  was empty.You can use the 3 family of functions to insert a value into a  to create a guaranteed .You can use the  and " patterns to "pattern match" on a * to reveal it as either containing a  or an empty map. offers a continuation-based interface for deconstructing a ' and treating it as if it were an .You can convert an  into a  with  or , essentially "obscuring" the non-empty property from the type.nonempty-containers3invariant: must be smaller than smallest key in mapnonempty-containersO(n). Fold the values in the map using the given right-associative binary operator, such that  f z ==  f z . .  elemsList map = foldr (:) [] map let f a len = len + (length a) foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 nonempty-containersO(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. nonempty-containersO(n). A version of  that uses the value at the maximal key in the map as the starting value.Note that, unlike  for 9, this function is total if the input function is total. nonempty-containersO(n). Fold the values in the map using the given left-associative binary operator, such that   f z ==  f z . . )elemsList = reverse . foldl (flip (:)) [] let f len a = len + (length a) foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 nonempty-containersO(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. nonempty-containersO(n). A version of   that uses the value at the minimal key in the map as the starting value.Note that, unlike  for 9, this function is total if the input function is total.nonempty-containersO(n). Fold the keys and values in the map using the given semigroup, such that  f =  .  fWARNING: Differs from Data.IntMap.foldMapWithKey=, which traverses positive items first, then negative items.+This can be an asymptotically faster than  or  for some monoids.nonempty-containersO(n)/. IntMap a function over all values in the map. map (++ "x") (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "bx") :| [(5, "ax")])nonempty-containersO(m*log(n/m + 1)), m <= n. The expression ( t1 t2!) takes the left-biased union of t1 and t2 . It prefers t1- when duplicate keys are encountered, i.e. ( ==  ). union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")])nonempty-containers2The left-biased union of a non-empty list of maps. unions (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])]) == fromList [(3, "b"), (5, "a"), (7, "C")] unions (fromList ((5, "A3") :| [(3, "B3")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "a") :| [(3, "b")])]) == fromList ((3, "B3") :| [(5, "A3"), (7, "C")])nonempty-containersO(n). Return all elements of the map in the ascending order of their keys. 9elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])nonempty-containersO(1). The number of elements in the map. Guaranteed to be greater than zero. size (singleton 1 'a') == 1 size (fromList ((1,'a') :| [(2,'c'), (3,'b')])) == 3nonempty-containersO(log n). Convert a non-empty map back into a normal possibly-empty map, for usage with functions that expect .Can be thought of as "obscuring" the non-emptiness of the map in its type. See the  pattern. and    form an isomorphism: they are perfect structure-preserving inverses of eachother. toMap (fromList ((3,"a") :| [(5,"b")])) == Data.IntMap.fromList [(3,"a"), (5,"b")]nonempty-containersO(n).  f m ==   $  ((k, v) -> (,) k  $ f k v) ( m)* That is, behaves exactly like a regular  except that the traversing function also has access to the key associated with a value.Use  whenever possible (if your  also has  instance). This version is provided only for types that do not have  instance, since  is not at the moment (and might not ever be) an official superclass of .WARNING: Differs from Data.IntMap.traverseWithKey=, which traverses positive items first, then negative items.  f =  .  (\k -> WrapApplicative . f k) nonempty-containersO(n).  f m ==   $  ((k, v) -> (,) k  $ f k v) ( m)(That is, behaves exactly like a regular  except that the traversing function also has access to the key associated with a value.WARNING: Differs from Data.IntMap.traverseWithKey=, which traverses positive items first, then negative items.Is more general than , since works with all , and not just .nonempty-containersO(n)9. Convert the map to a non-empty list of key/value pairs. toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])nonempty-containersO(log n). Smart constructor for an  from a  . Returns  if the $ was originally actually empty, and  n with an  , if the  was not empty. and    form an isomorphism: they are perfect structure-preserving inverses of eachother.See  for a pattern synonym that lets you "match on" the possiblity of a  being an . nonEmptyMap (Data.IntMap.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")]))nonempty-containersO(log n)0. A general continuation-based way to consume a  as if it were an .  def f will take a ). If map is empty, it will evaluate to def. Otherwise, a non-empty map  will be fed to the function f instead.  ==   nonempty-containers O(n*log n). Build a non-empty map from a non-empty list of key/value pairs. See also . If the list contains more than one value for the same key, the last value for the key is retained. fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")]) fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")])nonempty-containersO(1). A map with a single element. singleton 1 'a' == fromList ((1, 'a') :| []) size (singleton 1 'a') == 1nonempty-containersO(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).See . for a version where the first argument is a . 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")])nonempty-containersO(n).. Test if the internal map structure is valid.nonempty-containersO(log n)6. Insert new key and value into a map where keys are strictly greater than- the new key. That is, the new key must be strictly less than all keys present in the &. /The precondition is not checked./*At the moment this is simply an alias for Data.IntSet.insert, but it's left here as a placeholder in case this eventually gets implemented in a more efficient way.nonempty-containersO(log n)6. Insert new key and value into a map where keys are strictly less than- the new key. That is, the new key must be strictly greater than all keys present in the &. /The precondition is not checked./*At the moment this is simply an alias for Data.IntSet.insert, but it's left here as a placeholder in case this eventually gets implemented in a more efficient way. nonempty-containersO(n). A fixed version of  2 that traverses items in ascending order of keys.!nonempty-containersCPP for new functions not in old containers ---------------------------------------------Compatibility layer for !"."nonempty-containersCompatibility layer for !#.#nonempty-containers( gets the value at the minimal key, and  produces a map of maps comprised of all keys from the original map greater than or equal to the current key.$nonempty-containers-Traverses elements in order of ascending keysWARNING:  and  are different  and  for the  instance of =. They traverse elements in order of ascending keys, while 4 traverses positive keys first, then negative keys.%nonempty-containers-Traverses elements in order of ascending keysWARNING:  and  are different than  and  for the  instance of =. They traverse elements in order of ascending keys, while 4 traverses positive keys first, then negative keys.&nonempty-containers-Traverses elements in order of ascending keysWARNING: Different than for the  instance. They traverse elements in order of ascending keys, while 4 traverses positive keys first, then negative keys.'nonempty-containers.Traverses elements in order of ascending keys.WARNING:  and  are different than for the  instance. They traverse elements in order of ascending keys, while 3 traverses positive keys first, then negative keys., , $, % are all total.)nonempty-containersLeft-biased unionnonempty-containersvalue to return if map is emptynonempty-containers%function to apply if map is not empty!  !"!  !"(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&3M86nonempty-containersA non-empty (by construction) set of integers. At least one value exists in an 6 a at all times.Functions that take an 6 can safely operate on it with the assumption that it has at least one item.Functions that return an 6= provide an assurance that the result has at least one item.Data.IntSet.NonEmpty re-exports the API of  Data.IntSet, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output sets are both non-empty (like   ) return 6, but functions that might potentially return an empty map (like   ) return a  instead.You can directly construct an 6 with the API from Data.IntSet.NonEmpty7; it's more or less the same as constructing a normal ", except you don't have access to &.. There are also a few ways to construct an 6 from a : The :" smart constructor will convert a  a into a  (6 a) , returning  if the original  was empty.You can use the '3 family of functions to insert a value into a  to create a guaranteed 6.You can use the  and " patterns to "pattern match" on a * to reveal it as either containing a 6 or an empty map.; offers a continuation-based interface for deconstructing a " and treating it as if it were an 6.You can convert an 6 into a  with < or , essentially "obscuring" the non-empty property from the type.8nonempty-containers5invariant: must be smaller than smallest value in set:nonempty-containersO(log n). Smart constructor for an 6 from a  . Returns  if the $ was originally actually empty, and  n with an 6 , if the  was not empty.: and  & < form an isomorphism: they are perfect structure-preserving inverses of eachother.See  for a pattern synonym that lets you "match on" the possiblity of a  being an 6. nonEmptySet (Data.IntSet.fromList [3,5]) == Just (fromList (3:|[5]));nonempty-containersO(log n)0. A general continuation-based way to consume a  as if it were an 6. ; def f will take a ). If set is empty, it will evaluate to def. Otherwise, a non-empty set 6 will be fed to the function f instead. : == ;  <nonempty-containersO(log n). Convert a non-empty set back into a normal possibly-empty map, for usage with functions that expect .Can be thought of as "obscuring" the non-emptiness of the set in its type. See the  pattern.: and  & < form an isomorphism: they are perfect structure-preserving inverses of eachother. toSet (fromList ((3,"a") :| [(5,"b")])) == Data.IntSet.fromList [(3,"a"), (5,"b")]=nonempty-containersO(1). Create a singleton set.>nonempty-containers O(n*log n)'. Create a set from a list of elements.?nonempty-containersO(n)2. Convert the set to a non-empty list of elements.@nonempty-containersO(m*log(n/m + 1)), m <= n. The union of two sets, preferring the first set when equal elements are encountered.Anonempty-containers%The union of a non-empty list of setsBnonempty-containersO(n).. Test if the internal set structure is valid.Cnonempty-containersO(log n)0. Insert new value into a set where values are strictly greater than1 the new values That is, the new value must be strictly less than all values present in the &. /The precondition is not checked./*At the moment this is simply an alias for Data.IntSet.insert, but it's left here as a placeholder in case this eventually gets implemented in a more efficient way.Dnonempty-containersO(log n). Insert new value into a set where values are /strictly less than0 the new value. That is, the new value must be strictly greater than all values present in the . "The precondition is not checked./*At the moment this is simply an alias for Data.IntSet.insert, but it's left here as a placeholder in case this eventually gets implemented in a more efficient way.Enonempty-containersCPP for new functions not in old containers ---------------------------------------------Comptability layer for &(.Fnonempty-containersLeft-biased union;nonempty-containersvalue to return if set is emptynonempty-containers%function to apply if set is not empty6789:;<=>?@ABCDE6789:;<=>?@ABCDE(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&F.Ononempty-containersO(1). The P and O patterns allow you to treat a  as if it were either a P n (where n is a 6) or an O. Matching on O means that the original  was empty.A case statement handling both P and O provides complete coverage.0This is a bidirectional pattern, so you can use O2 as an expression, and it will be interpreted as &.See P for more information.Pnonempty-containersO(1) match, O(log n) usage of contents. The P and O patterns allow you to treat a  as if it were either a P n (where n is a 6) or an O.(For example, you can pattern match on a :  myFunc ::  X -> Y myFunc (P7 n) = -- here, the user provided a non-empty set, and n is the 6 myFunc O3 = -- here, the user provided an empty set  Matching on P n means that the original  was not+ empty, and you have a verified-non-empty 6 n to use.&Note that patching on this pattern is O(1)+. However, using the contents requires a O(log n) cost that is deferred until after the pattern is matched on (and is not incurred at all if the contents are never used).A case statement handling both P and O provides complete coverage.0This is a bidirectional pattern, so you can use P to convert a 6 back into a #, obscuring its non-emptiness (see <).Qnonempty-containersO(log n) . Convert a  into an 6 by adding a value. Because of this, we know that the set must have at least one element, and so therefore cannot be empty.See R: for a version that is constant-time if the new value is strictly smaller than all values in the original set insertSet 4 (Data.IntSet.fromList [5, 3]) == fromList (3 :| [4, 5]) insertSet 4 Data.IntSet.empty == singleton 4 "c"Rnonempty-containersO(1) Convert a  into an 6' by adding a value where the value is strictly less than all values in the input set The values in the original map must all be strictly greater than the new value.  The precondition is not checked. insertSetMin 2 (Data.IntSet.fromList [5, 3]) == fromList (2 :| [3, 5]) valid (insertSetMin 2 (Data.IntSet.fromList [5, 3])) == True valid (insertSetMin 7 (Data.IntSet.fromList [5, 3])) == False valid (insertSetMin 3 (Data.IntSet.fromList [5, 3])) == FalseSnonempty-containersO(log n) Convert a  into an 6' by adding a value where the value is strictly less than all values in the input set The values in the original map must all be strictly greater than the new value.  The precondition is not checked.0At the current moment, this is identical simply Q; however, it is left both for consistency and as a placeholder for a future version where optimizations are implemented to allow for a faster implementation. insertSetMin 7 (Data.IntSet.fromList [5, 3]) == fromList (3 :| [5, 7])Tnonempty-containersO(log n). Unsafe version of : . Coerces a  into an 6, but is undefined (throws a runtime exception when evaluation is attempted) for an empty .Unonempty-containersO(n). Build a set from an ascending list in linear time. /The precondition (input list is ascending) is not checked./Vnonempty-containersO(n). Build a set from an ascending list of distinct elements in linear time. The precondition (input list is strictly ascending) is not checked.Wnonempty-containersO(log n). Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.Xnonempty-containersO(log n). Delete an element from a set.Ynonempty-containersO(log n). Is the element in the set?Znonempty-containersO(log n) . Is the element not in the set?[nonempty-containersO(log n)2. Find largest element smaller than the given one. lookupLT 3 (fromList (3 :| [5])) == Nothing lookupLT 5 (fromList (3 :| [5])) == Just 3\nonempty-containersO(log n)3. Find smallest element greater than the given one. lookupLT 4 (fromList (3 :| [5])) == Just 5 lookupLT 5 (fromList (3 :| [5])) == Nothing]nonempty-containersO(log n)9. Find largest element smaller or equal to the given one. lookupLT 2 (fromList (3 :| [5])) == Nothing lookupLT 4 (fromList (3 :| [5])) == Just 3 lookupLT 5 (fromList (3 :| [5])) == Just 5^nonempty-containersO(log n):. Find smallest element greater or equal to the given one. lookupLT 3 (fromList (3 :| [5])) == Just 3 lookupLT 4 (fromList (3 :| [5])) == Just 5 lookupLT 6 (fromList (3 :| [5])) == Nothing_nonempty-containersO(n). Fold the elements in the set using the given right-associative binary operator, such that _ f z ==  f z . {. For example,  elemsList set = foldr (:) [] set`nonempty-containersO(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.anonempty-containersO(n). A version of _ that uses the value at the maximal value in the set as the starting value.Note that, unlike  for 9, this function is total if the input function is total.bnonempty-containersO(n). Fold the elements in the set using the given left-associative binary operator, such that b f z ==  f z . {. For example, +descElemsList set = foldl (flip (:)) [] setcnonempty-containersO(n). A strict version of b. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.dnonempty-containersO(n). A version of b that uses the value at the minimal value in the set as the starting value.Note that, unlike  for 9, this function is total if the input function is total.enonempty-containersO(n). A strict version of a. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.fnonempty-containersO(n). A strict version of d. Each application of the operator is evaluated before using the result in the next application. This function is strict in the starting value.gnonempty-containersO(1). The number of elements in the set. Guaranteed to be greater than zero.hnonempty-containersO(n+m). Is this a subset? (s1 `isSubsetOf` s2) tells whether s1 is a subset of s2.inonempty-containersO(n+m)8. Is this a proper subset? (ie. a subset but not equal).jnonempty-containersO(n+m). Check whether two sets are disjoint (i.e. their intersection is empty). disjoint (fromList (2:|[4,6])) (fromList (1:|[3])) == True disjoint (fromList (2:|[4,6,8])) (fromList (2:|[3,5,7])) == False disjoint (fromList (1:|[2])) (fromList (1:|[2,3,4])) == Falseknonempty-containersO(m*log(n/m + 1)), m <= n. Difference of two sets.!Returns a potentially empty set () because the first set might be a subset of the second set, and therefore have all of its elements removed.lnonempty-containersSame as k.mnonempty-containersO(m*log(n/m + 1)), m <= n. The intersection of two sets.!Returns a potentially empty set (:), because the two sets might have an empty intersection.>Elements of the result come from the first set, so for example import qualified Data.IntSet.NonEmpty as NES data AB = A | B deriving Show instance Ord AB where compare _ _ = EQ instance Eq AB where _ == _ = True main = print (NES.singleton A `NES.intersection` NES.singleton B, NES.singleton B `NES.intersection` NES.singleton A)prints #(fromList (A:|[]),fromList (B:|[])).nnonempty-containersO(n)1. Filter all elements that satisfy the predicate.!Returns a potentially empty set () because the predicate might filter out all items in the original non-empty set.ononempty-containersO(n)-. Partition the map according to a predicate. Returns a % with potentially two non-empty sets: n11 means that the predicate was true for all items. n22 means that the predicate was false for all items. n1 n2 gives n1> (all of the items that were true for the predicate) and n2; (all of the items that were false for the predicate). See also p. partition (> 3) (fromList (5 :| [3])) == These (singleton 5) (singleton 3) partition (< 7) (fromList (5 :| [3])) == This (fromList (3 :| [5])) partition (> 7) (fromList (5 :| [3])) == That (fromList (3 :| [5]))pnonempty-containersO(log n). The expression (p x set) is potentially a  containing up to two 6s based on splitting the set into sets containing items before and after the value x-. It will never return a set that contains x itself. means that x was the only value in the the original set, and so there are no items before or after it. ( n1) means x< was larger than or equal to all items in the set, and n1# is the entire original set (minus x, if it was present) ( n2) means x= was smaller than or equal to all items in the set, and n2# is the entire original set (minus x, if it was present) ( n1 n2) gives n1= (the set of all values from the original set less than x) and n2 (the set of all values from the original set greater than x). split 2 (fromList (5 :| [3])) == Just (That (fromList (3 :| [5])) ) split 3 (fromList (5 :| [3])) == Just (That (singleton 5) ) split 4 (fromList (5 :| [3])) == Just (These (singleton 3) (singleton 5)) split 5 (fromList (5 :| [3])) == Just (This (singleton 3) ) split 6 (fromList (5 :| [3])) == Just (This (fromList (3 :| [5])) ) split 5 (singleton 5) == Nothingqnonempty-containersO(log n). The expression (q x set) splits a set just like p but also returns Y x set (whether or not x was in set) splitMember 2 (fromList (5 :| [3])) == (False, Just (That (fromList (3 :| [5)])))) splitMember 3 (fromList (5 :| [3])) == (True , Just (That (singleton 5))) splitMember 4 (fromList (5 :| [3])) == (False, Just (These (singleton 3) (singleton 5))) splitMember 5 (fromList (5 :| [3])) == (True , Just (This (singleton 3)) splitMember 6 (fromList (5 :| [3])) == (False, Just (This (fromList (3 :| [5]))) splitMember 5 (singleton 5) == (True , Nothing)rnonempty-containersO(1). Decompose a set into pieces based on the structure of the underlying tree. This function is useful for consuming a set in parallel.No guarantee is made as to the sizes of the pieces; an internal, but deterministic process determines this. However, it is guaranteed that the pieces returned will be in ascending order (all elements in the first subset less than all elements in the second, and so on).Note that the current implementation does not return more than four subsets, but you should not depend on this behaviour because it can change in the future without notice.snonempty-containers O(n*log n). s f s! is the set obtained by applying f to each element of s.It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f ytnonempty-containersO(1). The minimal element of a set. Note that this is total, making &) obsolete. It is constant-time, so has better asymptotics than Data.IntSet.lookupMin and Data.Map.findMin as well. "findMin (fromList (5 :| [3])) == 3unonempty-containersO(log n)=. The maximal key of a set Note that this is total, making &) obsolete. "findMax (fromList (5 :| [3])) == 5vnonempty-containersO(1). Delete the minimal element. Returns a potentially empty set (), because we might delete the final item in a singleton set. It is constant-time, so has better asymptotics than Data.IntSet.deleteMin. deleteMin (fromList (5 :| [3, 7])) == Data.IntSet.fromList [5, 7] deleteMin (singleton 5) == Data.IntSet.emptywnonempty-containersO(log n). Delete the maximal element. Returns a potentially empty set (=), because we might delete the final item in a singleton set. deleteMax (fromList (5 :| [3, 7])) == Data.IntSet.fromList [3, 5] deleteMax (singleton 5) == Data.IntSet.emptyxnonempty-containersO(1). Delete and find the minimal element. It is constant-time, so has better asymptotics that Data.IntSet.minView for .Note that unlike Data.IntSet.deleteFindMin for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original set might have contained just a single item. deleteFindMin (fromList (5 :| [3, 10])) == (3, Data.IntSet.fromList [5, 10])ynonempty-containersO(log n)&. Delete and find the minimal element.Note that unlike Data.IntSet.deleteFindMax for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original set might have contained just a single item. deleteFindMax (fromList (5 :| [3, 10])) == (10, Data.IntSet.fromList [3, 5])znonempty-containersO(n). An alias of {,. The elements of a set in ascending order.{nonempty-containersO(n)=. Convert the set to an ascending non-empty list of elements.|nonempty-containersO(n)=. Convert the set to a descending non-empty list of elements.96:;<=>?@ABOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|96PO:<;QRST=>UVWXYZ[\]^ghij@Aklmnopqrs_bad`ceftuvwxyz?{|B(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&;}nonempty-containersO(1). The ~ and } patterns allow you to treat a  as if it were either a ~ n (where n is a ) or an }. Matching on } means that the original  was empty.A case statement handling both ~ and } provides complete coverage.0This is a bidirectional pattern, so you can use }2 as an expression, and it will be interpreted as .See ~ for more information.~nonempty-containersO(1) match, O(log n) usage of contents. The ~ and } patterns allow you to treat a  as if it were either a ~ n (where n is a ) or an }.(For example, you can pattern match on a :  myFunc ::  K X -> Y myFunc (~7 n) = -- here, the user provided a non-empty map, and n is the  myFunc }4 = -- here, the user provided an empty map.  Matching on ~ n means that the original  was not+ empty, and you have a verified-non-empty  n to use.&Note that patching on this pattern is O(1)+. However, using the contents requires a O(log n) cost that is deferred until after the pattern is matched on (and is not incurred at all if the contents are never used).A case statement handling both ~ and } provides complete coverage.0This is a bidirectional pattern, so you can use ~ to convert a  back into a #, obscuring its non-emptiness (see ).nonempty-containersO(log n). Unsafe version of  . Coerces a  into an , but is undefined (throws a runtime exception when evaluation is attempted) for an empty .nonempty-containersO(log n) . Convert a  into an  by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. If key is already present, will overwrite the original value.See 8 for a version that is constant-time if the new key is strictly smaller than all keys in the original map. insertMap 4 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")]) insertMap 4 "c" Data.IntMap.empty == singleton 4 "c"nonempty-containersO(log n) . Convert a  into an  by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. Uses a combining function with the new value as the first argument if the key is already present. insertMapWith (++) 4 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")]) insertMapWith (++) 5 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"ca")])nonempty-containersO(log n) . Convert a  into an  by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. Uses a combining function with the key and new value as the first and second arguments if the key is already present. let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value insertWithKey f 5 "xxx" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "5:xxx|a")]) insertWithKey f 7 "xxx" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) insertWithKey f 5 "xxx" Data.IntMap.empty == singleton 5 "xxx"nonempty-containersO(1) Convert a  into an . by adding a key-value pair where the key is strictly less than all keys in the input map. The keys in the original map must all be strictly greater than the new key.  The precondition is not checked. insertMapMin 2 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((2,"c") :| [(3,"b"), (5,"a")]) valid (insertMapMin 2 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == True valid (insertMapMin 7 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == False valid (insertMapMin 3 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")])) == Falsenonempty-containersO(log n) Convert a  into an . by adding a key-value pair where the key is strictly greater than all keys in the input map. The keys in the original map must all be strictly less than the new key.  The precondition is not checked.0At the current moment, this is identical simply ; however, it is left both for consistency and as a placeholder for a future version where optimizations are implemented to allow for a faster implementation. insertMap 7 "c" (Data.IntMap.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"a"), (7,"c")])nonempty-containersO(n). Build a non-empty map from a non-empty set of keys and a function which for each key computes its value. fromSet (\k -> replicate k 'a') (Data.Set.NonEmpty.fromList (3 :| [5])) == fromList ((5,"aaaaa") :| [(3,"aaa")])nonempty-containers O(n*log n). Build a map from a non-empty list of key/value pairs with a combining function. See also . fromListWith (++) ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "ab") :| [(5, "aba")])nonempty-containers O(n*log n). Build a map from a non-empty list of key/value pairs with a combining function. See also . let f k a1 a2 = (show k) ++ a1 ++ a2 fromListWithKey f ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "3ab") :| [(5, "5a5ba")])nonempty-containersO(n). Build a map from an ascending non-empty 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")]) valid (fromAscList ((3,"b") :| [(5,"a"), (5,"b")])) == True valid (fromAscList ((5,"a") :| [(3,"b"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from an ascending non-empty 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")]) valid (fromAscListWith (++) ((3,"b") :| [(5,"a"), (5,"b"))]) == True valid (fromAscListWith (++) ((5,"a") :| [(3,"b"), (5,"b"))]) == Falsenonempty-containersO(n). Build a map from an ascending non-empty list in linear time with a combining function for equal keys. /The precondition (input list is ascending) is not checked./ let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2 fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")]) == fromList ((3, "b") :| [(5, "5:b5:ba")]) valid (fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")])) == True valid (fromAscListWithKey f ((5,"a") :| [(3,"b"), (5,"b"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from an ascending non-empty list of distinct elements in linear time.  The precondition is not checked. fromDistinctAscList ((3,"b") :| [(5,"a")]) == fromList ((3, "b") :| [(5, "a")]) valid (fromDistinctAscList ((3,"b") :| [(5,"a")])) == True valid (fromDistinctAscList ((3,"b") :| [(5,"a"), (5,"b")])) == Falsenonempty-containersO(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  .See - for a version where the first argument is a . 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')])nonempty-containersO(log n). 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 .See - for a version where the first argument is a . 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")])nonempty-containersO(log n). 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). 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")]))This is how to define  insertLookup using insertLookupWithKey: let 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")])) insertLookup 7 "x" (fromList ((5,"a") :| [(3,"b")])) == (Nothing, fromList ((3, "b") :| [(5, "a"), (7, "x")]))nonempty-containersO(log n). Delete a key and its value from the non-empty map. A potentially empty map (=) is returned, since this might delete the last item in the >. When the key is not a member of the map, is equivalent to . delete 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b" delete 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.Singleton [(3, "b"), (5, "a")]nonempty-containersO(log n). 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")])nonempty-containersO(log n). 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")])nonempty-containersO(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.!Returns a potentially empty map (), because we can't know ahead of time if the function returns $ and deletes the final item in the . let f x = if x == "a" then Just "new a" else Nothing update f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "new a")] update f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")] update f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"nonempty-containersO(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.!Returns a potentially empty map (), because we can't know ahead of time if the function returns $ and deletes the final item in the . let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing updateWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "5:new a")] updateWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")] updateWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"nonempty-containers O(min(n,W)). Lookup and update. The function returns original value, if it is updated. This is different behavior than %Data.Map.NonEmpty.updateLookupWithKey>. Returns the original key value if the map entry is deleted.!Returns a potentially empty map (?) in the case that we delete the final key of a singleton map. let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing updateLookupWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == (Just "5:new a", Data.IntMap.fromList ((3, "b") :| [(5, "5:new a")])) updateLookupWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == (Nothing, Data.IntMap.fromList ((3, "b") :| [(5, "a")])) updateLookupWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Data.IntMap.singleton 5 "a")nonempty-containersO(log n). The expression ( f k map) alters the value x at k, or absence thereof. 8 can be used to insert, delete, or update a value in a  . In short : Data.IntMap.lookup k ( f k m) = f ( k m).!Returns a potentially empty map (), because we can't know ahead of time if the function returns $ and deletes the final item in the .See  for a version that disallows deletion, and so therefore can return . let f _ = Nothing alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a")] alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b" let f _ = Just "c" alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "a"), (7, "c")] alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "c")]nonempty-containersO(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  . In short: Data.IntMap.lookup k <$>  f k m = f ( k m).Example: interactiveAlter :: Int -> NEIntMap Int String -> IO (IntMap Int 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) Like Data.IntMap.alterF for , 7 can be considered to be a unifying generalization of  and ;; however, as a constrast, it cannot be used to implement , because it must return a  instead of an ; (because the function might delete the final item in the *). When used with trivial functors like  and 0, it is often slightly slower than specialized  and . However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.See  for a version that disallows deletion, and so therefore can return  and be used to implement Note on rewrite rules:3This module includes GHC rewrite rules to optimize  for the  and  functors. In general, these rules improve performance. The sole exception is that when using , deleting a key that is already absent takes longer than it would without the rules. If you expect this to occur a very large fraction of the time, you might consider using a private copy of the  type. Note: Unlike Data.IntMap.alterF for ,  is not a flipped version of the *+ combinator from Control.Lens.At. However, it match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.nonempty-containersO(log n) . Variant of  that disallows deletion. Allows us to guarantee that the result is also a non-empty IntMap.nonempty-containersO(log n) . Variant of  that disallows deletion. Allows us to guarantee that the result is also a non-empty IntMap.Like Data.IntMap.alterF for ', can be used to generalize and unify  and . However, because it disallows deletion, it cannot be used to implement .See # for usage information and caveats.Note: Neither  nor , can be considered flipped versions of the *+ combinator from Control.Lens.At. However, this can match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.WARNING: The rewrite rule for 5 exposes an inconsistency in undefined behavior for  Data.IntMap. Data.IntMap.alterF will actually maintain, the original key in the map when used with  ; however, Data.IntMap.insertWith will replace4 the orginal key in the map. The rewrite rule for  has chosen to be faithful to Data.IntMap.insertWith, and not Data.IntMap.alterF,, for the sake of a cleaner implementation.nonempty-containersO(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.An example of using lookup: import Prelude hiding (lookup) import Data.Map.NonEmpty employeeDept = fromList (("John","Sales") :| [("Bob","IT")]) deptCountry = fromList (("IT","USA") :| [("Sales","France")]) countryCurrency = fromList (("USA", "Dollar") :| [("France", "Euro")]) employeeCurrency :: String -> Maybe String employeeCurrency name = do dept <- lookup name employeeDept country <- lookup dept deptCountry lookup country countryCurrency main = do putStrLn $ "John's currency: " ++ (show (employeeCurrency "John")) putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))The output of this program: 9 John's currency: Just "Euro" Pete's currency: Nothingnonempty-containersO(log n)#. Find the value at a key. Returns $ when the element can not be found.1fromList ((5, 'a') :| [(3, 'b')]) !? 1 == Nothing2fromList ((5, 'a') :| [(3, 'b')]) !? 5 == Just 'a'nonempty-containersO(log n)!. Find the value at a key. Calls $ when the element can not be found. fromList ((5,'a') :| [(3,'b')]) ! 1 Error: element not in the map fromList ((5,'a') :| [(3,'b')]) ! 5 == 'a'nonempty-containersO(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' findWithDefault 'x' 5 (fromList ((5,'a') :| [(3,'b')])) == 'a'nonempty-containersO(log n)+. Is the key a member of the map? See also . member 5 (fromList ((5,'a') :| [(3,'b')])) == True member 1 (fromList ((5,'a') :| [(3,'b')])) == Falsenonempty-containersO(log n)/. Is the key not a member of the map? See also . notMember 5 (fromList ((5,'a') :| [(3,'b')])) == False notMember 1 (fromList ((5,'a') :| [(3,'b')])) == Truenonempty-containersO(log n). Find largest key smaller than the given one and return the corresponding (key, value) pair. lookupLT 3 (fromList ((3,'a') :| [(5,'b')])) == Nothing lookupLT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')nonempty-containersO(log n). Find smallest key greater than the given one and return the corresponding (key, value) pair. lookupGT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b') lookupGT 5 (fromList ((3,'a') :| [(5,'b')])) == Nothingnonempty-containersO(log n). Find largest key smaller or equal to the given one and return the corresponding (key, value) pair. lookupLE 2 (fromList ((3,'a') :| [(5,'b')])) == Nothing lookupLE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a') lookupLE 5 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')nonempty-containersO(log n). Find smallest key greater or equal to the given one and return the corresponding (key, value) pair. lookupGE 3 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a') lookupGE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b') lookupGE 6 (fromList ((3,'a') :| [(5,'b')])) == Nothingnonempty-containersO(m*log(n/m + 1)), m <= n". Union with a combining function. unionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "aA"), (7, "C")])nonempty-containersO(m*log(n/m + 1)), m <= n;. Union with a combining function, given the matching key. let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value unionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "5:a|A"), (7, "C")])nonempty-containersThe union of a non-empty list of maps, with a combining operation: ( f ==  ( f)). unionsWith (++) (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])]) == fromList ((3, "bB3") :| [(5, "aAA3"), (7, "C")])nonempty-containersO(m*log(n/m + 1)), m <= n. Difference of two maps. Return elements of the first map not existing in the second map.!Returns a potentially empty map (8), in case the first map is a subset of the second map. difference (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 3 "b"nonempty-containersSame as .nonempty-containersO(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns , the element is discarded (proper set difference). If it returns ( y+), the element is updated with a new value y.!Returns a potentially empty map (), in case the first map is a subset of the second map and the function returns  for every pair. 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")])) == Data.IntMap.singleton 3 "b:B"nonempty-containersO(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns , the element is discarded (proper set difference). If it returns ( y+), the element is updated with a new value y.!Returns a potentially empty map (), in case the first map is a subset of the second map and the function returns  for every pair. 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")])) == Data.IntMap.singleton 3 "3:b|B"nonempty-containersO(m*log(n/m + 1)), m <= n. Intersection of two maps. Return data in the first map for the keys existing in both maps. ( m1 m2 ==   m1 m2).!Returns a potentially empty map (1), in case the two maps share no keys in common. intersection (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "a"nonempty-containersO(m*log(n/m + 1)), m <= n). Intersection with a combining function.!Returns a potentially empty map (1), in case the two maps share no keys in common. intersectionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "aA"nonempty-containersO(m*log(n/m + 1)), m <= n). Intersection with a combining function.!Returns a potentially empty map (1), in case the two maps share no keys in common. let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar intersectionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.IntMap.singleton 5 "5:a|A"nonempty-containersO(n)/. IntMap 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")])nonempty-containersO(n). The function  threads an accumulating argument through the map in ascending order of keys. let f a b = (a ++ b, b ++ "X") mapAccum f "Everything: " (fromList ((5,"a") :| [(3,"b")])) == ("Everything: ba", fromList ((3, "bX") :| [(5, "aX")]))nonempty-containersO(n). The function  threads an accumulating argument through the map in ascending order of keys. let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X") mapAccumWithKey f "Everything:" (fromList ((5,"a") :| [(3,"b")])) == ("Everything: 3-b 5-a", fromList ((3, "bX") :| [(5, "aX")]))nonempty-containersO(n). The function  threads an accumulating argument through the map in descending order of keys.nonempty-containers O(n*log n).  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.While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty. 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"nonempty-containers O(n*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 f maps two or more distinct keys to the same new key. In this case the associated values will be combined using c. The value at the greater of the two original keys is used as the first argument to c.While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty. 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"nonempty-containersO(n).  f s ==  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, we have: and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f s where ls = keys sThis means that f maps distinct original keys to distinct resulting keys. This function has better performance than .While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty. mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")])) == fromList ((6, "b") :| [(10, "a")]) valid (mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")]))) == True valid (mapKeysMonotonic (\ _ -> 1) (fromList ((5,"a") :| [(3,"b")]))) == Falsenonempty-containersO(n). Fold the keys and values in the map using the given right-associative binary operator, such that  f z ==  ( f) z . . For example, 4keysList map = foldrWithKey (\k x ks -> k:ks) [] mapnonempty-containersO(n). Fold the keys and values in the map using the given left-associative binary operator, such that  f z ==  (\z' (kx, x) -> f z' kx x) z . . For example, 6keysList = reverse . foldlWithKey (\ks k x -> k:ks) []nonempty-containersO(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.nonempty-containersO(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.nonempty-containersO(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.nonempty-containersO(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.nonempty-containersO(n)0. Return all keys of the map in ascending order. 4keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5])nonempty-containersO(n). An alias for . Return all key/value pairs in the map in ascending key order. assocs (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])nonempty-containersO(n)+. The non-empty set of all keys of the map. keysSet (fromList ((5,"a") :| [(3,"b")])) == Data.Set.NonEmpty.fromList (3 :| [5])nonempty-containersO(n). Convert the map to a list of key/value pairs where the keys are in ascending order. toAscList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])nonempty-containersO(n). Convert the map to a list of key/value pairs where the keys are in descending order. toDescList (fromList ((5,"a") :| [(3,"b")])) == ((5,"a") :| [(3,"b")])nonempty-containersO(n)/. Filter all values that satisfy the predicate.!Returns a potentially empty map (), because we could potentailly filter out all items in the original . filter (> "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b" filter (> "x") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.empty filter (< "a") (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.emptynonempty-containersO(n)4. Filter all keys/values that satisfy the predicate.!Returns a potentially empty map (), because we could potentailly filter out all items in the original . filterWithKey (\k _ -> k > 4) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"nonempty-containersO(m*log(n/m + 1)), m <= n. Restrict an  to only those keys found in a ,-. m `restrictKeys` s =  (k _ -> k -. s) m m `restrictKeys` s = m   (const ()) s nonempty-containersO(m*log(n/m + 1)), m <= n. Remove all keys in a ,- from an . m `withoutKeys` s =  (k _ -> k -/ s) m m `withoutKeys` s = m   (const ()) s nonempty-containersO(n)-. Partition the map according to a predicate. Returns a % with potentially two non-empty maps: n11 means that the predicate was true for all items. n22 means that the predicate was false for all items. n1 n2 gives n1> (all of the items that were true for the predicate) and n2; (all of the items that were false for the predicate). See also . partition (> "a") (fromList ((5,"a") :| [(3,"b")])) == These (singleton 3 "b") (singleton 5 "a") partition (< "x") (fromList ((5,"a") :| [(3,"b")])) == This (fromList ((3, "b") :| [(5, "a")])) partition (> "x") (fromList ((5,"a") :| [(3,"b")])) == That (fromList ((3, "b") :| [(5, "a")]))nonempty-containersO(n)-. Partition the map according to a predicate. Returns a % with potentially two non-empty maps: n1 means that the predicate was true for all items, returning the original map. n2 means that the predicate was false for all items, returning the original map. n1 n2 gives n1> (all of the items that were true for the predicate) and n2; (all of the items that were false for the predicate). See also . partitionWithKey (\ k _ -> k > 3) (fromList ((5,"a") :| [(3,"b")])) == These (singleton 5 "a") (singleton 3 "b") partitionWithKey (\ k _ -> k < 7) (fromList ((5,"a") :| [(3,"b")])) == This (fromList ((3, "b") :| [(5, "a")])) partitionWithKey (\ k _ -> k > 7) (fromList ((5,"a") :| [(3,"b")])) == That (fromList ((3, "b") :| [(5, "a")]))nonempty-containersO(n). Map values and collect the  results.!Returns a potentially empty map (2), because the function could potentially return  on all items in the . let f x = if x == "a" then Just "new a" else Nothing mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "new a"nonempty-containersO(n)". Map keys/values and collect the  results.!Returns a potentially empty map (2), because the function could potentially return  on all items in the . let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing mapMaybeWithKey f (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "key : 3"nonempty-containersO(n). Map values and separate the  and  results. Returns a % with potentially two non-empty maps: n1! means that the results were all . n2! means that the results were all . n1 n2 gives n1! (the map where the results were  ) and n2! (the map where the results were ) let f a = if a < "c" then Left a else Right a mapEither f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")])) == These (fromList ((3,"b") :| [(5,"a")])) (fromList ((1,"x") :| [(7,"z")])) mapEither (\ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")])) == That (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))nonempty-containersO(n)#. Map keys/values and separate the  and  results. Returns a % with potentially two non-empty maps: n1! means that the results were all . n2! means that the results were all . n1 n2 gives n1! (the map where the results were  ) and n2! (the map where the results were ) 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")])) == These (fromList ((1,2) :| [(3,6)])) (fromList ((5,"aa") :| [(7,"zz")])) mapEitherWithKey (\_ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")])) == That (fromList ((1,"x") :| [(3,"b"), (5,"a"), (7,"z")]))nonempty-containersO(log n). The expression ( k map) is potentially a  containing up to two s based on splitting the map into maps containing items before and after the given key k-. It will never return a map that contains k itself. means that k was the only key in the the original map, and so there are no items before or after it. ( n1) means k< was larger than or equal to all items in the map, and n1# is the entire original map (minus k, if it was present) ( n2) means k= was smaller than or equal to all items in the map, and n2# is the entire original map (minus k, if it was present) ( n1 n2) gives n1; (the map of all keys from the original map less than k) and n2> (the map of all keys from the original map greater than k) split 2 (fromList ((5,"a") :| [(3,"b")])) == Just (That (fromList ((3,"b") :| [(5,"a")])) ) split 3 (fromList ((5,"a") :| [(3,"b")])) == Just (That (singleton 5 "a") ) split 4 (fromList ((5,"a") :| [(3,"b")])) == Just (These (singleton 3 "b") (singleton 5 "a")) split 5 (fromList ((5,"a") :| [(3,"b")])) == Just (This (singleton 3 "b") ) split 6 (fromList ((5,"a") :| [(3,"b")])) == Just (This (fromList ((3,"b") :| [(5,"a")])) ) split 5 (singleton 5 "a") == Nothingnonempty-containersO(log n). The expression ( k map) splits a map just like  but also returns  k map, as the first field in the : splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == That (That (fromList ((3,"b") :| [(5,"a")]))) splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == These "b" (That (singleton 5 "a")) splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == That (These (singleton 3 "b") (singleton 5 "a")) splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == These "a" (This (singleton 3 "b")) splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == That (This (fromList ((3,"b") :| [(5,"a")]))) splitLookup 5 (singleton 5 "a") == This "a"nonempty-containersO(1). Decompose a map into pieces based on the structure of the underlying tree. This function is useful for consuming a map in parallel.No guarantee is made as to the sizes of the pieces; an internal, but deterministic process determines this. However, it is guaranteed that the pieces returned will be in ascending order (all elements in the first submap less than all elements in the second, and so on).Note that the current implementation does not return more than four submaps, but you should not depend on this behaviour because it can change in the future without notice.nonempty-containersO(m*log(n/m + 1)), m <= n . This function is defined as ( =  (==)).nonempty-containersO(m*log(n/m + 1)), m <= n. The expression ( 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 : isSubmapOfBy (==) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (<=) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (fromList (('a',1) :| [('b',2)]))But the following are all : isSubmapOfBy (==) (singleton 'a' 2) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (<) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (singleton 'a' 1)nonempty-containersO(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a submap but not equal). Defined as ( =  (==)).nonempty-containersO(m*log(n/m + 1)), m <= n. 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 values. For example, the following expressions are all : isProperSubmapOfBy (==) (singleton 1 1) (fromList ((1,1) :| [(2,2)])) isProperSubmapOfBy (<=) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))But the following are all : isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (fromList ((1,1) :| [(2,2)])) isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (singleton 1 1)) isProperSubmapOfBy (<) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))nonempty-containersO(1). The minimal key of the map. Note that this is total, making ) obsolete. It is constant-time, so has better asymptotics than Data.IntMap.lookupMin and Data.IntMap.findMin , as well. 4findMin (fromList ((5,"a") :| [(3,"b")])) == (3,"b")nonempty-containersO(log n). The maximal key of the map. Note that this is total, making ) obsolete. 4findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a")nonempty-containersO(1)<. Delete the minimal key. Returns a potentially empty map (), because we might end up deleting the final key in a singleton map. It is constant-time, so has better asymptotics than 0. deleteMin (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(5,"a"), (7,"c")] deleteMin (singleton 5 "a") == Data.IntMap.emptynonempty-containersO(log n)<. Delete the maximal key. Returns a potentially empty map (), because we might end up deleting the final key in a singleton map. deleteMax (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(3,"b"), (5,"a")] deleteMax (singleton 5 "a") == Data.IntMap.emptynonempty-containersO(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See  for a version that can guaruntee that we return a non-empty map. updateMin (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "Xb"), (5, "a")] updateMin (\ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"nonempty-containersO(1). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty.nonempty-containersO(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See 0 for a version that guaruntees a non-empty map. updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")] updateMinWithKey (\ _ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"nonempty-containersO(1). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty. Note that it also is able to have better asymptotics than  in general.nonempty-containersO(log n). Update the value at the maximal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See  for a version that can guarantee that we return a non-empty map. updateMax (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3, "b"), (5, "Xa")] updateMax (\ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 3 "b"nonempty-containersO(log n). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty.nonempty-containersO(log n). Update the value at the maximal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See / for a version that guaruntees a non-empty map. updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.fromList [(3,"3:b"), (5,"a")] updateMinWithKey (\ _ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a"nonempty-containersO(log n). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty.nonempty-containersO(1). Retrieves the value associated with minimal key of the map, and the map stripped of that element. It is constant-time, so has better asymptotics than Data.IntMap.minView for .Note that unlike Data.IntMap.minView for 9, this cannot ever fail, so doesn't need to return in a . However, the result  is potentially empty, since the original map might have contained just a single item. minView (fromList ((5,"a") :| [(3,"b")])) == ("b", Data.IntMap.singleton 5 "a")nonempty-containersO(1). Delete and find the minimal key-value pair. It is constant-time, so has better asymptotics that Data.IntMap.minView for .Note that unlike Data.IntMap.deleteFindMin for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original map might have contained just a single item. deleteFindMin (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((3,"b"), Data.IntMap.fromList [(5,"a"), (10,"c")])nonempty-containersO(log n). Retrieves the value associated with maximal key of the map, and the map stripped of that element.Note that unlike Data.IntMap.maxView from 9, this cannot ever fail, so doesn't need to return in a . However, the result  is potentially empty, since the original map might have contained just a single item. maxView (fromList ((5,"a") :| [(3,"b")])) == ("a", Data.IntMap.singleton 3 "b")nonempty-containersO(log n)-. Delete and find the minimal key-value pair.Note that unlike Data.IntMap.deleteFindMax for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original map might have contained just a single item. deleteFindMax (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((10,"c"), Data.IntMap.fromList [(3,"b"), (5,"a")]) }~~}   9 9 (c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&3e nonempty-containers,A non-empty (by construction) map from keys k to values a-. At least one key-value pair exists in an  k v at all times.Functions that take an  can safely operate on it with the assumption that it has at least one key-value pair.Functions that return an  provide an assurance that the result has at least one key-value pair.Data.Map.NonEmpty re-exports the API of Data.Map, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output maps are both non-empty (like   ) return , but functions that might potentially return an empty map (like   ) return a  instead.You can directly construct an  with the API from Data.Map.NonEmpty7; it's more or less the same as constructing a normal ", except you don't have access to 1.. There are also a few ways to construct an  from a : The " smart constructor will convert a  k a into a  ( k a) , returning  if the original  was empty.You can use the 23 family of functions to insert a value into a  to create a guaranteed .You can use the  and " patterns to "pattern match" on a * to reveal it as either containing a  or an empty map. offers a continuation-based interface for deconstructing a " and treating it as if it were an .You can convert an  into a  with  or , essentially "obscuring" the non-empty property from the type.nonempty-containers3invariant: must be smaller than smallest key in mapnonempty-containersO(n). Fold the values in the map using the given right-associative binary operator, such that  f z ==  f z . .  elemsList map = foldr (:) [] map let f a len = len + (length a) foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4nonempty-containersO(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.nonempty-containersO(n). A version of  that uses the value at the maximal key in the map as the starting value.Note that, unlike  for 9, this function is total if the input function is total.nonempty-containersO(n). Fold the values in the map using the given left-associative binary operator, such that  f z ==  f z . . )elemsList = reverse . foldl (flip (:)) [] let f len a = len + (length a) foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4nonempty-containersO(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.nonempty-containersO(n). A version of  that uses the value at the minimal key in the map as the starting value.Note that, unlike  for 9, this function is total if the input function is total.nonempty-containersO(n). Fold the keys and values in the map using the given semigroup, such that  f =  .  f+This can be an asymptotically faster than  or  for some monoids.nonempty-containersO(n),. Map a function over all values in the map. map (++ "x") (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "bx") :| [(5, "ax")])nonempty-containersO(m*log(n/m + 1)), m <= n. The expression ( t1 t2!) takes the left-biased union of t1 and t2 . It prefers t1- when duplicate keys are encountered, i.e. ( ==  ). union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")])nonempty-containers2The left-biased union of a non-empty list of maps. unions (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])]) == fromList [(3, "b"), (5, "a"), (7, "C")] unions (fromList ((5, "A3") :| [(3, "B3")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "a") :| [(3, "b")])]) == fromList ((3, "B3") :| [(5, "A3"), (7, "C")])nonempty-containersO(n). Return all elements of the map in the ascending order of their keys. 9elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])nonempty-containersO(1). The number of elements in the map. Guaranteed to be greater than zero. size (singleton 1 'a') == 1 size (fromList ((1,'a') :| [(2,'c'), (3,'b')])) == 3nonempty-containersO(log n). Convert a non-empty map back into a normal possibly-empty map, for usage with functions that expect .Can be thought of as "obscuring" the non-emptiness of the map in its type. See the  pattern. and  1  form an isomorphism: they are perfect structure-preserving inverses of eachother. toMap (fromList ((3,"a") :| [(5,"b")])) == Data.Map.fromList [(3,"a"), (5,"b")]nonempty-containersO(n).  f m ==   $  ((k, v) -> (,) k  $ f k v) ( m)* That is, behaves exactly like a regular  except that the traversing function also has access to the key associated with a value.Use  whenever possible (if your  also has  instance). This version is provided only for types that do not have  instance, since  is not at the moment (and might not ever be) an official superclass of .  f =  .  (\k -> WrapApplicative . f k) nonempty-containersO(n).  f m ==   $  ((k, v) -> (,) k  $ f k v) ( m)(That is, behaves exactly like a regular  except that the traversing function also has access to the key associated with a value.Is more general than , since works with all , and not just .nonempty-containersO(n)9. Convert the map to a non-empty list of key/value pairs. toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])nonempty-containersO(log n). Smart constructor for an  from a  . Returns  if the $ was originally actually empty, and  n with an  , if the  was not empty. and  1  form an isomorphism: they are perfect structure-preserving inverses of eachother.See  for a pattern synonym that lets you "match on" the possiblity of a  being an . nonEmptyMap (Data.Map.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")]))nonempty-containersO(log n)0. A general continuation-based way to consume a  as if it were an .  def f will take a ). If map is empty, it will evaluate to def. Otherwise, a non-empty map  will be fed to the function f instead.  ==   nonempty-containers O(n*log n). Build a non-empty map from a non-empty list of key/value pairs. See also . If the list contains more than one value for the same key, the last value for the key is retained. fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")]) fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")])nonempty-containersO(1). A map with a single element. singleton 1 'a' == fromList ((1, 'a') :| []) size (singleton 1 'a') == 1nonempty-containersO(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).See 3. for a version where the first argument is a . 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")])nonempty-containersO(n).. Test if the internal map structure is valid.nonempty-containersO(log n)6. Insert new key and value into a map where keys are strictly greater than- the new key. That is, the new key must be strictly less than all keys present in the &. /The precondition is not checked./'While this has the same asymptotics as Data.Map.insert, it saves a constant factor for key comparison (so may be helpful if comparison is expensive) and also does not require an  instance for the key type.nonempty-containersO(log n)6. Insert new key and value into a map where keys are strictly less than- the new key. That is, the new key must be strictly greater than all keys present in the &. /The precondition is not checked./'While this has the same asymptotics as Data.Map.insert, it saves a constant factor for key comparison (so may be helpful if comparison is expensive) and also does not require an  instance for the key type.nonempty-containers( gets the value at the minimal key, and  produces a map of maps comprised of all keys from the original map greater than or equal to the current key.nonempty-containers-Traverses elements in order of ascending keysnonempty-containers-Traverses elements in order of ascending keysnonempty-containers-Traverses elements in order of ascending keysnonempty-containers-Traverses elements in order of ascending keys, , $, % are all total.nonempty-containersLeft-biased unionnonempty-containersvalue to return if map is emptynonempty-containers%function to apply if map is not empty (c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone &3567Mnonempty-containersA general-purpose non-empty (by construction) finite sequence type.Non-emptiness means that:Functions that take an  can safely operate on it with the assumption that it has at least value.Functions that return an  provide an assurance that the result has at least one value.Data.Sequence.NonEmpty re-exports the API of  Data.Sequence, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output maps are both non-empty (like 4 ) return , but functions that might potentially return an empty map (like 5 ) return a  instead.You can directly construct an  with the API from Data.Sequence.NonEmpty7; it's more or less the same as constructing a normal ", except you don't have access to 6.. There are also a few ways to construct an  from a : The 7' smart constructor will convert a  a into a  ( a) , returning  if the original  was empty. You can use 8, 9 , and : to insert a value into a  to create a guaranteed .You can use the  and ' patterns to "pattern match" on a % to reveal it as either containing a  or an empty sequence.; offers a continuation-based interface for deconstructing a ' and treating it as if it were an .You can convert an  into a  with  or , essentially "obscuring" the non-empty property from the type.nonempty-containersO(1)!. An abstract constructor for an  that consists of a "init"  a and a "last" a. Similar to  for :, but at the end of the list instead of at the beginning.0Can be used to match on the init and last of an , and also used to  construct an $ by snocing an item to the end of a ), ensuring that the result is non-empty.nonempty-containersO(1)!. An abstract constructor for an  that consists of a "head" a and a "tail"  a. Similar to  for .0Can be used to match on the head and tail of an , and also used to  construct an + by consing an item to the beginnong of a (, ensuring that the result is non-empty.nonempty-containersO(log n)0. A general continuation-based way to consume a  as if it were an .  def f will take a ). If map is empty, it will evaluate to def. Otherwise, a non-empty map  will be fed to the function f instead. 7 ==   nonempty-containersO(1). Convert a non-empty sequence back into a normal possibly-empty sequence, for usage with functions that expect .Can be thought of as "obscuring" the non-emptiness of the map in its type. See the  pattern.7 and  6  form an isomorphism: they are perfect structure-preserving inverses of eachother.nonempty-containers O(1) . A singleton sequence.nonempty-containers O(1) ). The number of elements in the sequence.nonempty-containers O(n) . Create a sequence from a finite list of elements. There is a function 5 in the opposite direction for all instances of the  class, including .nonempty-containers O(n) . Convert a given sequence length and a function representing that sequence into a sequence.nonempty-containers O(\log n) .  replicate n x is a sequence consisting of n copies of x. Is only defined when n is positive.nonempty-containers O(\log(\min(i,n-i))) . The element at the specified position, counting from 0. The argument should thus be a non-negative integer less than the size of the sequence. If the position is out of range,  fails with an error.xs `index` i = toList xs !! i Caution:  necessarily delays retrieving the requested element until the result is forced. It can therefore lead to a space leak if the result is stored, unforced, in another structure. To retrieve an element immediately without forcing it, use  or (!?).nonempty-containers O(1) . Add an element to the left end of a non-empty sequence. Mnemonic: a triangle with the single element at the pointy end.nonempty-containers O(\log(\min(n_1,n_2))) &. Concatenate two non-empty sequences.nonempty-containers O(\log(\min(n_1,n_2))) . Concatenate a non-empty sequence with a potentially empty sequence (), to produce a guaranteed non-empty sequence. Mnemonic: like 0, but a pipe for the guarunteed non-empty side.nonempty-containers.nonempty-containersCompatibility layer for =?.nonempty-containersCompatibility layer for =@.nonempty-containersCompatibility layer for =<.nonempty-containers mzipWith = zipWith munzip = unzipnonempty-containers, , , and  are all total, unlike for .5555555(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&Ζnonempty-containersO(1). The  and  patterns allow you to treat a  as if it were either a  n (where n is a ) or an . Matching on  means that the original  was empty.A case statement handling both  and  provides complete coverage.0This is a bidirectional pattern, so you can use 2 as an expression, and it will be interpreted as 6.See  for more information.nonempty-containersO(1). The  and  patterns allow you to treat a  as if it were either a  n (where n is a  ) or an .(For example, you can pattern match on a :  safeHead ::  Int -> Int safeHead ( (x :<|| _)) = x -- here, user provided a non-empty sequence, and n is the  safeHead  = 0 -- here the user provided an empty sequence  Matching on  n means that the original  was not+ empty, and you have a verified-non-empty  n to use.A case statement handling both  and  provides complete coverage.0This is a bidirectional pattern, so you can use  to convert a  back into a #, obscuring its non-emptiness (see ).nonempty-containersO(1). Smart constructor for an  from a  . Returns  if the $ was originally actually empty, and  n with an  , if the  was not empty. and  =  form an isomorphism: they are perfect structure-preserving inverses of eachother.See  for a pattern synonym that lets you "match on" the possiblity of a  being an . nonEmptySeq (Data.Sequence.fromList [1,2,3]) == Just (fromList (1) :| [2,3])nonempty-containersO(1). Unsafe version of  . Coerces a  into an , but is undefined (throws a runtime exception when evaluation is attempted) for an empty .nonempty-containersTurn a  into a guarantted non-empty ( by adding an element at a given index. insertSeqAt 1 0 (Data.Sequence.fromList [1,2,3]) == fromList (1 :| [0,2,3])nonempty-containers O(1) . Add an element to the right end of a non-empty sequence. Mnemonic: a triangle with the single element at the pointy end.nonempty-containers O(\log(\min(n_1,n_2))) . Concatenate a non-empty sequence with a potentially empty sequence (), to produce a guaranteed non-empty sequence. Mnemonic: like 0, but a pipe for the guarunteed non-empty side.nonempty-containers is an  version of #, and makes ( O(log n) ) calls to  and . Is only defined when n is positive. *replicateA n x = sequenceA (replicate n x)!Is a more restrictive version of . ( should be preferred whenever possible.nonempty-containers is an  version of #, and makes ( O(log n) ) calls to . Is only defined when n is positive. +replicateA1 n x = sequence1 (replicate n x)nonempty-containers An alias of .nonempty-containersO(log k).  k xs forms a sequence of length k by repeatedly concatenating xs# with itself. Is only defined when k is positive.cycleTaking k = fromList . fromJust . nonEmpty . take k . cycle . toListnonempty-containers O(n) . Constructs a sequence by repeated application of a function to a seed value. Is only defined if given a positive value. iterateN n f x = fromList (fromJust (nonEmpty ((Prelude.take n (Prelude.iterate f x)))))nonempty-containersBuilds a sequence from a seed value. Takes time linear in the number of generated elements. WARNING: If the number of generated elements is infinite, this method will not terminate.nonempty-containers f x is equivalent to  ( ( swap . f) x).nonempty-containersO(1). Retrieve the left-most item in a non-empty sequence. Note that this function is total.nonempty-containersO(1). Delete the left-most item in a non-empty sequence. Returns a potentially empty sequence (!) in the case that the original  contained only a single element. Note that this function is total.nonempty-containersO(1). Retrieve the right-most item in a non-empty sequence. Note that this function is total.nonempty-containersO(1). Delete the right-most item in a non-empty sequence. Returns a potentially empty sequence (!) in the case that the original  contained only a single element. Note that this function is total.nonempty-containers is similar to :, but returns a sequence of reduced values from the left: scanl f z (fromList [x1, x2, ...]) = fromList [z, z `f` x1, (z `f` x1) `f` x2, ...]nonempty-containers is a variant of % that has no starting value argument: scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]nonempty-containers is the right-to-left dual of .nonempty-containers is a variant of % that has no starting value argument.nonempty-containers O(n) . Returns a sequence of all non-empty prefixes of this sequence, shortest first. For example, tails (fromList (1:|[2,3])) = fromList (fromList (1:|[]) :| [fromList (1:|[2]), fromList (1:|[2,3]))Evaluating the  i th prefix takes  O(\log(\min(i, n-i))) 5, but evaluating every prefix in the sequence takes  O(n)  due to sharing.nonempty-containers,O \Bigl(\bigl(\frac{n}{c}\bigr) \log c\Bigr).  chunksOf c xs splits xs into chunks of size c>0. If c does not divide the length of xs evenly, then the last element of the result will be short. Is only defined if c is a positive number.Side note: the given performance bound is missing some messy terms that only really affect edge cases. Performance degrades smoothly from  O(1)  (for  c = n ) to  O(n)  (for  c = 1  ). The true bound is more like  O \Bigl( \bigl(\frac{n}{c} - 1\bigr) (\log (c + 1)) + 1 \Bigr) nonempty-containers O(i)  where  i  is the prefix length. , applied to a predicate p and a sequence xs2, returns the longest prefix (possibly empty) of xs of elements that satisfy p.#Returns a possibly empty sequence (:) in the case that the predicate fails on the first item.nonempty-containers O(i)  where  i  is the suffix length. , applied to a predicate p and a sequence xs2, returns the longest suffix (possibly empty) of xs of elements that satisfy p.#Returns a possibly empty sequence (:) in the case that the predicate fails on the first item. p xs is equivalent to  ( p ( xs)).nonempty-containers O(i)  where  i  is the prefix length.  p xs% returns the suffix remaining after  p xs.#Returns a possibly empty sequence (7) in the case that the predicate passes for all items.nonempty-containers O(i)  where  i  is the suffix length.  p xs% returns the prefix remaining after  p xs.#Returns a possibly empty sequence (7) in the case that the predicate passes for all items. p xs is equivalent to  ( p ( xs)).nonempty-containers O(i)  where  i  is the prefix length. , applied to a predicate p and a sequence xs , returns a / based on the point where the predicate fails: ys; means that the predicate was true for all items, and ys! is the entire original sequence. zs= means that the predicate failed on the first item, and zs! is the entire original sequence. ys zs gives ys= (the prefix of elements that satisfy the predicae) and zs (the remainder of the sequence)nonempty-containers O(i)  where  i  is the suffix length. , applied to a predicate p and a sequence xs , returns a / based on the point where the predicate fails: ys; means that the predicate was true for all items, and ys! is the entire original sequence. zs= means that the predicate failed on the first item, and zs! is the entire original sequence. ys zs gives ys= (the suffix of elements that satisfy the predicae) and zs3 (the remainder of the sequence, before the suffix)nonempty-containers O(i)  where  i  is the breakpoint index. p is  (not . p).nonempty-containers O(i)  where  i  is the breakpoint index. p is  (not . p).nonempty-containers O(n) . The  function takes a predicate p and a sequence xs and returns sequences of those elements which do and do not satisfy the predicate, as a : ys; means that the predicate was true for all items, and ys! is the entire original sequence. zs= means that the predicate failed on the first item, and zs! is the entire original sequence. ys zs gives ys (the sequence of elements for which the predicate was true) and zs (the sequence of elements for which the predicate was false).nonempty-containers O(n) . The  function takes a predicate p and a sequence xs and returns a sequence of those elements which satisfy the predicate.&Returns a potentially empty sequence () in the case that the predicate fails for all items in the sequence.nonempty-containers O(n \log n) .  sorts the specified  by the natural ordering of its elements. The sort is stable. If stability is not required,  can be slightly faster.nonempty-containers O(n \log n) .  sorts the specified  according to the specified comparator. The sort is stable. If stability is not required,  can be slightly faster.nonempty-containers O(n \log n) .  sorts the specified  by comparing the results of a key function applied to each element.  f is equivalent to  ( AB f)8, but has the performance advantage of only evaluating f once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.An example of using  might be to sort a ' of strings according to their length: sortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator"]) If, instead,  had been used, 1 would be evaluated on every comparison, giving  O(n \log n)  evaluations, rather than  O(n) .If f2 is very cheap (for example a record selector, or ),  ( AB f) will be faster than  f.nonempty-containers O(n \log n) .  sorts the specified  by the natural ordering of its elements, but the sort is not stable. This algorithm is frequently faster and uses less memory than .nonempty-containers O(n \log n) . A generalization of ,  takes an arbitrary comparator and sorts the specified sequence. The sort is not stable. This algorithm is frequently faster and uses less memory than .nonempty-containers O(n \log n) .  sorts the specified  by comparing the results of a key function applied to each element.  f is equivalent to  ( AB f)8, but has the performance advantage of only evaluating f once for each element in the input list. This is called the decorate-sort-undecorate paradigm, or Schwartzian transform.An example of using  might be to sort a ' of strings according to their length. unstableSortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator]") If, instead,  had been used, 1 would be evaluated on every comparison, giving  O(n \log n)  evaluations, rather than  O(n) .If f2 is very cheap (for example a record selector, or ),  ( AB f) will be faster than  f.nonempty-containers O(\log(\min(i,n-i))) . The element at the specified position, counting from 0. If the specified position is negative or at least the length of the sequence,  returns .Unlike >, this can be used to retrieve an element without forcing it.nonempty-containers O(\log(\min(i,n-i))) . A flipped, infix version of .nonempty-containers O(\log(\min(i,n-i))) . Update the element at the specified position. If the position is out of range, the original sequence is returned.  can lead to poor performance and even memory leaks, because it does not force the new value before installing it in the sequence.  should usually be preferred.nonempty-containers O(\log(\min(i,n-i))) . Update the element at the specified position. If the position is out of range, the original sequence is returned. The new value is forced before it is installed in the sequence. adjust' f i xs = case xs !? i of Nothing -> xs Just x -> let !x' = f x in update i x' xs nonempty-containers O(\log(\min(i,n-i))) . Replace the element at the specified position. If the position is out of range, the original sequence is returned.nonempty-containers O(\log(\min(i,n-i)))  . The first i elements of a sequence. If i is negative,  i s yields the empty sequence. If the sequence contains fewer than i+ elements, the whole sequence is returned.nonempty-containers O(\log(\min(i,n-i))) ). Elements of a sequence after the first i. If i is negative,  i s yields the whole sequence. If the sequence contains fewer than i+ elements, the empty sequence is returned.nonempty-containers O(\log(\min(i,n-i))) .  i x xs inserts x into xs at the index i), shifting the rest of the sequence over. insertAt 2 x (fromList (a:|[b,c,d])) = fromList (a:|[b,x,c,d]) insertAt 4 x (fromList (a:|[b,c,d])) = insertAt 10 x (fromList (a:|[b,c,d])) = fromList (a:|[b,c,d,x]) 7insertAt i x xs = take i xs >< singleton x >< drop i xsnonempty-containers O(\log(\min(i,n-i))) . Delete the element of a sequence at a given index. Return the original sequence if the index is out of range. deleteAt 2 (a:|[b,c,d]) = a:|[b,d] deleteAt 4 (a:|[b,c,d]) = deleteAt (-1) (a:|[b,c,d]) = a:|[b,c,d] nonempty-containers O(\log(\min(i,n-i))) '. Split a sequence at a given position. ys means that the given position was longer than the length of the list, and ys is the entire original system. zs means that the given position was zero or smaller, and so zs! is the entire original sequence. ys zs gives ys; (the sequence of elements before the given position,  take n xs) and zs: (the sequence of elements after the given position,  drop n xs).nonempty-containers finds the leftmost index of the specified element, if it is present, and otherwise .nonempty-containers finds the rightmost index of the specified element, if it is present, and otherwise .nonempty-containers finds the indices of the specified element, from left to right (i.e. in ascending order).nonempty-containers finds the indices of the specified element, from right to left (i.e. in descending order).nonempty-containers p xs9 finds the index of the leftmost element that satisfies p, if any exist.nonempty-containers p xs: finds the index of the rightmost element that satisfies p, if any exist.nonempty-containers p, finds all indices of elements that satisfy p, in ascending order.nonempty-containers p, finds all indices of elements that satisfy p, in descending order.nonempty-containers is a version of 9 that also provides access to the index of each element.nonempty-containers is a version of 9 that also provides access to the index of each element.nonempty-containersA generalization of ,  takes a mapping function that also depends on the element's index, and applies it to every element in the sequence.nonempty-containers is a version of 7 that also offers access to the index of each element.!Is a more restrictive version of ; " should be used whenever possible.nonempty-containers O(n) . The reverse of a sequence.nonempty-containers O(n) <. Intersperse an element between the elements of a sequence. intersperse a empty = empty intersperse a (singleton x) = singleton x intersperse a (fromList [x,y]) = fromList [x,a,y] intersperse a (fromList [x,y,z]) = fromList [x,a,y,a,z] nonempty-containers O(\min(n_1,n_2,n_3)) .  takes three sequences and returns a sequence of triples, analogous to .nonempty-containers O(\min(n_1,n_2,n_3)) .  takes a function which combines three elements, as well as three sequences and returns a sequence of their point-wise combinations, analogous to .nonempty-containers O(\min(n_1,n_2,n_3,n_4)) .  takes four sequences and returns a sequence of quadruples, analogous to .nonempty-containers O(\min(n_1,n_2,n_3,n_4)) .  takes a function which combines four elements, as well as four sequences and returns a sequence of their point-wise combinations, analogous to .nonempty-containers O(n) 7. Unzip a sequence using a function to divide elements.  unzipWith f xs ==  ( f xs)Efficiency note: unzipWith9 produces its two results in lockstep. If you calculate  unzipWith f xs  and fully force either3 of the results, then the entire structure of the other one will be built as well. This behavior allows the garbage collector to collect each calculated pair component as soon as it dies, without having to wait for its mate to die. If you do not need this behavior, you may be better off simply calculating the sequence of pairs and using % to extract each component sequence.55 (c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&3nonempty-containers Used for Cnonempty-containers,A non-empty (by construction) set of values a$. At least one value exists in an  a at all times.Functions that take an  can safely operate on it with the assumption that it has at least one item.Functions that return an = provide an assurance that the result has at least one item.Data.Set.NonEmpty re-exports the API of Data.Set, faithfully reproducing asymptotics, typeclass constraints, and semantics. Functions that ensure that input and output sets are both non-empty (like   ) return , but functions that might potentially return an empty map (like   ) return a  instead.You can directly construct an  with the API from Data.Set.NonEmpty7; it's more or less the same as constructing a normal ", except you don't have access to ,.. There are also a few ways to construct an  from a : The " smart constructor will convert a  a into a  ( a) , returning  if the original  was empty.You can use the D3 family of functions to insert a value into a  to create a guaranteed .You can use the  and " patterns to "pattern match" on a * to reveal it as either containing a  or an empty map. offers a continuation-based interface for deconstructing a " and treating it as if it were an .You can convert an  into a  with  or , essentially "obscuring" the non-empty property from the type.nonempty-containers5invariant: must be smaller than smallest value in setnonempty-containersO(log n). Smart constructor for an  from a  . Returns  if the $ was originally actually empty, and  n with an  , if the  was not empty. and  ,  form an isomorphism: they are perfect structure-preserving inverses of eachother.See  for a pattern synonym that lets you "match on" the possiblity of a  being an . nonEmptySet (Data.Set.fromList [3,5]) == Just (fromList (3:|[5]))nonempty-containersO(log n)0. A general continuation-based way to consume a  as if it were an .  def f will take a ). If set is empty, it will evaluate to def. Otherwise, a non-empty set  will be fed to the function f instead.  ==   nonempty-containersO(log n). Convert a non-empty set back into a normal possibly-empty map, for usage with functions that expect .Can be thought of as "obscuring" the non-emptiness of the set in its type. See the  pattern. and  ,  form an isomorphism: they are perfect structure-preserving inverses of eachother. toSet (fromList ((3,"a") :| [(5,"b")])) == Data.Set.fromList [(3,"a"), (5,"b")]nonempty-containersO(1). Create a singleton set.nonempty-containers O(n*log n)'. Create a set from a list of elements.nonempty-containersO(n)2. Convert the set to a non-empty list of elements.nonempty-containersO(1). The number of elements in the set. Guaranteed to be greater than zero.nonempty-containersO(n). Fold the elements in the set using the given right-associative binary operator, such that  f z ==  f z . E. For example,  elemsList set = foldr (:) [] setnonempty-containersO(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.nonempty-containersO(n). Fold the elements in the set using the given left-associative binary operator, such that  f z ==  f z . E. For example, +descElemsList set = foldl (flip (:)) [] setnonempty-containersO(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.nonempty-containersO(m*log(n/m + 1)), m <= n. The union of two sets, preferring the first set when equal elements are encountered.nonempty-containers%The union of a non-empty list of setsnonempty-containersUnsafely merge two disjoint sets. Only legal if all items in the first set are less than all items in the second setnonempty-containersO(n).. Test if the internal set structure is valid.nonempty-containersO(log n)0. Insert new value into a set where values are strictly greater than1 the new values That is, the new value must be strictly less than all values present in the &. /The precondition is not checked./'While this has the same asymptotics as Data.Set.insert, it saves a constant factor for value comparison (so may be helpful if comparison is expensive) and also does not require an  instance for the value type.nonempty-containersO(log n). Insert new value into a set where values are /strictly less than0 the new value. That is, the new value must be strictly greater than all values present in the . "The precondition is not checked./'While this has the same asymptotics as Data.Set.insert, it saves a constant factor for value comparison (so may be helpful if comparison is expensive) and also does not require an  instance for the value type.nonempty-containersCPP for new functions not in old containers ---------------------------------------------Comptability layer for ,(.nonempty-containersComptability layer for ,F.nonempty-containersComptability layer for ,G.nonempty-containersComptability layer for ,C.nonempty-containers%Traverses elements in ascending ordernonempty-containers%Traverses elements in ascending order, , $, % are all total.nonempty-containersLeft-biased unionnonempty-containersvalue to return if set is emptynonempty-containers%function to apply if set is not empty(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&77nonempty-containersO(1). The  and  patterns allow you to treat a  as if it were either a  n (where n is a ) or an . Matching on  means that the original  was empty.A case statement handling both  and  provides complete coverage.0This is a bidirectional pattern, so you can use 2 as an expression, and it will be interpreted as ,.See  for more information.nonempty-containersO(1) match, O(log n) usage of contents. The  and  patterns allow you to treat a  as if it were either a  n (where n is a ) or an .(For example, you can pattern match on a :  myFunc ::  X -> Y myFunc (7 n) = -- here, the user provided a non-empty set, and n is the  myFunc 3 = -- here, the user provided an empty set  Matching on  n means that the original  was not+ empty, and you have a verified-non-empty  n to use.&Note that patching on this pattern is O(1)+. However, using the contents requires a O(log n) cost that is deferred until after the pattern is matched on (and is not incurred at all if the contents are never used).A case statement handling both  and  provides complete coverage.0This is a bidirectional pattern, so you can use  to convert a  back into a #, obscuring its non-emptiness (see ).nonempty-containersO(log n). Unsafe version of  . Coerces a  into an , but is undefined (throws a runtime exception when evaluation is attempted) for an empty .nonempty-containersO(log n) . Convert a  into an  by adding a value. Because of this, we know that the set must have at least one element, and so therefore cannot be empty.See : for a version that is constant-time if the new value is strictly smaller than all values in the original set insertSet 4 (Data.Set.fromList [5, 3]) == fromList (3 :| [4, 5]) insertSet 4 Data.Set.empty == singleton 4 "c"nonempty-containersO(1) Convert a  into an ' by adding a value where the value is strictly less than all values in the input set The values in the original map must all be strictly greater than the new value.  The precondition is not checked. insertSetMin 2 (Data.Set.fromList [5, 3]) == fromList (2 :| [3, 5]) valid (insertSetMin 2 (Data.Set.fromList [5, 3])) == True valid (insertSetMin 7 (Data.Set.fromList [5, 3])) == False valid (insertSetMin 3 (Data.Set.fromList [5, 3])) == Falsenonempty-containersO(log n) Convert a  into an ' by adding a value where the value is strictly less than all values in the input set The values in the original map must all be strictly greater than the new value.  The precondition is not checked.'While this has the same asymptotics as , it saves a constant factor for key comparison (so may be helpful if comparison is expensive) and also does not require an  instance for the key type. insertSetMin 7 (Data.Set.fromList [5, 3]) == fromList (3 :| [5, 7]) valid (insertSetMin 7 (Data.Set.fromList [5, 3])) == True valid (insertSetMin 2 (Data.Set.fromList [5, 3])) == False valid (insertSetMin 5 (Data.Set.fromList [5, 3])) == Falsenonempty-containersO(n). Build a set from an ascending list in linear time. /The precondition (input list is ascending) is not checked./nonempty-containersO(n). Build a set from an ascending list of distinct elements in linear time. The precondition (input list is strictly ascending) is not checked.nonempty-containersO(n)6. Build a set from a descending list in linear time. ;The precondition (input list is descending) is not checked.nonempty-containersO(n). Build a set from a descending list of distinct elements in linear time. The precondition (input list is strictly descending) is not checked.nonempty-containersCalculate the power set of a non-empty: the set of all its (non-empty) subsets. t  powerSet s == t  s Example: powerSet (fromList (1 :| [2,3])) = fromList (singleton 1 :| [ singleton 2 , singleton 3 , fromList (1 :| [2]) , fromList (1 :| [3]) , fromList (2 :| [3]) , fromList (1 :| [2,3]) ] ) We know that the result is non-empty because the result will always at least contain the original set.nonempty-containersO(log n). Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.nonempty-containersO(log n). Delete an element from a set.nonempty-containersO(log n). Is the element in the set?nonempty-containersO(log n) . Is the element not in the set?nonempty-containersO(log n)2. Find largest element smaller than the given one. lookupLT 3 (fromList (3 :| [5])) == Nothing lookupLT 5 (fromList (3 :| [5])) == Just 3nonempty-containersO(log n)3. Find smallest element greater than the given one. lookupLT 4 (fromList (3 :| [5])) == Just 5 lookupLT 5 (fromList (3 :| [5])) == Nothingnonempty-containersO(log n)9. Find largest element smaller or equal to the given one. lookupLT 2 (fromList (3 :| [5])) == Nothing lookupLT 4 (fromList (3 :| [5])) == Just 3 lookupLT 5 (fromList (3 :| [5])) == Just 5nonempty-containersO(log n):. Find smallest element greater or equal to the given one. lookupLT 3 (fromList (3 :| [5])) == Just 3 lookupLT 4 (fromList (3 :| [5])) == Just 5 lookupLT 6 (fromList (3 :| [5])) == Nothingnonempty-containersO(n+m). Is this a subset? (s1 `isSubsetOf` s2) tells whether s1 is a subset of s2.nonempty-containersO(n+m)8. Is this a proper subset? (ie. a subset but not equal).nonempty-containersO(n+m). Check whether two sets are disjoint (i.e. their intersection is empty). disjoint (fromList (2:|[4,6])) (fromList (1:|[3])) == True disjoint (fromList (2:|[4,6,8])) (fromList (2:|[3,5,7])) == False disjoint (fromList (1:|[2])) (fromList (1:|[2,3,4])) == Falsenonempty-containersO(m*log(n/m + 1)), m <= n. Difference of two sets.!Returns a potentially empty set () because the first set might be a subset of the second set, and therefore have all of its elements removed.nonempty-containersSame as .nonempty-containersO(m*log(n/m + 1)), m <= n. The intersection of two sets.!Returns a potentially empty set (:), because the two sets might have an empty intersection.>Elements of the result come from the first set, so for example import qualified Data.Set.NonEmpty as NES data AB = A | B deriving Show instance Ord AB where compare _ _ = EQ instance Eq AB where _ == _ = True main = print (NES.singleton A `NES.intersection` NES.singleton B, NES.singleton B `NES.intersection` NES.singleton A)prints #(fromList (A:|[]),fromList (B:|[])).nonempty-containers,Calculate the Cartesian product of two sets. cartesianProduct xs ys = fromList $ liftA2 (,) (toList xs) (toList ys) Example: cartesianProduct (fromList (1:|[2])) (fromList ('a':|['b'])) = fromList ((1,'a') :| [(1,'b'), (2,'a'), (2,'b')]) nonempty-containers)Calculate the disjoint union of two sets. # disjointUnion xs ys = map Left xs  map Right ysExample: disjointUnion (fromList (1:|[2])) (fromList ("hi":|["bye"])) = fromList (Left 1 :| [Left 2, Right "hi", Right "bye"]) nonempty-containersO(n)1. Filter all elements that satisfy the predicate.!Returns a potentially empty set () because the predicate might filter out all items in the original non-empty set.nonempty-containersO(log n). Take while a predicate on the elements holds. The user is responsible for ensuring that for all elements j and k in the set, j < k ==> p j >= p k. See note at .!Returns a potentially empty set (7) because the predicate might fail on the first input. takeWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.takeWhile p .  takeWhileAntitone p =  p nonempty-containersO(log n). Drop while a predicate on the elements holds. The user is responsible for ensuring that for all elements j and k in the set, j < k ==> p j >= p k. See note at .!Returns a potentially empty set (5) because the predicate might be true for all items. dropWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.dropWhile p .  dropWhileAntitone p =  (not . p) nonempty-containersO(log n). Divide a set at the point where a predicate on the elements stops holding. The user is responsible for ensuring that for all elements j and k in the set, j < k ==> p j >= p k. Returns a % with potentially two non-empty sets: n1 means that the predicate never failed for any item, returning the original set n2 means that the predicate failed for the first item, returning the original set n1 n2 gives n1 (the set up to the point where the predicate stops holding) and n2 (the set starting from the point where the predicate stops holding) #spanAntitone p xs = partition p xs  Note: if p is not actually antitone, then  spanAntitone will split the set at some  unspecified point where the predicate switches from holding to not holding (where the predicate is seen to hold before the first element and to fail after the last element).nonempty-containersO(n)-. Partition the map according to a predicate. Returns a % with potentially two non-empty sets: n11 means that the predicate was true for all items. n22 means that the predicate was false for all items. n1 n2 gives n1> (all of the items that were true for the predicate) and n2; (all of the items that were false for the predicate). See also . partition (> 3) (fromList (5 :| [3])) == These (singleton 5) (singleton 3) partition (< 7) (fromList (5 :| [3])) == This (fromList (3 :| [5])) partition (> 7) (fromList (5 :| [3])) == That (fromList (3 :| [5]))nonempty-containersO(log n). The expression ( x set) is potentially a  containing up to two s based on splitting the set into sets containing items before and after the value x-. It will never return a set that contains x itself. means that x was the only value in the the original set, and so there are no items before or after it. ( n1) means x< was larger than or equal to all items in the set, and n1# is the entire original set (minus x, if it was present) ( n2) means x= was smaller than or equal to all items in the set, and n2# is the entire original set (minus x, if it was present) ( n1 n2) gives n1= (the set of all values from the original set less than x) and n2 (the set of all values from the original set greater than x). split 2 (fromList (5 :| [3])) == Just (That (fromList (3 :| [5])) ) split 3 (fromList (5 :| [3])) == Just (That (singleton 5) ) split 4 (fromList (5 :| [3])) == Just (These (singleton 3) (singleton 5)) split 5 (fromList (5 :| [3])) == Just (This (singleton 3) ) split 6 (fromList (5 :| [3])) == Just (This (fromList (3 :| [5])) ) split 5 (singleton 5) == Nothingnonempty-containersO(log n). The expression ( x set) splits a set just like  but also returns  x set (whether or not x was in set) splitMember 2 (fromList (5 :| [3])) == (False, Just (That (fromList (3 :| [5)])))) splitMember 3 (fromList (5 :| [3])) == (True , Just (That (singleton 5))) splitMember 4 (fromList (5 :| [3])) == (False, Just (These (singleton 3) (singleton 5))) splitMember 5 (fromList (5 :| [3])) == (True , Just (This (singleton 3)) splitMember 6 (fromList (5 :| [3])) == (False, Just (This (fromList (3 :| [5]))) splitMember 5 (singleton 5) == (True , Nothing)nonempty-containersO(1). Decompose a set into pieces based on the structure of the underlying tree. This function is useful for consuming a set in parallel.No guarantee is made as to the sizes of the pieces; an internal, but deterministic process determines this. However, it is guaranteed that the pieces returned will be in ascending order (all elements in the first subset less than all elements in the second, and so on).Note that the current implementation does not return more than four subsets, but you should not depend on this behaviour because it can change in the future without notice.nonempty-containersO(log n) . Lookup the index of an element, which is its zero-based index in the sorted sequence of elements. The index is a number from 0 up to, but not including, the  of the set. isJust (lookupIndex 2 (fromList (5:|[3]))) == False fromJust (lookupIndex 3 (fromList (5:|[3]))) == 0 fromJust (lookupIndex 5 (fromList (5:|[3]))) == 1 isJust (lookupIndex 6 (fromList (5:|[3]))) == Falsenonempty-containersO(log n) . Return the index of an element, which is its zero-based index in the sorted sequence of elements. The index is a number from 0 up to, but not including, the  of the set. Calls  when the element is not a  of the set. findIndex 2 (fromList (5:|[3])) Error: element is not in the set findIndex 3 (fromList (5:|[3])) == 0 findIndex 5 (fromList (5:|[3])) == 1 findIndex 6 (fromList (5:|[3])) Error: element is not in the setnonempty-containersO(log n). Retrieve an element by its index, i.e. by its zero-based index in the sorted sequence of elements. If the index7 is out of range (less than zero, greater or equal to  of the set),  is called. elemAt 0 (fromList (5:|[3])) == 3 elemAt 1 (fromList (5:|[3])) == 5 elemAt 2 (fromList (5:|[3])) Error: index out of rangenonempty-containersO(log n). Delete the element at index, i.e. by its zero-based index in the sorted sequence of elements. If the index7 is out of range (less than zero, greater or equal to  of the set),  is called.!Returns a potentially empty set (), because this could potentailly delete the final element in a singleton set. deleteAt 0 (fromList (5:|[3])) == singleton 5 deleteAt 1 (fromList (5:|[3])) == singleton 3 deleteAt 2 (fromList (5:|[3])) Error: index out of range deleteAt (-1) (fromList (5:|[3])) Error: index out of rangenonempty-containersTake a given number of elements in order, beginning with the smallest ones.!Returns a potentailly empty set ('), which can only happen when calling take 0. take n = Data.Set.fromDistinctAscList . Data.List.NonEmpty.take n .  nonempty-containersDrop a given number of elements in order, beginning with the smallest ones.!Returns a potentailly empty set (), in the case that  is called with a number equal to or greater the number of items in the set, and we drop every item. drop n = Data.Set.fromDistinctAscList . Data.List.NonEmpty.drop n .  nonempty-containersO(log n)$. Split a set at a particular index i. n1 means that there are less than i items in the set, and n1 is the original set. n2 means i was 0; we dropped 0 items, so n2 is the original set. n1 n2 gives n1 (taking i' items from the original set) and n2 (dropping i items from the original set))nonempty-containers O(n*log n).  f s! is the set obtained by applying f to each element of s.It's worth noting that the size of the result may be smaller if, for some (x,y), x /= y && f x == f ynonempty-containersO(n).  f s ==  f s, but works only when f is strictly increasing.  The precondition is not checked. Semi-formally, we have: and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapMonotonic f s == map f s where ls = Data.Foldable.toList snonempty-containersO(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.nonempty-containersO(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.nonempty-containersO(1). The minimal element of a set. Note that this is total, making ,) obsolete. It is constant-time, so has better asymptotics than Data.Set.lookupMin and Data.Map.findMin as well. "findMin (fromList (5 :| [3])) == 3nonempty-containersO(log n)=. The maximal key of a set Note that this is total, making ,) obsolete. "findMax (fromList (5 :| [3])) == 5nonempty-containersO(1). Delete the minimal element. Returns a potentially empty set (), because we might delete the final item in a singleton set. It is constant-time, so has better asymptotics than Data.Set.deleteMin. deleteMin (fromList (5 :| [3, 7])) == Data.Set.fromList [5, 7] deleteMin (singleton 5) == Data.Set.emptynonempty-containersO(log n). Delete the maximal element. Returns a potentially empty set (=), because we might delete the final item in a singleton set. deleteMax (fromList (5 :| [3, 7])) == Data.Set.fromList [3, 5] deleteMax (singleton 5) == Data.Set.emptynonempty-containersO(1). Delete and find the minimal element. It is constant-time, so has better asymptotics that Data.Set.minView for .Note that unlike Data.Set.deleteFindMin for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original set might have contained just a single item. deleteFindMin (fromList (5 :| [3, 10])) == (3, Data.Set.fromList [5, 10])nonempty-containersO(log n)&. Delete and find the minimal element.Note that unlike Data.Set.deleteFindMax for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original set might have contained just a single item. deleteFindMax (fromList (5 :| [3, 10])) == (10, Data.Set.fromList [3, 5])nonempty-containersO(n). An alias of ,. The elements of a set in ascending order.nonempty-containersO(n)=. Convert the set to an ascending non-empty list of elements.nonempty-containersO(n)=. Convert the set to a descending non-empty list of elements.(c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&nonempty-containersO(1). The  and  patterns allow you to treat a  as if it were either a  n (where n is a ) or an . Matching on  means that the original  was empty.A case statement handling both  and  provides complete coverage.0This is a bidirectional pattern, so you can use 2 as an expression, and it will be interpreted as 1.See  for more information.nonempty-containersO(1) match, O(log n) usage of contents. The  and  patterns allow you to treat a  as if it were either a  n (where n is a ) or an .(For example, you can pattern match on a :  myFunc ::  K X -> Y myFunc (7 n) = -- here, the user provided a non-empty map, and n is the  myFunc 4 = -- here, the user provided an empty map.  Matching on  n means that the original  was not+ empty, and you have a verified-non-empty  n to use.&Note that patching on this pattern is O(1)+. However, using the contents requires a O(log n) cost that is deferred until after the pattern is matched on (and is not incurred at all if the contents are never used).A case statement handling both  and  provides complete coverage.0This is a bidirectional pattern, so you can use  to convert a  back into a #, obscuring its non-emptiness (see ).nonempty-containersO(log n). Unsafe version of  . Coerces a  into an , but is undefined (throws a runtime exception when evaluation is attempted) for an empty .nonempty-containersO(n). Build a non-empty map from a non-empty set of keys and a function which for each key computes its value. fromSet (\k -> replicate k 'a') (Data.Set.NonEmpty.fromList (3 :| [5])) == fromList ((5,"aaaaa") :| [(3,"aaa")])nonempty-containersO(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.An example of using lookup: import Prelude hiding (lookup) import Data.Map.NonEmpty employeeDept = fromList (("John","Sales") :| [("Bob","IT")]) deptCountry = fromList (("IT","USA") :| [("Sales","France")]) countryCurrency = fromList (("USA", "Dollar") :| [("France", "Euro")]) employeeCurrency :: String -> Maybe String employeeCurrency name = do dept <- lookup name employeeDept country <- lookup dept deptCountry lookup country countryCurrency main = do putStrLn $ "John's currency: " ++ (show (employeeCurrency "John")) putStrLn $ "Pete's currency: " ++ (show (employeeCurrency "Pete"))The output of this program: 9 John's currency: Just "Euro" Pete's currency: Nothingnonempty-containersO(log n)#. Find the value at a key. Returns $ when the element can not be found.1fromList ((5, 'a') :| [(3, 'b')]) !? 1 == Nothing2fromList ((5, 'a') :| [(3, 'b')]) !? 5 == Just 'a'nonempty-containersO(log n)!. Find the value at a key. Calls $ when the element can not be found. fromList ((5,'a') :| [(3,'b')]) ! 1 Error: element not in the map fromList ((5,'a') :| [(3,'b')]) ! 5 == 'a'nonempty-containersO(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' findWithDefault 'x' 5 (fromList ((5,'a') :| [(3,'b')])) == 'a'nonempty-containersO(log n)+. Is the key a member of the map? See also . member 5 (fromList ((5,'a') :| [(3,'b')])) == True member 1 (fromList ((5,'a') :| [(3,'b')])) == Falsenonempty-containersO(log n)/. Is the key not a member of the map? See also . notMember 5 (fromList ((5,'a') :| [(3,'b')])) == False notMember 1 (fromList ((5,'a') :| [(3,'b')])) == Truenonempty-containersO(log n). Find largest key smaller than the given one and return the corresponding (key, value) pair. lookupLT 3 (fromList ((3,'a') :| [(5,'b')])) == Nothing lookupLT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a')nonempty-containersO(log n). Find smallest key greater than the given one and return the corresponding (key, value) pair. lookupGT 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b') lookupGT 5 (fromList ((3,'a') :| [(5,'b')])) == Nothingnonempty-containersO(log n). Find largest key smaller or equal to the given one and return the corresponding (key, value) pair. lookupLE 2 (fromList ((3,'a') :| [(5,'b')])) == Nothing lookupLE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a') lookupLE 5 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b')nonempty-containersO(log n). Find smallest key greater or equal to the given one and return the corresponding (key, value) pair. lookupGE 3 (fromList ((3,'a') :| [(5,'b')])) == Just (3, 'a') lookupGE 4 (fromList ((3,'a') :| [(5,'b')])) == Just (5, 'b') lookupGE 6 (fromList ((3,'a') :| [(5,'b')])) == Nothingnonempty-containersO(m*log(n/m + 1)), m <= n". Union with a combining function. unionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "aA"), (7, "C")])nonempty-containersO(m*log(n/m + 1)), m <= n;. Union with a combining function, given the matching key. let f key left_value right_value = (show key) ++ ":" ++ left_value ++ "|" ++ right_value unionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "5:a|A"), (7, "C")])nonempty-containersThe union of a non-empty list of maps, with a combining operation: ( f ==  ( f)). unionsWith (++) (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])]) == fromList ((3, "bB3") :| [(5, "aAA3"), (7, "C")])nonempty-containersO(m*log(n/m + 1)), m <= n. Difference of two maps. Return elements of the first map not existing in the second map.!Returns a potentially empty map (8), in case the first map is a subset of the second map. difference (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.Map.singleton 3 "b"nonempty-containersSame as .nonempty-containersO(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the values of these keys. If it returns , the element is discarded (proper set difference). If it returns ( y+), the element is updated with a new value y.!Returns a potentially empty map (), in case the first map is a subset of the second map and the function returns  for every pair. 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")])) == Data.Map.singleton 3 "b:B"nonempty-containersO(n+m). Difference with a combining function. When two equal keys are encountered, the combining function is applied to the key and both values. If it returns , the element is discarded (proper set difference). If it returns ( y+), the element is updated with a new value y.!Returns a potentially empty map (), in case the first map is a subset of the second map and the function returns  for every pair. 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")])) == Data.Map.singleton 3 "3:b|B"nonempty-containersO(m*log(n/m + 1)), m <= n. Intersection of two maps. Return data in the first map for the keys existing in both maps. ( m1 m2 ==   m1 m2).!Returns a potentially empty map (1), in case the two maps share no keys in common. intersection (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.Map.singleton 5 "a"nonempty-containersO(m*log(n/m + 1)), m <= n). Intersection with a combining function.!Returns a potentially empty map (1), in case the two maps share no keys in common. intersectionWith (++) (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.Map.singleton 5 "aA"nonempty-containersO(m*log(n/m + 1)), m <= n). Intersection with a combining function.!Returns a potentially empty map (1), in case the two maps share no keys in common. let f k al ar = (show k) ++ ":" ++ al ++ "|" ++ ar intersectionWithKey f (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == Data.Map.singleton 5 "5:a|A"nonempty-containersO(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.nonempty-containersO(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.nonempty-containersO(n). Fold the keys and values in the map using the given right-associative binary operator, such that  f z ==  ( f) z . . For example, 4keysList map = foldrWithKey (\k x ks -> k:ks) [] mapnonempty-containersO(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.nonempty-containersO(n). Fold the keys and values in the map using the given left-associative binary operator, such that  f z ==  (\z' (kx, x) -> f z' kx x) z . . For example, 6keysList = reverse . foldlWithKey (\ks k x -> k:ks) []nonempty-containersO(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.nonempty-containersO(n)0. Return all keys of the map in ascending order. 4keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5])nonempty-containersO(n). An alias for . Return all key/value pairs in the map in ascending key order. assocs (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])nonempty-containersO(n)+. The non-empty set of all keys of the map. keysSet (fromList ((5,"a") :| [(3,"b")])) == Data.Set.NonEmpty.fromList (3 :| [5])nonempty-containersO(n),. Map a function over all values in the map. let f key x = (show key) ++ ":" ++ x mapWithKey f (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "3:b") :| [(5, "5:a")])nonempty-containersO(n). Convert the map to a list of key/value pairs where the keys are in ascending order. toAscList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")])nonempty-containersO(n). Convert the map to a list of key/value pairs where the keys are in descending order. toDescList (fromList ((5,"a") :| [(3,"b")])) == ((5,"a") :| [(3,"b")])nonempty-containersO(log n) . Convert a  into an  by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. If key is already present, will overwrite the original value.See 8 for a version that is constant-time if the new key is strictly smaller than all keys in the original map. insertMap 4 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")]) insertMap 4 "c" Data.Map.empty == singleton 4 "c"nonempty-containersO(log n) . Convert a  into an  by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. Uses a combining function with the new value as the first argument if the key is already present. insertMapWith (++) 4 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(4,"c"), (5,"a")]) insertMapWith (++) 5 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"ca")])nonempty-containersO(log n) . Convert a  into an  by adding a key-value pair. Because of this, we know that the map must have at least one element, and so therefore cannot be empty. Uses a combining function with the key and new value as the first and second arguments if the key is already present. let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value insertWithKey f 5 "xxx" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "5:xxx|a")]) insertWithKey f 7 "xxx" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) insertWithKey f 5 "xxx" Data.Map.empty == singleton 5 "xxx"nonempty-containersO(1) Convert a  into an . by adding a key-value pair where the key is strictly less than all keys in the input map. The keys in the original map must all be strictly greater than the new key.  The precondition is not checked. insertMapMin 2 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((2,"c") :| [(3,"b"), (5,"a")]) valid (insertMapMin 2 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == True valid (insertMapMin 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False valid (insertMapMin 3 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == Falsenonempty-containersO(log n) Convert a  into an . by adding a key-value pair where the key is strictly greater than all keys in the input map. The keys in the original map must all be strictly less than the new key.  The precondition is not checked.'While this has the same asymptotics as , it saves a constant factor for key comparison (so may be helpful if comparison is expensive) and also does not require an  instance for the key type. insertMap 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")]) == fromList ((3,"b") :| [(5,"a"), (7,"c")]) valid (insertMap 7 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == True valid (insertMap 2 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == False valid (insertMap 5 "c" (Data.Map.fromList [(5,"a"), (3,"b")])) == Falsenonempty-containersO(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  .See - for a version where the first argument is a . 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')])nonempty-containersO(log n). 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 .See - for a version where the first argument is a . 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")])nonempty-containersO(log n). 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). 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")]))This is how to define  insertLookup using insertLookupWithKey: let 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")])) insertLookup 7 "x" (fromList ((5,"a") :| [(3,"b")])) == (Nothing, fromList ((3, "b") :| [(5, "a"), (7, "x")]))nonempty-containers O(n*log n). Build a map from a non-empty list of key/value pairs with a combining function. See also . fromListWith (++) ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "ab") :| [(5, "aba")])nonempty-containers O(n*log n). Build a map from a non-empty list of key/value pairs with a combining function. See also . let f k a1 a2 = (show k) ++ a1 ++ a2 fromListWithKey f ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "3ab") :| [(5, "5a5ba")])nonempty-containersO(n). Build a map from an ascending non-empty 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")]) valid (fromAscList ((3,"b") :| [(5,"a"), (5,"b")])) == True valid (fromAscList ((5,"a") :| [(3,"b"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from an ascending non-empty 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")]) valid (fromAscListWith (++) ((3,"b") :| [(5,"a"), (5,"b"))]) == True valid (fromAscListWith (++) ((5,"a") :| [(3,"b"), (5,"b"))]) == Falsenonempty-containersO(n). Build a map from an ascending non-empty list in linear time with a combining function for equal keys. /The precondition (input list is ascending) is not checked./ let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2 fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")]) == fromList ((3, "b") :| [(5, "5:b5:ba")]) valid (fromAscListWithKey f ((3,"b") :| [(5,"a"), (5,"b"), (5,"b")])) == True valid (fromAscListWithKey f ((5,"a") :| [(3,"b"), (5,"b"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from an ascending non-empty list of distinct elements in linear time.  The precondition is not checked. fromDistinctAscList ((3,"b") :| [(5,"a")]) == fromList ((3, "b") :| [(5, "a")]) valid (fromDistinctAscList ((3,"b") :| [(5,"a")])) == True valid (fromDistinctAscList ((3,"b") :| [(5,"a"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from a descending non-empty list in linear time. ;The precondition (input list is descending) is not checked. fromDescList ((5,"a") :| [(3,"b")]) == fromList ((3, "b") :| [(5, "a")]) fromDescList ((5,"a") :| [(5,"b"), (3,"b")]) == fromList ((3, "b") :| [(5, "b")]) valid (fromDescList ((5,"a") :| [(5,"b"), (3,"b")])) == True valid (fromDescList ((5,"a") :| [(3,"b"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from a descending non-empty list in linear time with a combining function for equal keys. /The precondition (input list is descending) is not checked./ fromDescListWith (++) ((5,"a") :| [(5,"b"), (3,"b")]) == fromList ((3, "b") :| [(5, "ba")]) valid (fromDescListWith (++) ((5,"a") :| [(5,"b"), (3,"b")])) == True valid (fromDescListWith (++) ((5,"a") :| [(3,"b"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from a descending non-empty list in linear time with a combining function for equal keys. /The precondition (input list is descending) is not checked./ let f k a1 a2 = (show k) ++ ":" ++ a1 ++ a2 fromDescListWithKey f ((5,"a") :| [(5,"b"), (5,"b"), (3,"b")]) == fromList ((3, "b") :| [(5, "5:b5:ba")]) valid (fromDescListWithKey f ((5,"a") :| [(5,"b"), (5,"b"), (3,"b")])) == True valid (fromDescListWithKey f ((5,"a") :| [(3,"b"), (5,"b"), (5,"b")])) == Falsenonempty-containersO(n). Build a map from a descending list of distinct elements in linear time.  The precondition is not checked. fromDistinctDescList ((5,"a") :| [(3,"b")]) == fromList ((3, "b") :| [(5, "a")]) valid (fromDistinctDescList ((5,"a") :| [(3,"b")])) == True valid (fromDistinctDescList ((5,"a") :| [(5,"b"), (3,"b")])) == Falsenonempty-containersO(log n). Delete a key and its value from the non-empty map. A potentially empty map (=) is returned, since this might delete the last item in the >. When the key is not a member of the map, is equivalent to . delete 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b" delete 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.Singleton [(3, "b"), (5, "a")]nonempty-containersO(log n). 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")])nonempty-containersO(log n). 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")])nonempty-containersO(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.!Returns a potentially empty map (), because we can't know ahead of time if the function returns $ and deletes the final item in the . let f x = if x == "a" then Just "new a" else Nothing update f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "new a")] update f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a")] update f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"nonempty-containersO(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.!Returns a potentially empty map (), because we can't know ahead of time if the function returns $ and deletes the final item in the . let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing updateWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "5:new a")] updateWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a")] updateWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"nonempty-containersO(log n). Lookup and update. See also . The function returns changed value, if it is updated. Returns the original key value if the map entry is deleted.!Returns a potentially empty map (?) in the case that we delete the final key of a singleton map. let f k x = if x == "a" then Just ((show k) ++ ":new a") else Nothing updateLookupWithKey f 5 (fromList ((5,"a") :| [(3,"b")])) == (Just "5:new a", Data.Map.fromList ((3, "b") :| [(5, "5:new a")])) updateLookupWithKey f 7 (fromList ((5,"a") :| [(3,"b")])) == (Nothing, Data.Map.fromList ((3, "b") :| [(5, "a")])) updateLookupWithKey f 3 (fromList ((5,"a") :| [(3,"b")])) == (Just "b", Data.Map.singleton 5 "a")nonempty-containersO(log n). The expression ( f k map) alters the value x at k, or absence thereof. 8 can be used to insert, delete, or update a value in a  . In short : Data.Map.lookup k ( f k m) = f ( k m).!Returns a potentially empty map (), because we can't know ahead of time if the function returns $ and deletes the final item in the .See  for a version that disallows deletion, and so therefore can return . let f _ = Nothing alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a")] alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b" let f _ = Just "c" alter f 7 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "a"), (7, "c")] alter f 5 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "c")]nonempty-containersO(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  . In short: Data.Map.lookup k <$>  f k m = f ( k m).Example: interactiveAlter :: Int -> NEMap Int String -> IO (Map Int 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) Like Data.Map.alterF for , 7 can be considered to be a unifying generalization of  and ;; however, as a constrast, it cannot be used to implement , because it must return a  instead of an ; (because the function might delete the final item in the *). When used with trivial functors like  and 0, it is often slightly slower than specialized  and . However, when the functor is non-trivial and key comparison is not particularly cheap, it is the fastest way.See  for a version that disallows deletion, and so therefore can return  and be used to implement Note on rewrite rules:3This module includes GHC rewrite rules to optimize  for the  and  functors. In general, these rules improve performance. The sole exception is that when using , deleting a key that is already absent takes longer than it would without the rules. If you expect this to occur a very large fraction of the time, you might consider using a private copy of the  type. Note: Unlike Data.Map.alterF for ,  is not a flipped version of the *+ combinator from Control.Lens.At. However, it match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.nonempty-containersO(log n) . Variant of  that disallows deletion. Allows us to guarantee that the result is also a non-empty Map.nonempty-containersO(log n) . Variant of  that disallows deletion. Allows us to guarantee that the result is also a non-empty Map.Like Data.Map.alterF for ', can be used to generalize and unify  and . However, because it disallows deletion, it cannot be used to implement .See # for usage information and caveats.Note: Neither  nor , can be considered flipped versions of the *+ combinator from Control.Lens.At. However, this can match the shape expected from most functions expecting lenses, getters, and setters, so can be thought of as a "psuedo-lens", with virtually the same practical applications as a legitimate lens.WARNING: The rewrite rule for 5 exposes an inconsistency in undefined behavior for Data.Map. Data.Map.alterF will actually maintain, the original key in the map when used with  ; however, Data.Map.insertWith will replace4 the orginal key in the map. The rewrite rule for  has chosen to be faithful to Data.Map.insertWith, and not Data.Map.alterF,, for the sake of a cleaner implementation.nonempty-containersO(n)'. Traverse keys/values and collect the  results.!Returns a potentially empty map (), our function might return  on every item in the .Use  whenever possible (if your  also has  instance). This version is provided only for types that do not have  instance, since  is not at the moment (and might not ever be) an official superclass of .nonempty-containersO(n)'. Traverse keys/values and collect the  results.!Returns a potentially empty map (), our function might return  on every item in the .Is more general than , since works with all , and not just .nonempty-containersO(n). The function  threads an accumulating argument through the map in ascending order of keys. let f a b = (a ++ b, b ++ "X") mapAccum f "Everything: " (fromList ((5,"a") :| [(3,"b")])) == ("Everything: ba", fromList ((3, "bX") :| [(5, "aX")]))nonempty-containersO(n). The function  threads an accumulating argument through the map in ascending order of keys. let f a k b = (a ++ " " ++ (show k) ++ "-" ++ b, b ++ "X") mapAccumWithKey f "Everything:" (fromList ((5,"a") :| [(3,"b")])) == ("Everything: 3-b 5-a", fromList ((3, "bX") :| [(5, "aX")]))nonempty-containersO(n). The function  threads an accumulating argument through the map in descending order of keys.nonempty-containers O(n*log n).  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.While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty. 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"nonempty-containers O(n*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 f maps two or more distinct keys to the same new key. In this case the associated values will be combined using c. The value at the greater of the two original keys is used as the first argument to c.While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty. 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"nonempty-containersO(n).  f s ==  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, we have: and [x < y ==> f x < f y | x <- ls, y <- ls] ==> mapKeysMonotonic f s == mapKeys f s where ls = keys sThis means that f maps distinct original keys to distinct resulting keys. This function has better performance than .While the size of the result map may be smaller than the input map, the output map is still guaranteed to be non-empty if the input map is non-empty. mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")])) == fromList ((6, "b") :| [(10, "a")]) valid (mapKeysMonotonic (\ k -> k * 2) (fromList ((5,"a") :| [(3,"b")]))) == True valid (mapKeysMonotonic (\ _ -> 1) (fromList ((5,"a") :| [(3,"b")]))) == Falsenonempty-containersO(n)/. Filter all values that satisfy the predicate.!Returns a potentially empty map (), because we could potentailly filter out all items in the original . filter (> "a") (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b" filter (> "x") (fromList ((5,"a") :| [(3,"b")])) == Data.Map.empty filter (< "a") (fromList ((5,"a") :| [(3,"b")])) == Data.Map.emptynonempty-containersO(n)4. Filter all keys/values that satisfy the predicate.!Returns a potentially empty map (), because we could potentailly filter out all items in the original . filterWithKey (\k _ -> k > 4) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"nonempty-containersO(m*log(n/m + 1)), m <= n. Restrict an  to only those keys found in a . m `restrictKeys` s =  (k _ -> k -. s) m m `restrictKeys` s = m   (const ()) s nonempty-containersO(m*log(n/m + 1)), m <= n. Remove all keys in a  from an . m `withoutKeys` s =  (k _ -> k -/ s) m m `withoutKeys` s = m   (const ()) s nonempty-containersO(n)-. Partition the map according to a predicate. Returns a % with potentially two non-empty maps: n11 means that the predicate was true for all items. n22 means that the predicate was false for all items. n1 n2 gives n1> (all of the items that were true for the predicate) and n2; (all of the items that were false for the predicate). See also . partition (> "a") (fromList ((5,"a") :| [(3,"b")])) == These (singleton 3 "b") (singleton 5 "a") partition (< "x") (fromList ((5,"a") :| [(3,"b")])) == This (fromList ((3, "b") :| [(5, "a")])) partition (> "x") (fromList ((5,"a") :| [(3,"b")])) == That (fromList ((3, "b") :| [(5, "a")]))nonempty-containersO(n)-. Partition the map according to a predicate. Returns a % with potentially two non-empty maps: n1 means that the predicate was true for all items, returning the original map. n2 means that the predicate was false for all items, returning the original map. n1 n2 gives n1> (all of the items that were true for the predicate) and n2; (all of the items that were false for the predicate). See also . partitionWithKey (\ k _ -> k > 3) (fromList ((5,"a") :| [(3,"b")])) == These (singleton 5 "a") (singleton 3 "b") partitionWithKey (\ k _ -> k < 7) (fromList ((5,"a") :| [(3,"b")])) == This (fromList ((3, "b") :| [(5, "a")])) partitionWithKey (\ k _ -> k > 7) (fromList ((5,"a") :| [(3,"b")])) == That (fromList ((3, "b") :| [(5, "a")]))nonempty-containersO(log n). Take while a predicate on the keys holds. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k. See note at .!Returns a potentially empty map (8), because the predicate might fail on the first input. takeWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.takeWhile (p . fst) . Data.Foldable.toList takeWhileAntitone p =  (k _ -> p k) nonempty-containersO(log n). Drop while a predicate on the keys holds. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k. See note at . dropWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.dropWhile (p . fst) . Data.Foldable.toList dropWhileAntitone p =  (k -> not (p k)) nonempty-containersO(log n). Divide a map at the point where a predicate on the keys stops holding. The user is responsible for ensuring that for all keys j and k in the map, j < k ==> p j >= p k. Returns a % with potentially two non-empty maps: n1 means that the predicate never failed for any item, returning the original map. n2 means that the predicate failed for the first item, returning the original map. n1 n2 gives n1 (the map up to the point where the predicate on the keys stops holding) and n2 (the map starting from the point where the predicate stops holding) 5spanAntitone p xs = partitionWithKey (k _ -> p k) xs  Note: if p is not actually antitone, then  spanAntitone will split the map at some  unspecified point where the predicate switches from holding to not holding (where the predicate is seen to hold before the first key and to fail after the last key).nonempty-containersO(n). Map values and collect the  results.!Returns a potentially empty map (2), because the function could potentially return  on all items in the . let f x = if x == "a" then Just "new a" else Nothing mapMaybe f (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "new a"nonempty-containersO(n)". Map keys/values and collect the  results.!Returns a potentially empty map (2), because the function could potentially return  on all items in the . let f k _ = if k < 5 then Just ("key : " ++ (show k)) else Nothing mapMaybeWithKey f (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "key : 3"nonempty-containersO(n). Map values and separate the  and  results. Returns a % with potentially two non-empty maps: n1! means that the results were all . n2! means that the results were all . n1 n2 gives n1! (the map where the results were  ) and n2! (the map where the results were ) let f a = if a < "c" then Left a else Right a mapEither f (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")])) == These (fromList ((3,"b") :| [(5,"a")])) (fromList ((1,"x") :| [(7,"z")])) mapEither (\ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")])) == That (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")]))nonempty-containersO(n)#. Map keys/values and separate the  and  results. Returns a % with potentially two non-empty maps: n1! means that the results were all . n2! means that the results were all . n1 n2 gives n1! (the map where the results were  ) and n2! (the map where the results were ) 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")])) == These (fromList ((1,2) :| [(3,6)])) (fromList ((5,"aa") :| [(7,"zz")])) mapEitherWithKey (\_ a -> Right a) (fromList ((5,"a") :| [(3,"b"), (1,"x"), (7,"z")])) == That (fromList ((1,"x") :| [(3,"b"), (5,"a"), (7,"z")]))nonempty-containersO(log n). The expression ( k map) is potentially a  containing up to two s based on splitting the map into maps containing items before and after the given key k-. It will never return a map that contains k itself. means that k was the only key in the the original map, and so there are no items before or after it. ( n1) means k< was larger than or equal to all items in the map, and n1# is the entire original map (minus k, if it was present) ( n2) means k= was smaller than or equal to all items in the map, and n2# is the entire original map (minus k, if it was present) ( n1 n2) gives n1; (the map of all keys from the original map less than k) and n2> (the map of all keys from the original map greater than k) split 2 (fromList ((5,"a") :| [(3,"b")])) == Just (That (fromList ((3,"b") :| [(5,"a")])) ) split 3 (fromList ((5,"a") :| [(3,"b")])) == Just (That (singleton 5 "a") ) split 4 (fromList ((5,"a") :| [(3,"b")])) == Just (These (singleton 3 "b") (singleton 5 "a")) split 5 (fromList ((5,"a") :| [(3,"b")])) == Just (This (singleton 3 "b") ) split 6 (fromList ((5,"a") :| [(3,"b")])) == Just (This (fromList ((3,"b") :| [(5,"a")])) ) split 5 (singleton 5 "a") == Nothingnonempty-containersO(log n). The expression ( k map) splits a map just like  but also returns  k map, as the first field in the : splitLookup 2 (fromList ((5,"a") :| [(3,"b")])) == That (That (fromList ((3,"b") :| [(5,"a")]))) splitLookup 3 (fromList ((5,"a") :| [(3,"b")])) == These "b" (That (singleton 5 "a")) splitLookup 4 (fromList ((5,"a") :| [(3,"b")])) == That (These (singleton 3 "b") (singleton 5 "a")) splitLookup 5 (fromList ((5,"a") :| [(3,"b")])) == These "a" (This (singleton 3 "b")) splitLookup 6 (fromList ((5,"a") :| [(3,"b")])) == That (This (fromList ((3,"b") :| [(5,"a")]))) splitLookup 5 (singleton 5 "a") == This "a"nonempty-containersO(1). Decompose a map into pieces based on the structure of the underlying tree. This function is useful for consuming a map in parallel.No guarantee is made as to the sizes of the pieces; an internal, but deterministic process determines this. However, it is guaranteed that the pieces returned will be in ascending order (all elements in the first submap less than all elements in the second, and so on).Note that the current implementation does not return more than four submaps, but you should not depend on this behaviour because it can change in the future without notice.nonempty-containersO(m*log(n/m + 1)), m <= n . This function is defined as ( =  (==)).nonempty-containersO(m*log(n/m + 1)), m <= n. The expression ( 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 : isSubmapOfBy (==) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (<=) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (fromList (('a',1) :| [('b',2)]))But the following are all : isSubmapOfBy (==) (singleton 'a' 2) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (<) (singleton 'a' 1) (fromList (('a',1) :| [('b',2)])) isSubmapOfBy (==) (fromList (('a',1) :| [('b',2)])) (singleton 'a' 1)nonempty-containersO(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a submap but not equal). Defined as ( =  (==)).nonempty-containersO(m*log(n/m + 1)), m <= n. 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 values. For example, the following expressions are all : isProperSubmapOfBy (==) (singleton 1 1) (fromList ((1,1) :| [(2,2)])) isProperSubmapOfBy (<=) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))But the following are all : isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (fromList ((1,1) :| [(2,2)])) isProperSubmapOfBy (==) (fromList ((1,1) :| [(2,2)])) (singleton 1 1)) isProperSubmapOfBy (<) (singleton 1 1) (fromList ((1,1) :| [(2,2)]))nonempty-containersO(log n) . Lookup the index of a key, which is its zero-based index in the sequence sorted by keys. The index is a number from 0 up to, but not including, the  of the map. isJust (lookupIndex 2 (fromList ((5,"a") :| [(3,"b")]))) == False fromJust (lookupIndex 3 (fromList ((5,"a") :| [(3,"b")]))) == 0 fromJust (lookupIndex 5 (fromList ((5,"a") :| [(3,"b")]))) == 1 isJust (lookupIndex 6 (fromList ((5,"a") :| [(3,"b")]))) == Falsenonempty-containersO(log n) . Return the index of a key, which is its zero-based index in the sequence sorted by keys. The index is a number from 0 up to, but not including, the  of the map. Calls  when the key is not a  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 mapnonempty-containersO(log n). Retrieve an element by its index, i.e. by its zero-based index in the sequence sorted by keys. If the index7 is out of range (less than zero, greater or equal to  of the map),  is called. 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 rangenonempty-containersO(log n). Update the element at index, i.e. by its zero-based index in the sequence sorted by keys. If the index7 is out of range (less than zero, greater or equal to  of the map),  is called.Returns a possibly empty map (), because the function might end up deleting the last key in the map. See  for a version that disallows deletion, guaranteeing that the result is also a non-empty Map. updateAt (\ _ _ -> Just "x") 0 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "x"), (5, "a")] updateAt (\ _ _ -> Just "x") 1 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.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")])) == Data.Map.singleton 5 "a" updateAt (\_ _ -> Nothing) 1 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.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 rangenonempty-containersO(log n) . Variant of  that disallows deletion. Allows us to guarantee that the result is also a non-empty Map.nonempty-containersO(log n). Delete the element at index, i.e. by its zero-based index in the sequence sorted by keys. If the index7 is out of range (less than zero, greater or equal to  of the map),  is called.!Returns a potentially empty map () because of the possibility of deleting the last item in a map. deleteAt 0 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a" deleteAt 1 (fromList ((5,"a") :| [(3,"b")])) == Data.Map.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 rangenonempty-containersTake a given number of entries in key order, beginning with the smallest keys.Returns a possibly empty map (%), which can only happen if we call take 0. take n = Data.Map.fromDistinctAscList . Data.List.NonEmpty.take n .  nonempty-containersDrop a given number of entries in key order, beginning with the smallest keys.Returns a possibly empty map (), in case we drop all of the elements (which can happen if we drop a number greater than or equal to the number of items in the map) drop n = Data.Map.fromDistinctAscList . Data.List.NonEmpty.drop' n .  nonempty-containersO(log n)$. Split a map at a particular index i. n1 means that there are less than i items in the map, and n1 is the original map. n2 means i was 0; we dropped 0 items, so n2 is the original map. n1 n2 gives n1 (taking i' items from the original map) and n2 (dropping i items from the original map))nonempty-containersO(1). The minimal key of the map. Note that this is total, making 1) obsolete. It is constant-time, so has better asymptotics than Data.Map.lookupMin and Data.Map.findMin , as well. 4findMin (fromList ((5,"a") :| [(3,"b")])) == (3,"b")nonempty-containersO(log n). The maximal key of the map. Note that this is total, making 1) obsolete. 4findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a")nonempty-containersO(1)<. Delete the minimal key. Returns a potentially empty map (), because we might end up deleting the final key in a singleton map. It is constant-time, so has better asymptotics than 10. deleteMin (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.Map.fromList [(5,"a"), (7,"c")] deleteMin (singleton 5 "a") == Data.Map.emptynonempty-containersO(log n)<. Delete the maximal key. Returns a potentially empty map (), because we might end up deleting the final key in a singleton map. deleteMax (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.Map.fromList [(3,"b"), (5,"a")] deleteMax (singleton 5 "a") == Data.Map.emptynonempty-containersO(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See  for a version that can guaruntee that we return a non-empty map. updateMin (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "Xb"), (5, "a")] updateMin (\ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"nonempty-containersO(1). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty.nonempty-containersO(1) if delete, O(log n) otherwise. Update the value at the minimal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See 0 for a version that guaruntees a non-empty map. updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3,"3:b"), (5,"a")] updateMinWithKey (\ _ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"nonempty-containersO(1). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty. Note that it also is able to have better asymptotics than  in general.nonempty-containersO(log n). Update the value at the maximal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See  for a version that can guarantee that we return a non-empty map. updateMax (\ a -> Just ("X" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3, "b"), (5, "Xa")] updateMax (\ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 3 "b"nonempty-containersO(log n). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty.nonempty-containersO(log n). Update the value at the maximal key. Returns a potentially empty map (), because we might end up deleting the final key in the map if the function returns . See / for a version that guaruntees a non-empty map. updateMinWithKey (\ k a -> Just ((show k) ++ ":" ++ a)) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.fromList [(3,"3:b"), (5,"a")] updateMinWithKey (\ _ _ -> Nothing) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a"nonempty-containersO(log n). A version of  that disallows deletion, allowing us to guarantee that the result is also non-empty.nonempty-containersO(1). Retrieves the value associated with minimal key of the map, and the map stripped of that element. It is constant-time, so has better asymptotics than Data.Map.minView for .Note that unlike Data.Map.minView for 9, this cannot ever fail, so doesn't need to return in a . However, the result  is potentially empty, since the original map might have contained just a single item. minView (fromList ((5,"a") :| [(3,"b")])) == ("b", Data.Map.singleton 5 "a")nonempty-containersO(1). Delete and find the minimal key-value pair. It is constant-time, so has better asymptotics that Data.Map.minView for .Note that unlike Data.Map.deleteFindMin for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original map might have contained just a single item. deleteFindMin (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((3,"b"), Data.Map.fromList [(5,"a"), (10,"c")])nonempty-containersO(log n). Retrieves the value associated with maximal key of the map, and the map stripped of that element.Note that unlike Data.Map.maxView from 9, this cannot ever fail, so doesn't need to return in a . However, the result  is potentially empty, since the original map might have contained just a single item. maxView (fromList ((5,"a") :| [(3,"b")])) == ("a", Data.Map.singleton 3 "b")nonempty-containersO(log n)-. Delete and find the minimal key-value pair.Note that unlike Data.Map.deleteFindMax for , this cannot ever fail, and so is a total function. However, the result  is potentially empty, since the original map might have contained just a single item. deleteFindMax (fromList ((5,"a") :| [(3,"b"), (10,"c")])) == ((10,"c"), Data.Map.fromList [(3,"b"), (5,"a")])nonempty-containersSpecial property of non-empty maps: The type of non-empty maps over uninhabited keys is itself uninhabited.This property also exists for values) inside a non-empty container (like for , NESeq, and NEIntMap-); this can be witnessed using the function  . fold1.9 9 (c) Justin Le 2018BSD3 justin@jle.im experimental non-portableNone&& nonempty-containersIf s is an instance of  HasNonEmpty, it means that there is a corresponding "non-empty" version of s,  s.7In order for things to be well-behaved, we expect that  and maybe  & should form an isomorphism (or that    == id. In addition, the following properties should hold for most exectations: (x == empty) ==> isEmpty x '(x == empty) ==> isNothing (nonEmpty x) 'isEmpty x ==> isNothing (nonEmpty x) +unsafeToNonEmpty x == fromJust (nonEmpty x) Usually, 'not (isEmpty x) ==> isJust (nonEmpty x)!, but this isn't necessary.nonempty-containers s is the "non-empty" version of s.nonempty-containers"Smart constructor" for  s given a (potentailly empty) s. Will return  if the s was empty, and  n if the s was not empty, with n ::  s. Should form an isomorphism with   .nonempty-containers Convert a  s (non-empty s) back into an s/, "obscuring" its non-emptiness from its type.nonempty-containersContinuation-based version of 5, which can be more efficient in certain situations.   should be id.nonempty-containers An empty s.nonempty-containers Check if an s is empty.nonempty-containersUnsafely coerce an s into an  s (non-empty s). Is undefined (throws a runtime exception when evaluation is attempted) when the s is empty.nonempty-containersThe  and  patterns allow you to treat a s as if it were either a  n (where n is a non-empty version of s, type  s) or an . Matching on ( means that the original item was empty.0This is a bidirectional pattern, so you can use 2 as an expression, and it will be interpreted as .Note that because of the way coverage checking works for polymorphic pattern synonyms, you will unfortunatelly still get incomplete pattern match warnings if you match on both  and , even though the two are meant to provide complete coverage. However, many instances of  (like , , , 6) will provide their own monomorphic versions of these patterns that can be verified as complete covers by GHC.See  for more information.nonempty-containersThe  and  patterns allow you to treat a s as if it were either a  n (where n is a non-empty version of s, type  s) or an .6For example, you can pattern match on a list to get a  (non-empty list): #safeHead :: [Int] -> Int safeHead (< (x :| _)) = x -- here, the list was not empty safehead 3 = 0 -- here, the list was empty  Matching on  n# means that the original input was not+ empty, and you have a verified-non-empty n ::  s to use.Note that because of the way coverage checking works for polymorphic pattern synonyms, you will unfortunatelly still get incomplete pattern match warnings if you match on both  and , even though the two are meant to provide complete coverage. However, many instances of  (like , , , 6) will provide their own monomorphic versions of these patterns that can be verified as complete covers by GHC.0This is a bidirectional pattern, so you can use  to convert a  s back into an s&, "obscuring" its non-emptiness (see ).nonempty-containersUseful function for mapping over the "non-empty" representation of a type.nonempty-containersUseful function for applying a function on the "non-empty" representation of a type."If you want a continuation taking  s -> 'Maybe r', you can use  .  H Safe-Inferred&IIJKLMMNOPQRSTUVWXY Z[\;]^_`abc"#defghijklmnopqrstuvwwxyz;{^][UV`|}~D  ./QRX(T0WE23  ./E0QRSTUVWXY Z[\;]^_`ab     9 8 ;  ^  ]    4   T      @                               7:5>?<        z ; { ^ ] [ X  Q  R U V  ` | } ~                  DF  ./(CGT0WE./E23  0     ;              JIIIIIIIIIIIIJKIIIIIIJJIIIIIII%I$IIIIJ-IHHHHHHHH#nonempty-containers-0.3.4.2-inplaceData.Set.NonEmptyData.IntSet.NonEmptyData.IntMap.NonEmptyData.IntMap.NonEmpty.InternalData.IntSet.NonEmpty.InternalData.Map.NonEmptyData.Map.NonEmpty.InternalData.Sequence.NonEmptyData.Sequence.NonEmpty.InternalData.Set.NonEmpty.InternalData.Containers.NonEmptyinsertdelete Data.IntMapempty insertIntMap IsNonEmptyIsEmptyPreludefoldr Data.Foldablefoldr1foldlfoldl1 mapWithKey foldrWithKey foldlWithKey unionWith IsNotEmpty fromAscListinsertIntMapWithtraverseWithKeyData.IntMap.Lazy lookupMinMap lookupMaxMapminimummaximum Data.IntSet insertIntSetdisjoint lookupMinControl.Lens.AtatData.SetSetmember notMember deleteMinData.Map insertMap insertMapWith<|tailData.Seq nonEmptySeq:<||:||> insertSeqAt withNonEmpty unzipWith Data.SequencesortOnunstableSortOnunzip Data.FunctiononcartesianProduct insertSet toAscListpowerSet disjointUnionPaths_nonempty_containersbasecontainers-0.6.2.1Data.IntSet.InternalKeyNEIntMapneimK0neimV0 neimIntMapfoldr'foldl'foldMapWithKeymapunionunionselemssizetoMaptraverseWithKey1toList nonEmptyMapfromList singleton insertWithvalid insertMinMap insertMaxMaptraverseMapWithKey$fComonadNEIntMap$fTraversable1NEIntMap$fFoldable1NEIntMap$fTraversableNEIntMap$fFoldableNEIntMap$fFunctorNEIntMap$fSemigroupNEIntMap$fFromJSONNEIntMap$fToJSONNEIntMap$fDataNEIntMap$fNFDataNEIntMap$fShowNEIntMap$fReadNEIntMap$fRead1NEIntMap$fShow1NEIntMap$fOrd1NEIntMap $fEq1NEIntMap $fOrdNEIntMap $fEqNEIntMapNEIntSetneisV0 neisIntSet nonEmptySettoSet insertMinSet insertMaxSet disjointSet$fSemigroupNEIntSet$fFromJSONNEIntSet$fToJSONNEIntSet$fDataNEIntSet$fNFDataNEIntSet$fReadNEIntSet$fShowNEIntSet $fOrdNEIntSet $fEqNEIntSet insertSetMin insertSetMax unsafeFromSetfromDistinctAscListlookupLTlookupGTlookupLElookupGEfoldr1'foldl1' isSubsetOfisProperSubsetOf difference\\ intersectionfilter partitionsplit splitMember splitRootfindMinfindMax deleteMax deleteFindMin deleteFindMax toDescList unsafeFromMapinsertMapWithKey insertMapMin insertMapMaxfromSet fromListWithfromListWithKeyfromAscListWithfromAscListWithKey insertWithKeyinsertLookupWithKeyadjust adjustWithKeyupdate updateWithKeyupdateLookupWithKeyalteralterFalter'alterF'lookup!?!findWithDefault unionWithKey unionsWithdifferenceWithdifferenceWithKeyintersectionWithintersectionWithKeymapAccummapAccumWithKeymapAccumRWithKeymapKeys mapKeysWithmapKeysMonotonic foldrWithKey' foldlWithKey'keysassocskeysSet filterWithKey restrictKeys withoutKeyspartitionWithKeymapMaybemapMaybeWithKey mapEithermapEitherWithKey splitLookup isSubmapOf isSubmapOfByisProperSubmapOfisProperSubmapOfBy updateMin adjustMinupdateMinWithKeyadjustMinWithKey updateMax adjustMaxupdateMaxWithKeyadjustMaxWithKeyminViewmaxViewNEMapnemK0nemV0nemMap$fComonadNEMap$fTraversable1NEMap$fFoldable1NEMap$fTraversableNEMap$fFoldableNEMap$fFunctorNEMap$fSemigroupNEMap$fFromJSONNEMap $fToJSONNEMap $fDataNEMap $fNFDataNEMap $fShowNEMap $fReadNEMap $fRead1NEMap $fShow1NEMap $fShow2NEMap $fOrd1NEMap $fOrd2NEMap $fEq1NEMap $fEq2NEMap $fOrdNEMap $fEqNEMapNESeqnesHeadnesTailtoSeqlength fromFunction replicateindex><|><foldMapWithIndextraverseWithIndex1tailszipzipWith sortOnSequnstableSortOnSequnzipSeq unzipWithSeq $fNFDataNESeq$fMonadFixNESeq$fMonadZipNESeq$fTraversable1NESeq$fFoldable1NESeq$fFoldableNESeq$fComonadNESeq $fExtendNESeq $fMonadNESeq $fBindNESeq $fAltNESeq$fApplicativeNESeq $fApplyNESeq$fFunctorNESeq$fSemigroupNESeq$fFromJSONNESeq $fToJSONNESeq $fDataNESeq $fOrd1NESeq $fEq1NESeq $fRead1NESeq $fShow1NESeq $fOrdNESeq $fEqNESeq $fReadNESeq $fShowNESeq$fTraversableNESeq unsafeFromSeq|>><| replicateA replicateA1 replicateM cycleTakingiterateNunfoldrunfoldlheadlastinitscanlscanl1scanrscanr1initschunksOf takeWhileL takeWhileR dropWhileL dropWhileRspanlspanrbreaklbreakrsortsortBy unstableSortunstableSortByadjust'takedropinsertAtdeleteAtsplitAt elemIndexL elemIndexR elemIndicesL elemIndicesR findIndexL findIndexR findIndicesL findIndicesRfoldlWithIndexfoldrWithIndex mapWithIndextraverseWithIndexreverse interspersezip3zipWith3zip4zipWith4 MergeNESet getMergeNESetNESetnesV0nesSetmerge powerSetSetdisjointUnionSetcartesianProductSet$fFoldable1NESet$fFoldableNESet$fSemigroupNESet$fFromJSONNESet $fToJSONNESet $fDataNESet $fNFDataNESet $fShow1NESet $fOrd1NESet $fEq1NESet $fReadNESet $fShowNESet $fOrdNESet $fEqNESet$fSemigroupMergeNESet fromDescListfromDistinctDescListtakeWhileAntitonedropWhileAntitone spanAntitone lookupIndex findIndexelemAt mapMonotonicfromDescListWithfromDescListWithKeytraverseMaybeWithKeytraverseMaybeWithKey1updateAtadjustAt absurdNEMap HasNonEmptyNEnonEmpty fromNonEmptyisEmptyunsafeToNonEmpty overNonEmpty onNonEmpty$fHasNonEmptyVector$fHasNonEmptySeq$fHasNonEmptyIntSet$fHasNonEmptySet$fHasNonEmptyIntMap$fHasNonEmptyMap$fHasNonEmpty[]Data.IntMap.InternalIntMap GHC.MaybeMaybeNothingsemigroupoids-5.3.5-f25d8f21f96a1e3238016584197a21905e3d4cf1a190ab0ad532b7b437ff2f52Data.Semigroup.Foldable.Classfold1GHC.Baseconst Data.MaybemaybeData.Traversabletraverse ApplicativeData.Functor.Bind.ClassApplyunwrapApplicative Data.Semigroup.Traversable.Class traverse1Justcomonad-5.0.8-f1c6b650f10a414152dc26a2d1e940fcd3c9901e07723c213f39408dfb4a424eControl.Comonadextract duplicate sequence1sequence TraversablefoldMap1foldfoldMapFoldableIntSetthese-1.1.1.1-d2fcdddf4c2a25ec3e878e18e97a04a3b0f6728983457c9b3f8e3b0afb018739 Data.TheseTheseThisThatData.Functor.IdentityIdentityData.Functor.ConstConstGHC.Errerror Data.Tupleuncurry Data.EitherLeftRightghc-prim GHC.TypesTrueFalseData.Map.InternalMap GHC.ClassesOrdData.Sequence.InternalSeq:|NonEmpty toNonEmpty Foldable1GHC.ListGHC.PrimseqfmapfstsndliftA2pure<.>compareData.Set.Internal Data.Voidabsurdversion getBinDir getLibDir getDynLibDir getDataDir getLibexecDir getSysconfDirgetDataFileName