-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Non-empty variants of containers data types, with full API -- -- Efficient and optimized non-empty versions of types from -- containers. Inspired by non-empty-containers library, -- except attempting a more faithful port (with under-the-hood -- optimizations) of the full containers API. Also contains a -- convenient typeclass abstraction for converting betwewen non-empty and -- possibly-empty variants. See README.md for more information. @package nonempty-containers @version 0.3.4.2 -- | Unsafe internal-use functions used in the implementation of -- Data.IntMap.NonEmpty. These functions can potentially be used -- to break the abstraction of NEIntMap and produce unsound maps, -- so be wary! module Data.IntMap.NonEmpty.Internal -- | A non-empty (by construction) map from integer keys to values -- a. At least one key-value pair exists in an -- NEIntMap v at all times. -- -- Functions that take an NEIntMap can safely operate on it -- with the assumption that it has at least one key-value pair. -- -- Functions that return an NEIntMap 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 insert) return NEIntMap, but functions -- that might potentially return an empty map (like delete) return -- a IntMap instead. -- -- You can directly construct an NEIntMap with the API from -- Data.IntMap.NonEmpty; it's more or less the same as -- constructing a normal IntMap, except you don't have access to -- empty. There are also a few ways to construct an -- NEIntMap from a IntMap: -- --
-- singleton 1 'a' == fromList ((1, 'a') :| []) -- size (singleton 1 'a') == 1 --singleton :: Key -> a -> NEIntMap a -- | O(log n). Smart constructor for an NEIntMap from a -- IntMap. Returns Nothing if the IntMap was -- originally actually empty, and Just n with an -- NEIntMap, if the IntMap was not empty. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- -- See IsNonEmpty for a pattern synonym that lets you "match on" -- the possiblity of a IntMap being an NEIntMap. -- --
-- nonEmptyMap (Data.IntMap.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")])) --nonEmptyMap :: IntMap a -> Maybe (NEIntMap a) -- | O(log n). A general continuation-based way to consume a -- IntMap as if it were an NEIntMap. -- withNonEmpty def f will take a IntMap. If map -- is empty, it will evaluate to def. Otherwise, a non-empty map -- NEIntMap will be fed to the function f instead. -- --
-- nonEmptyMap == withNonEmpty Nothing Just --withNonEmpty :: r -> (NEIntMap a -> r) -> IntMap a -> r -- | O(n*log n). Build a non-empty map from a non-empty list of -- key/value pairs. See also fromAscList. If the list contains -- more than one value for the same key, the last value for the key is -- retained. -- --
-- fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")]) -- fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")]) --fromList :: NonEmpty (Key, a) -> NEIntMap a -- | O(n). Convert the map to a non-empty list of key/value pairs. -- --
-- toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")]) --toList :: NEIntMap a -> NonEmpty (Key, a) -- | O(n). IntMap a function over all values in the map. -- --
-- map (++ "x") (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "bx") :| [(5, "ax")]) --map :: (a -> b) -> NEIntMap a -> NEIntMap b -- | O(log n). Insert with a function, combining new value and old -- value. insertWith f key value mp will insert the pair -- (key, value) into mp if key does not exist in the map. If the -- key does exist, the function will insert the pair (key, f -- new_value old_value). -- -- See insertIntMapWith for a version where the first argument is -- a IntMap. -- --
-- insertWith (++) 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "xxxa")]) -- insertWith (++) 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) --insertWith :: (a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a -- | O(m*log(n/m + 1)), m <= n. The expression (union -- t1 t2) takes the left-biased union of t1 and -- t2. It prefers t1 when duplicate keys are -- encountered, i.e. (union == unionWith -- const). -- --
-- union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")]) --union :: NEIntMap a -> NEIntMap a -> NEIntMap a -- | The 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")]) --unions :: Foldable1 f => f (NEIntMap a) -> NEIntMap a -- | O(n). Return all elements of the map in the ascending order of -- their keys. -- --
-- elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])
--
elems :: NEIntMap a -> NonEmpty a
-- | O(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')])) == 3 --size :: NEIntMap a -> Int -- | O(log n). Convert a non-empty map back into a normal -- possibly-empty map, for usage with functions that expect -- IntMap. -- -- Can be thought of as "obscuring" the non-emptiness of the map in its -- type. See the IsNotEmpty pattern. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toMap (fromList ((3,"a") :| [(5,"b")])) == Data.IntMap.fromList [(3,"a"), (5,"b")] --toMap :: NEIntMap a -> IntMap a -- | O(n). Fold the values in the map using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . elems. -- --
-- elemsList map = foldr (:) [] map ---- --
-- let f a len = len + (length a) -- foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldr :: (a -> b -> b) -> b -> NEIntMap a -> b -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> NEIntMap a -> b -- | O(n). A version of foldr that uses the value at the -- maximal key in the map as the starting value. -- -- Note that, unlike foldr1 for IntMap, this function is -- total if the input function is total. foldr1 :: (a -> a -> a) -> NEIntMap a -> a -- | O(n). Fold the values in the map using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . elems. -- --
-- elemsList = reverse . foldl (flip (:)) [] ---- --
-- let f len a = len + (length a) -- foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldl :: (a -> b -> a) -> a -> NEIntMap b -> a -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> NEIntMap b -> a -- | O(n). A version of foldl that uses the value at the -- minimal key in the map as the starting value. -- -- Note that, unlike foldl1 for IntMap, this function is -- total if the input function is total. foldl1 :: (a -> a -> a) -> NEIntMap a -> a -- | O(n). traverseWithKey f m == fromList -- $ traverse ((k, v) -> (,) k $ f k v) -- (toList m) That is, behaves exactly like a regular -- traverse except that the traversing function also has access to -- the key associated with a value. -- -- Use traverseWithKey1 whenever possible (if your -- Applicative also has Apply instance). This version is -- provided only for types that do not have Apply instance, since -- Apply is not at the moment (and might not ever be) an official -- superclass of Applicative. -- -- WARNING: Differs from Data.IntMap.traverseWithKey, -- which traverses positive items first, then negative items. -- --
-- traverseWithKey f = unwrapApplicative . traverseWithKey1 (\k -> WrapApplicative . f k) --traverseWithKey :: Applicative t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b) -- | O(n). traverseWithKey1 f m == fromList -- $ traverse1 ((k, v) -> (,) k $ f k v) -- (toList m) -- -- That is, behaves exactly like a regular traverse1 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 traverseWithKey, since works with all -- Apply, and not just Applicative. traverseWithKey1 :: Apply t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b) -- | O(n). Fold the keys and values in the map using the given -- semigroup, such that -- --
-- foldMapWithKey f = fold1 . mapWithKey f ---- -- WARNING: Differs from Data.IntMap.foldMapWithKey, -- which traverses positive items first, then negative items. -- -- This can be an asymptotically faster than foldrWithKey or -- foldlWithKey for some monoids. foldMapWithKey :: Semigroup m => (Key -> a -> m) -> NEIntMap a -> m -- | O(n). A fixed version of traverseWithKey that traverses -- items in ascending order of keys. traverseMapWithKey :: Applicative t => (Key -> a -> t b) -> IntMap a -> t (IntMap b) -- | O(log n). 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 IntMap. /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. insertMinMap :: Key -> a -> IntMap a -> IntMap a -- | O(log n). 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 IntMap. -- /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. insertMaxMap :: Key -> a -> IntMap a -> IntMap a -- | O(n). Test if the internal map structure is valid. valid :: NEIntMap a -> Bool -- | CPP for new functions not in old containers -- --------------------------------------------- -- -- Compatibility layer for lookupMinMap. lookupMinMap :: IntMap a -> Maybe (Key, a) -- | Compatibility layer for lookupMaxMap. lookupMaxMap :: IntMap a -> Maybe (Key, a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance Data.Functor.Classes.Eq1 Data.IntMap.NonEmpty.Internal.NEIntMap instance Data.Functor.Classes.Ord1 Data.IntMap.NonEmpty.Internal.NEIntMap instance Data.Functor.Classes.Show1 Data.IntMap.NonEmpty.Internal.NEIntMap instance Data.Functor.Classes.Read1 Data.IntMap.NonEmpty.Internal.NEIntMap instance GHC.Read.Read e => GHC.Read.Read (Data.IntMap.NonEmpty.Internal.NEIntMap e) instance GHC.Show.Show a => GHC.Show.Show (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance Data.Data.Data a => Data.Data.Data (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance Data.Aeson.Types.ToJSON.ToJSON a => Data.Aeson.Types.ToJSON.ToJSON (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance Data.Aeson.Types.FromJSON.FromJSON a => Data.Aeson.Types.FromJSON.FromJSON (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance GHC.Base.Semigroup (Data.IntMap.NonEmpty.Internal.NEIntMap a) instance GHC.Base.Functor Data.IntMap.NonEmpty.Internal.NEIntMap instance Data.Foldable.Foldable Data.IntMap.NonEmpty.Internal.NEIntMap instance Data.Traversable.Traversable Data.IntMap.NonEmpty.Internal.NEIntMap instance Data.Semigroup.Foldable.Class.Foldable1 Data.IntMap.NonEmpty.Internal.NEIntMap instance Data.Semigroup.Traversable.Class.Traversable1 Data.IntMap.NonEmpty.Internal.NEIntMap instance Control.Comonad.Comonad Data.IntMap.NonEmpty.Internal.NEIntMap -- | Unsafe internal-use functions used in the implementation of -- Data.IntSet.NonEmpty. These functions can potentially be used -- to break the abstraction of NEIntSet and produce unsound sets, -- so be wary! module Data.IntSet.NonEmpty.Internal -- | A non-empty (by construction) set of integers. At least one value -- exists in an NEIntSet a at all times. -- -- Functions that take an NEIntSet can safely operate on it -- with the assumption that it has at least one item. -- -- Functions that return an NEIntSet 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 insert) return NEIntSet, but functions -- that might potentially return an empty map (like delete) return -- a IntSet instead. -- -- You can directly construct an NEIntSet with the API from -- Data.IntSet.NonEmpty; it's more or less the same as -- constructing a normal IntSet, except you don't have access to -- empty. There are also a few ways to construct an -- NEIntSet from a IntSet: -- --
-- nonEmptySet (Data.IntSet.fromList [3,5]) == Just (fromList (3:|[5])) --nonEmptySet :: IntSet -> Maybe NEIntSet -- | O(log n). A general continuation-based way to consume a -- IntSet as if it were an NEIntSet. -- withNonEmpty def f will take a IntSet. If set -- is empty, it will evaluate to def. Otherwise, a non-empty set -- NEIntSet will be fed to the function f instead. -- --
-- nonEmptySet == withNonEmpty Nothing Just --withNonEmpty :: r -> (NEIntSet -> r) -> IntSet -> r -- | O(log n). Convert a non-empty set back into a normal -- possibly-empty map, for usage with functions that expect -- IntSet. -- -- Can be thought of as "obscuring" the non-emptiness of the set in its -- type. See the IsNotEmpty pattern. -- -- nonEmptySet and maybe empty toSet -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toSet (fromList ((3,"a") :| [(5,"b")])) == Data.IntSet.fromList [(3,"a"), (5,"b")] --toSet :: NEIntSet -> IntSet -- | O(1). Create a singleton set. singleton :: Key -> NEIntSet -- | O(n*log n). Create a set from a list of elements. fromList :: NonEmpty Key -> NEIntSet -- | O(n). Convert the set to a non-empty list of elements. toList :: NEIntSet -> NonEmpty Key -- | O(m*log(n/m + 1)), m <= n. The union of two sets, preferring -- the first set when equal elements are encountered. union :: NEIntSet -> NEIntSet -> NEIntSet -- | The union of a non-empty list of sets unions :: Foldable1 f => f NEIntSet -> NEIntSet -- | O(n). Test if the internal set structure is valid. valid :: NEIntSet -> Bool -- | O(log n). Insert new value into a set where values are -- strictly greater than the new values That is, the new value -- must be strictly less than all values present in the -- IntSet. /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. insertMinSet :: Key -> IntSet -> IntSet -- | O(log n). Insert new value into a set where values are -- /strictly less than the new value. That is, the new value must be -- strictly greater than all values present in the IntSet. -- 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. insertMaxSet :: Key -> IntSet -> IntSet -- | CPP for new functions not in old containers -- --------------------------------------------- -- -- Comptability layer for disjoint. disjointSet :: IntSet -> IntSet -> Bool instance GHC.Classes.Eq Data.IntSet.NonEmpty.Internal.NEIntSet instance GHC.Classes.Ord Data.IntSet.NonEmpty.Internal.NEIntSet instance GHC.Show.Show Data.IntSet.NonEmpty.Internal.NEIntSet instance GHC.Read.Read Data.IntSet.NonEmpty.Internal.NEIntSet instance Control.DeepSeq.NFData Data.IntSet.NonEmpty.Internal.NEIntSet instance Data.Data.Data Data.IntSet.NonEmpty.Internal.NEIntSet instance Data.Aeson.Types.ToJSON.ToJSON Data.IntSet.NonEmpty.Internal.NEIntSet instance Data.Aeson.Types.FromJSON.FromJSON Data.IntSet.NonEmpty.Internal.NEIntSet instance GHC.Base.Semigroup Data.IntSet.NonEmpty.Internal.NEIntSet -- |
-- import qualified Data.IntSet.NonEmpty as NEIS ---- -- Note that all asmyptotics O(f(n)) in this module are actually -- O(min(W, f(n))), where W is the number of bits in an -- Int (32 or 64). That is, if f(n) is greater than -- W, all operations are constant-time. module Data.IntSet.NonEmpty -- | A non-empty (by construction) set of integers. At least one value -- exists in an NEIntSet a at all times. -- -- Functions that take an NEIntSet can safely operate on it -- with the assumption that it has at least one item. -- -- Functions that return an NEIntSet 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 insert) return NEIntSet, but functions -- that might potentially return an empty map (like delete) return -- a IntSet instead. -- -- You can directly construct an NEIntSet with the API from -- Data.IntSet.NonEmpty; it's more or less the same as -- constructing a normal IntSet, except you don't have access to -- empty. There are also a few ways to construct an -- NEIntSet from a IntSet: -- --
-- myFunc :: IntSet X -> Y -- myFunc (IsNonEmpty n) = -- here, the user provided a non-empty set, and n is the NEIntSet -- myFunc IsEmpty = -- here, the user provided an empty set ---- -- Matching on IsNonEmpty n means that the original -- IntSet was not empty, and you have a verified-non-empty -- NEIntSet 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 IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsNonEmpty to -- convert a NEIntSet back into a IntSet, obscuring its -- non-emptiness (see toSet). pattern IsNonEmpty :: NEIntSet -> IntSet -- | O(1). The IsNonEmpty and IsEmpty patterns allow -- you to treat a IntSet as if it were either a -- IsNonEmpty n (where n is a NEIntSet) -- or an IsEmpty. -- -- Matching on IsEmpty means that the original IntSet was -- empty. -- -- A case statement handling both IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsEmpty as an -- expression, and it will be interpreted as empty. -- -- See IsNonEmpty for more information. pattern IsEmpty :: IntSet -- | O(log n). Smart constructor for an NEIntSet from a -- IntSet. Returns Nothing if the IntSet was -- originally actually empty, and Just n with an -- NEIntSet, if the IntSet was not empty. -- -- nonEmptySet and maybe empty toSet -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- -- See IsNonEmpty for a pattern synonym that lets you "match on" -- the possiblity of a IntSet being an NEIntSet. -- --
-- nonEmptySet (Data.IntSet.fromList [3,5]) == Just (fromList (3:|[5])) --nonEmptySet :: IntSet -> Maybe NEIntSet -- | O(log n). Convert a non-empty set back into a normal -- possibly-empty map, for usage with functions that expect -- IntSet. -- -- Can be thought of as "obscuring" the non-emptiness of the set in its -- type. See the IsNotEmpty pattern. -- -- nonEmptySet and maybe empty toSet -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toSet (fromList ((3,"a") :| [(5,"b")])) == Data.IntSet.fromList [(3,"a"), (5,"b")] --toSet :: NEIntSet -> IntSet -- | O(log n). A general continuation-based way to consume a -- IntSet as if it were an NEIntSet. -- withNonEmpty def f will take a IntSet. If set -- is empty, it will evaluate to def. Otherwise, a non-empty set -- NEIntSet will be fed to the function f instead. -- --
-- nonEmptySet == withNonEmpty Nothing Just --withNonEmpty :: r -> (NEIntSet -> r) -> IntSet -> r -- | O(log n). Convert a IntSet into an NEIntSet 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 insertSetMin 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" --insertSet :: Key -> IntSet -> NEIntSet -- | O(1) Convert a IntSet into an NEIntSet 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])) == False --insertSetMin :: Key -> IntSet -> NEIntSet -- | O(log n) Convert a IntSet into an NEIntSet 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. -- -- At the current moment, this is identical simply insertSet; -- 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]) --insertSetMax :: Key -> IntSet -> NEIntSet -- | O(log n). Unsafe version of nonEmptySet. Coerces a -- IntSet into an NEIntSet, but is undefined (throws a -- runtime exception when evaluation is attempted) for an empty -- IntSet. unsafeFromSet :: IntSet -> NEIntSet -- | O(1). Create a singleton set. singleton :: Key -> NEIntSet -- | O(n*log n). Create a set from a list of elements. fromList :: NonEmpty Key -> NEIntSet -- | O(n). Build a set from an ascending list in linear time. /The -- precondition (input list is ascending) is not checked./ fromAscList :: NonEmpty Key -> NEIntSet -- | O(n). Build a set from an ascending list of distinct elements -- in linear time. The precondition (input list is strictly ascending) -- is not checked. fromDistinctAscList :: NonEmpty Key -> NEIntSet -- | O(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. insert :: Key -> NEIntSet -> NEIntSet -- | O(log n). Delete an element from a set. delete :: Key -> NEIntSet -> IntSet -- | O(log n). Is the element in the set? member :: Key -> NEIntSet -> Bool -- | O(log n). Is the element not in the set? notMember :: Key -> NEIntSet -> Bool -- | O(log n). Find largest element smaller than the given one. -- --
-- lookupLT 3 (fromList (3 :| [5])) == Nothing -- lookupLT 5 (fromList (3 :| [5])) == Just 3 --lookupLT :: Key -> NEIntSet -> Maybe Key -- | O(log n). Find smallest element greater than the given one. -- --
-- lookupLT 4 (fromList (3 :| [5])) == Just 5 -- lookupLT 5 (fromList (3 :| [5])) == Nothing --lookupGT :: Key -> NEIntSet -> Maybe Key -- | O(log n). 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 --lookupLE :: Key -> NEIntSet -> Maybe Key -- | O(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 --lookupGE :: Key -> NEIntSet -> Maybe Key -- | O(1). The number of elements in the set. Guaranteed to be -- greater than zero. size :: NEIntSet -> Int -- | O(n+m). Is this a subset? (s1 `isSubsetOf` s2) tells -- whether s1 is a subset of s2. isSubsetOf :: NEIntSet -> NEIntSet -> Bool -- | O(n+m). Is this a proper subset? (ie. a subset but not equal). isProperSubsetOf :: NEIntSet -> NEIntSet -> Bool -- | O(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])) == False --disjoint :: NEIntSet -> NEIntSet -> Bool -- | O(m*log(n/m + 1)), m <= n. The union of two sets, preferring -- the first set when equal elements are encountered. union :: NEIntSet -> NEIntSet -> NEIntSet -- | The union of a non-empty list of sets unions :: Foldable1 f => f NEIntSet -> NEIntSet -- | O(m*log(n/m + 1)), m <= n. Difference of two sets. -- -- Returns a potentially empty set (IntSet) because the first set -- might be a subset of the second set, and therefore have all of its -- elements removed. difference :: NEIntSet -> NEIntSet -> IntSet -- | Same as difference. (\\) :: NEIntSet -> NEIntSet -> IntSet -- | O(m*log(n/m + 1)), m <= n. The intersection of two sets. -- -- Returns a potentially empty set (IntSet), 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:|[])). intersection :: NEIntSet -> NEIntSet -> IntSet -- | O(n). Filter all elements that satisfy the predicate. -- -- Returns a potentially empty set (IntSet) because the predicate -- might filter out all items in the original non-empty set. filter :: (Key -> Bool) -> NEIntSet -> IntSet -- | O(n). Partition the map according to a predicate. -- -- Returns a These with potentially two non-empty sets: -- --
-- 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])) --partition :: (Key -> Bool) -> NEIntSet -> These NEIntSet NEIntSet -- | O(log n). The expression (split x set) is -- potentially a These containing up to two NEIntSets 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. -- --
-- 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) == Nothing --split :: Key -> NEIntSet -> Maybe (These NEIntSet NEIntSet) -- | O(log n). The expression (splitMember x set) -- splits a set just like split but also returns member -- 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) --splitMember :: Key -> NEIntSet -> (Bool, Maybe (These NEIntSet NEIntSet)) -- | O(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. splitRoot :: NEIntSet -> NonEmpty NEIntSet -- | O(n*log n). map 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 y map :: (Key -> Key) -> NEIntSet -> NEIntSet -- | O(n). Fold the elements in the set using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . toAscList. -- -- For example, -- --
-- elemsList set = foldr (:) [] set --foldr :: (Key -> b -> b) -> b -> NEIntSet -> b -- | O(n). Fold the elements in the set using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . toAscList. -- -- For example, -- --
-- descElemsList set = foldl (flip (:)) [] set --foldl :: (a -> Key -> a) -> a -> NEIntSet -> a -- | O(n). A version of foldr that uses the value at the -- maximal value in the set as the starting value. -- -- Note that, unlike foldr1 for IntSet, this function is -- total if the input function is total. foldr1 :: (Key -> Key -> Key) -> NEIntSet -> Key -- | O(n). A version of foldl that uses the value at the -- minimal value in the set as the starting value. -- -- Note that, unlike foldl1 for IntSet, this function is -- total if the input function is total. foldl1 :: (Key -> Key -> Key) -> NEIntSet -> Key -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (Key -> b -> b) -> b -> NEIntSet -> b -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> Key -> a) -> a -> NEIntSet -> a -- | O(n). A strict version of foldr1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldr1' :: (Key -> Key -> Key) -> NEIntSet -> Key -- | O(n). A strict version of foldl1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldl1' :: (Key -> Key -> Key) -> NEIntSet -> Key -- | O(1). The minimal element of a set. Note that this is total, -- making lookupMin obsolete. It is constant-time, so has better -- asymptotics than Data.IntSet.lookupMin and -- Data.Map.findMin as well. -- --
-- findMin (fromList (5 :| [3])) == 3 --findMin :: NEIntSet -> Key -- | O(log n). The maximal key of a set Note that this is total, -- making lookupMin obsolete. -- --
-- findMax (fromList (5 :| [3])) == 5 --findMax :: NEIntSet -> Key -- | O(1). Delete the minimal element. Returns a potentially empty -- set (IntSet), 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.empty --deleteMin :: NEIntSet -> IntSet -- | O(log n). Delete the maximal element. Returns a potentially -- empty set (IntSet), 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.empty --deleteMax :: NEIntSet -> IntSet -- | O(1). Delete and find the minimal element. It is constant-time, -- so has better asymptotics that Data.IntSet.minView for -- IntSet. -- -- Note that unlike Data.IntSet.deleteFindMin for IntSet, -- this cannot ever fail, and so is a total function. However, the result -- IntSet 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]) --deleteFindMin :: NEIntSet -> (Key, IntSet) -- | O(log n). Delete and find the minimal element. -- -- Note that unlike Data.IntSet.deleteFindMax for IntSet, -- this cannot ever fail, and so is a total function. However, the result -- IntSet 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]) --deleteFindMax :: NEIntSet -> (Key, IntSet) -- | O(n). An alias of toAscList. The elements of a set in -- ascending order. elems :: NEIntSet -> NonEmpty Key -- | O(n). Convert the set to a non-empty list of elements. toList :: NEIntSet -> NonEmpty Key -- | O(n). Convert the set to an ascending non-empty list of -- elements. toAscList :: NEIntSet -> NonEmpty Key -- | O(n). Convert the set to a descending non-empty list of -- elements. toDescList :: NEIntSet -> NonEmpty Key -- | O(n). Test if the internal set structure is valid. valid :: NEIntSet -> Bool -- |
-- import qualified Data.IntMap.NonEmpty as NEIM ---- -- Note that all asmyptotics O(f(n)) in this module are actually -- O(min(W, f(n))), where W is the number of bits in an -- Int (32 or 64). That is, if f(n) is greater than -- W, all operations are constant-time. -- -- At the moment, this package does not provide a variant strict on -- values for these functions, like containers does. This is a -- planned future implementation (PR's are appreciated). For now, you can -- simulate a strict interface by manually forcing values before -- returning results. module Data.IntMap.NonEmpty -- | A non-empty (by construction) map from integer keys to values -- a. At least one key-value pair exists in an -- NEIntMap v at all times. -- -- Functions that take an NEIntMap can safely operate on it -- with the assumption that it has at least one key-value pair. -- -- Functions that return an NEIntMap 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 insert) return NEIntMap, but functions -- that might potentially return an empty map (like delete) return -- a IntMap instead. -- -- You can directly construct an NEIntMap with the API from -- Data.IntMap.NonEmpty; it's more or less the same as -- constructing a normal IntMap, except you don't have access to -- empty. There are also a few ways to construct an -- NEIntMap from a IntMap: -- --
-- myFunc :: IntMap K X -> Y -- myFunc (IsNonEmpty n) = -- here, the user provided a non-empty map, and n is the NEIntMap -- myFunc IsEmpty = -- here, the user provided an empty map. ---- -- Matching on IsNonEmpty n means that the original -- IntMap was not empty, and you have a verified-non-empty -- NEIntMap 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 IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsNonEmpty to -- convert a NEIntMap back into a IntMap, obscuring its -- non-emptiness (see toMap). pattern IsNonEmpty :: NEIntMap a -> IntMap a -- | O(1). The IsNonEmpty and IsEmpty patterns allow -- you to treat a IntMap as if it were either a -- IsNonEmpty n (where n is a NEIntMap) -- or an IsEmpty. -- -- Matching on IsEmpty means that the original IntMap was -- empty. -- -- A case statement handling both IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsEmpty as an -- expression, and it will be interpreted as empty. -- -- See IsNonEmpty for more information. pattern IsEmpty :: IntMap a -- | O(log n). Smart constructor for an NEIntMap from a -- IntMap. Returns Nothing if the IntMap was -- originally actually empty, and Just n with an -- NEIntMap, if the IntMap was not empty. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- -- See IsNonEmpty for a pattern synonym that lets you "match on" -- the possiblity of a IntMap being an NEIntMap. -- --
-- nonEmptyMap (Data.IntMap.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")])) --nonEmptyMap :: IntMap a -> Maybe (NEIntMap a) -- | O(log n). Convert a non-empty map back into a normal -- possibly-empty map, for usage with functions that expect -- IntMap. -- -- Can be thought of as "obscuring" the non-emptiness of the map in its -- type. See the IsNotEmpty pattern. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toMap (fromList ((3,"a") :| [(5,"b")])) == Data.IntMap.fromList [(3,"a"), (5,"b")] --toMap :: NEIntMap a -> IntMap a -- | O(log n). A general continuation-based way to consume a -- IntMap as if it were an NEIntMap. -- withNonEmpty def f will take a IntMap. If map -- is empty, it will evaluate to def. Otherwise, a non-empty map -- NEIntMap will be fed to the function f instead. -- --
-- nonEmptyMap == withNonEmpty Nothing Just --withNonEmpty :: r -> (NEIntMap a -> r) -> IntMap a -> r -- | O(log n). Convert a IntMap into an NEIntMap 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 insertMapMin 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" --insertMap :: Key -> a -> IntMap a -> NEIntMap a -- | O(log n). Convert a IntMap into an NEIntMap 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")]) --insertMapWith :: (a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a -- | O(log n). Convert a IntMap into an NEIntMap 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" --insertMapWithKey :: (Key -> a -> a -> a) -> Key -> a -> IntMap a -> NEIntMap a -- | O(1) Convert a IntMap into an NEIntMap 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")])) == False --insertMapMin :: Key -> a -> IntMap a -> NEIntMap a -- | O(log n) Convert a IntMap into an NEIntMap 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. -- -- At the current moment, this is identical simply insertMap; -- 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")]) --insertMapMax :: Key -> a -> IntMap a -> NEIntMap a -- | O(log n). Unsafe version of nonEmptyMap. Coerces a -- IntMap into an NEIntMap, but is undefined (throws a -- runtime exception when evaluation is attempted) for an empty -- IntMap. unsafeFromMap :: IntMap a -> NEIntMap a -- | O(1). A map with a single element. -- --
-- singleton 1 'a' == fromList ((1, 'a') :| []) -- size (singleton 1 'a') == 1 --singleton :: Key -> a -> NEIntMap a -- | O(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")]) --fromSet :: (Key -> a) -> NEIntSet -> NEIntMap a -- | O(n*log n). Build a non-empty map from a non-empty list of -- key/value pairs. See also fromAscList. If the list contains -- more than one value for the same key, the last value for the key is -- retained. -- --
-- fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")]) -- fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")]) --fromList :: NonEmpty (Key, a) -> NEIntMap a -- | O(n*log n). Build a map from a non-empty list of key/value -- pairs with a combining function. See also fromAscListWith. -- --
-- fromListWith (++) ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "ab") :| [(5, "aba")]) --fromListWith :: (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a -- | O(n*log n). Build a map from a non-empty list of key/value -- pairs with a combining function. See also fromAscListWithKey. -- --
-- 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")]) --fromListWithKey :: (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a -- | O(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")])) == False --fromAscList :: NonEmpty (Key, a) -> NEIntMap a -- | O(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"))]) == False --fromAscListWith :: (a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a -- | O(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")])) == False --fromAscListWithKey :: (Key -> a -> a -> a) -> NonEmpty (Key, a) -> NEIntMap a -- | O(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")])) == False --fromDistinctAscList :: NonEmpty (Key, a) -> NEIntMap a -- | O(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. insert is equivalent to insertWith -- const. -- -- See insertMap for a version where the first argument is a -- IntMap. -- --
-- insert 5 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'x')]) -- insert 7 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'a'), (7, 'x')]) --insert :: Key -> a -> NEIntMap a -> NEIntMap a -- | O(log n). Insert with a function, combining new value and old -- value. insertWith f key value mp will insert the pair -- (key, value) into mp if key does not exist in the map. If the -- key does exist, the function will insert the pair (key, f -- new_value old_value). -- -- See insertIntMapWith for a version where the first argument is -- a IntMap. -- --
-- insertWith (++) 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "xxxa")]) -- insertWith (++) 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) --insertWith :: (a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a -- | O(log n). Insert with a function, combining key, new value and -- old value. insertWithKey f key value mp will insert -- the pair (key, value) into mp if key does not exist in the -- map. If the key does exist, the function will insert the pair -- (key,f key new_value old_value). Note that the key passed to -- f is the same key passed to insertWithKey. -- -- See insertMapWithKey for a version where the first argument is -- a IntMap. -- --
-- let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value -- insertWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:xxx|a")]) -- insertWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) --insertWithKey :: (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> NEIntMap a -- | O(log n). Combines insert operation with old value retrieval. -- The expression (insertLookupWithKey f k x map) is a -- pair where the first element is equal to (lookup k -- map) and the second element equal to (insertWithKey f -- k x map). -- --
-- let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value -- insertLookupWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "5:xxx|a")])) -- insertLookupWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Nothing, fromList ((3, "b") :| [(5, "a"), (7, "xxx")])) ---- -- 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")])) --insertLookupWithKey :: (Key -> a -> a -> a) -> Key -> a -> NEIntMap a -> (Maybe a, NEIntMap a) -- | O(log n). Delete a key and its value from the non-empty map. A -- potentially empty map (IntMap) is returned, since this might -- delete the last item in the NEIntMap. When the key is not a -- member of the map, is equivalent to toMap. -- --
-- 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")] --delete :: Key -> NEIntMap a -> IntMap a -- | O(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")])
--
adjust :: (a -> a) -> Key -> NEIntMap a -> NEIntMap a
-- | O(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")]) --adjustWithKey :: (Key -> a -> a) -> Key -> NEIntMap a -> NEIntMap a -- | O(log n). The expression (update f k map) -- updates the value x at k (if it is in the map). If -- (f x) is Nothing, the element is deleted. If it is -- (Just y), the key k is bound to the new value -- y. -- -- Returns a potentially empty map (IntMap), because we can't know -- ahead of time if the function returns Nothing and deletes the -- final item in the NEIntMap. -- --
-- 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" --update :: (a -> Maybe a) -> Key -> NEIntMap a -> IntMap a -- | O(log n). The expression (updateWithKey f k -- map) updates the value x at k (if it is in the -- map). If (f k x) is Nothing, the element is deleted. -- If it is (Just y), the key k is bound to the -- new value y. -- -- Returns a potentially empty map (IntMap), because we can't know -- ahead of time if the function returns Nothing and deletes the -- final item in the NEIntMap. -- --
-- 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" --updateWithKey :: (Key -> a -> Maybe a) -> Key -> NEIntMap a -> IntMap a -- | 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 (IntMap) 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") --updateLookupWithKey :: (Key -> a -> Maybe a) -> Key -> NEIntMap a -> (Maybe a, IntMap a) -- | O(log n). The expression (alter f k map) alters -- the value x at k, or absence thereof. alter -- can be used to insert, delete, or update a value in a IntMap. -- In short : Data.IntMap.lookup k (alter f k m) = f -- (lookup k m). -- -- Returns a potentially empty map (IntMap), because we can't know -- ahead of time if the function returns Nothing and deletes the -- final item in the NEIntMap. -- -- See alterF' for a version that disallows deletion, and so -- therefore can return NEIntMap. -- --
-- 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")] --alter :: (Maybe a -> Maybe a) -> Key -> NEIntMap a -> IntMap a -- | O(log n). The expression (alterF f k map) -- alters the value x at k, or absence thereof. -- alterF can be used to inspect, insert, delete, or update a -- value in a IntMap. In short: Data.IntMap.lookup k <$> -- alterF f k m = f (lookup 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 IntMap, alterF can -- be considered to be a unifying generalization of lookup and -- delete; however, as a constrast, it cannot be used to implement -- insert, because it must return a IntMap instead of an -- NEIntMap (because the function might delete the final item in -- the NEIntMap). When used with trivial functors like -- Identity and Const, it is often slightly slower than -- specialized lookup and delete. However, when the functor -- is non-trivial and key comparison is not particularly cheap, it is the -- fastest way. -- -- See alterF' for a version that disallows deletion, and so -- therefore can return NEIntMap and be used to implement -- insert -- -- Note on rewrite rules: -- -- This module includes GHC rewrite rules to optimize alterF for -- the Const and Identity functors. In general, these rules -- improve performance. The sole exception is that when using -- Identity, 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 Identity type. -- -- Note: Unlike Data.IntMap.alterF for IntMap, -- alterF is not a flipped version of the at -- 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. alterF :: Functor f => (Maybe a -> f (Maybe a)) -> Key -> NEIntMap a -> f (IntMap a) -- | O(log n). Variant of alter that disallows deletion. -- Allows us to guarantee that the result is also a non-empty IntMap. alter' :: (Maybe a -> a) -> Key -> NEIntMap a -> NEIntMap a -- | O(log n). Variant of alterF that disallows deletion. -- Allows us to guarantee that the result is also a non-empty IntMap. -- -- Like Data.IntMap.alterF for IntMap, can be used to -- generalize and unify lookup and insert. However, because -- it disallows deletion, it cannot be used to implement delete. -- -- See alterF for usage information and caveats. -- -- Note: Neither alterF nor alterF' can be considered -- flipped versions of the at 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 Identity exposes an -- inconsistency in undefined behavior for Data.IntMap. -- Data.IntMap.alterF will actually maintain the original -- key in the map when used with Identity; however, -- Data.IntMap.insertWith will replace the orginal key in -- the map. The rewrite rule for alterF' has chosen to be faithful -- to Data.IntMap.insertWith, and not -- Data.IntMap.alterF, for the sake of a cleaner implementation. alterF' :: Functor f => (Maybe a -> f a) -> Key -> NEIntMap a -> f (NEIntMap a) -- | O(log n). Lookup the value at a key in the map. -- -- The function will return the corresponding value as (Just -- value), or Nothing if the key isn't in the map. -- -- 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:
--
-- -- John's currency: Just "Euro" -- Pete's currency: Nothing --lookup :: Key -> NEIntMap a -> Maybe a -- | O(log n). Find the value at a key. Returns Nothing when -- the element can not be found. -- --
-- fromList ((5, 'a') :| [(3, 'b')]) !? 1 == Nothing ---- --
-- fromList ((5, 'a') :| [(3, 'b')]) !? 5 == Just 'a' --(!?) :: NEIntMap a -> Key -> Maybe a infixl 9 !? -- | O(log n). Find the value at a key. Calls error 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' --(!) :: NEIntMap a -> Key -> a infixl 9 ! -- | O(log n). The expression (findWithDefault def k -- map) returns the value at key k or returns default value -- def when the key is not in the map. -- --
-- findWithDefault 'x' 1 (fromList ((5,'a') :| [(3,'b')])) == 'x' -- findWithDefault 'x' 5 (fromList ((5,'a') :| [(3,'b')])) == 'a' --findWithDefault :: a -> Key -> NEIntMap a -> a -- | O(log n). Is the key a member of the map? See also -- notMember. -- --
-- member 5 (fromList ((5,'a') :| [(3,'b')])) == True -- member 1 (fromList ((5,'a') :| [(3,'b')])) == False --member :: Key -> NEIntMap a -> Bool -- | O(log n). Is the key not a member of the map? See also -- member. -- --
-- notMember 5 (fromList ((5,'a') :| [(3,'b')])) == False -- notMember 1 (fromList ((5,'a') :| [(3,'b')])) == True --notMember :: Key -> NEIntMap a -> Bool -- | O(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') --lookupLT :: Key -> NEIntMap a -> Maybe (Key, a) -- | O(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')])) == Nothing --lookupGT :: Key -> NEIntMap a -> Maybe (Key, a) -- | O(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') --lookupLE :: Key -> NEIntMap a -> Maybe (Key, a) -- | O(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')])) == Nothing --lookupGE :: Key -> NEIntMap a -> Maybe (Key, a) -- | O(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')])) == 3 --size :: NEIntMap a -> Int -- | O(m*log(n/m + 1)), m <= n. The expression (union -- t1 t2) takes the left-biased union of t1 and -- t2. It prefers t1 when duplicate keys are -- encountered, i.e. (union == unionWith -- const). -- --
-- union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")]) --union :: NEIntMap a -> NEIntMap a -> NEIntMap a -- | O(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")]) --unionWith :: (a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a -- | O(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")]) --unionWithKey :: (Key -> a -> a -> a) -> NEIntMap a -> NEIntMap a -> NEIntMap a -- | The 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")]) --unions :: Foldable1 f => f (NEIntMap a) -> NEIntMap a -- | The union of a non-empty list of maps, with a combining operation: -- (unionsWith f == foldl1 (unionWith f)). -- --
-- unionsWith (++) (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])]) -- == fromList ((3, "bB3") :| [(5, "aAA3"), (7, "C")]) --unionsWith :: Foldable1 f => (a -> a -> a) -> f (NEIntMap a) -> NEIntMap a -- | O(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 (IntMap), 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" --difference :: NEIntMap a -> NEIntMap b -> IntMap a -- | Same as difference. (\\) :: NEIntMap a -> NEIntMap b -> IntMap a -- | O(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 Nothing, the element is discarded -- (proper set difference). If it returns (Just y), the -- element is updated with a new value y. -- -- Returns a potentially empty map (IntMap), in case the first map -- is a subset of the second map and the function returns Nothing -- 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" --differenceWith :: (a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a -- | O(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 Nothing, the element is discarded -- (proper set difference). If it returns (Just y), the -- element is updated with a new value y. -- -- Returns a potentially empty map (IntMap), in case the first map -- is a subset of the second map and the function returns Nothing -- 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" --differenceWithKey :: (Key -> a -> b -> Maybe a) -> NEIntMap a -> NEIntMap b -> IntMap a -- | O(m*log(n/m + 1)), m <= n. Intersection of two maps. Return -- data in the first map for the keys existing in both maps. -- (intersection m1 m2 == intersectionWith const -- m1 m2). -- -- Returns a potentially empty map (IntMap), 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" --intersection :: NEIntMap a -> NEIntMap b -> IntMap a -- | O(m*log(n/m + 1)), m <= n. Intersection with a combining -- function. -- -- Returns a potentially empty map (IntMap), 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" --intersectionWith :: (a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c -- | O(m*log(n/m + 1)), m <= n. Intersection with a combining -- function. -- -- Returns a potentially empty map (IntMap), 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" --intersectionWithKey :: (Key -> a -> b -> c) -> NEIntMap a -> NEIntMap b -> IntMap c -- | O(n). IntMap a function over all values in the map. -- --
-- map (++ "x") (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "bx") :| [(5, "ax")]) --map :: (a -> b) -> NEIntMap a -> NEIntMap b -- | O(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")]) --mapWithKey :: (Key -> a -> b) -> NEIntMap a -> NEIntMap b -- | O(n). traverseWithKey1 f m == fromList -- $ traverse1 ((k, v) -> (,) k $ f k v) -- (toList m) -- -- That is, behaves exactly like a regular traverse1 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 traverseWithKey, since works with all -- Apply, and not just Applicative. traverseWithKey1 :: Apply t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b) -- | O(n). traverseWithKey f m == fromList -- $ traverse ((k, v) -> (,) k $ f k v) -- (toList m) That is, behaves exactly like a regular -- traverse except that the traversing function also has access to -- the key associated with a value. -- -- Use traverseWithKey1 whenever possible (if your -- Applicative also has Apply instance). This version is -- provided only for types that do not have Apply instance, since -- Apply is not at the moment (and might not ever be) an official -- superclass of Applicative. -- -- WARNING: Differs from Data.IntMap.traverseWithKey, -- which traverses positive items first, then negative items. -- --
-- traverseWithKey f = unwrapApplicative . traverseWithKey1 (\k -> WrapApplicative . f k) --traverseWithKey :: Applicative t => (Key -> a -> t b) -> NEIntMap a -> t (NEIntMap b) -- | O(n). The function mapAccum 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")]))
--
mapAccum :: (a -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
-- | O(n). The function mapAccumWithKey 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")]))
--
mapAccumWithKey :: (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
-- | O(n). The function mapAccumRWithKey threads an
-- accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> Key -> b -> (a, c)) -> a -> NEIntMap b -> (a, NEIntMap c)
-- | O(n*log n). mapKeys f s is the map obtained by
-- applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the value at the
-- 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" --mapKeys :: (Key -> Key) -> NEIntMap a -> NEIntMap a -- | O(n*log n). mapKeysWith c f s is the map -- obtained by applying f to each key of s. -- -- The size of the result may be smaller if f maps two or more -- distinct keys to the same new key. In this case the associated values -- will be combined using c. 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" --mapKeysWith :: (a -> a -> a) -> (Key -> Key) -> NEIntMap a -> NEIntMap a -- | O(n). mapKeysMonotonic f s == mapKeys f -- s, but works only when f is strictly monotonic. That is, -- for any values x and y, if x < -- y then f x < f y. The precondition is -- not checked. Semi-formally, we have: -- --
-- and [x < y ==> f x < f y | x <- ls, y <- ls] -- ==> mapKeysMonotonic f s == mapKeys f s -- where ls = keys s ---- -- This means that f maps distinct original keys to distinct -- resulting keys. This function has better performance than -- mapKeys. -- -- 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")]))) == False --mapKeysMonotonic :: (Key -> Key) -> NEIntMap a -> NEIntMap a -- | O(n). Fold the values in the map using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . elems. -- --
-- elemsList map = foldr (:) [] map ---- --
-- let f a len = len + (length a) -- foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldr :: (a -> b -> b) -> b -> NEIntMap a -> b -- | O(n). Fold the values in the map using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . elems. -- --
-- elemsList = reverse . foldl (flip (:)) [] ---- --
-- let f len a = len + (length a) -- foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldl :: (a -> b -> a) -> a -> NEIntMap b -> a -- | O(n). A version of foldr that uses the value at the -- maximal key in the map as the starting value. -- -- Note that, unlike foldr1 for IntMap, this function is -- total if the input function is total. foldr1 :: (a -> a -> a) -> NEIntMap a -> a -- | O(n). A version of foldl that uses the value at the -- minimal key in the map as the starting value. -- -- Note that, unlike foldl1 for IntMap, this function is -- total if the input function is total. foldl1 :: (a -> a -> a) -> NEIntMap a -> a -- | O(n). Fold the keys and values in the map using the given -- right-associative binary operator, such that foldrWithKey f -- z == foldr (uncurry f) z . toAscList. -- -- For example, -- --
-- keysList map = foldrWithKey (\k x ks -> k:ks) [] map --foldrWithKey :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b -- | O(n). Fold the keys and values in the map using the given -- left-associative binary operator, such that foldlWithKey f -- z == foldl (\z' (kx, x) -> f z' kx x) z . -- toAscList. -- -- For example, -- --
-- keysList = reverse . foldlWithKey (\ks k x -> k:ks) [] --foldlWithKey :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a -- | O(n). Fold the keys and values in the map using the given -- semigroup, such that -- --
-- foldMapWithKey f = fold1 . mapWithKey f ---- -- WARNING: Differs from Data.IntMap.foldMapWithKey, -- which traverses positive items first, then negative items. -- -- This can be an asymptotically faster than foldrWithKey or -- foldlWithKey for some monoids. foldMapWithKey :: Semigroup m => (Key -> a -> m) -> NEIntMap a -> m -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> NEIntMap a -> b -- | O(n). A strict version of foldr1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldr1' :: (a -> a -> a) -> NEIntMap a -> a -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> NEIntMap b -> a -- | O(n). A strict version of foldl1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldl1' :: (a -> a -> a) -> NEIntMap a -> a -- | O(n). A strict version of foldrWithKey. Each application -- of the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldrWithKey' :: (Key -> a -> b -> b) -> b -> NEIntMap a -> b -- | O(n). A strict version of foldlWithKey. Each application -- of the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldlWithKey' :: (a -> Key -> b -> a) -> a -> NEIntMap b -> a -- | O(n). Return all elements of the map in the ascending order of -- their keys. -- --
-- elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])
--
elems :: NEIntMap a -> NonEmpty a
-- | O(n). Return all keys of the map in ascending order.
--
-- -- keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5]) --keys :: NEIntMap a -> NonEmpty Key -- | O(n). An alias for toAscList. Return all key/value pairs -- in the map in ascending key order. -- --
-- assocs (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")]) --assocs :: NEIntMap a -> NonEmpty (Key, a) -- | O(n). The non-empty set of all keys of the map. -- --
-- keysSet (fromList ((5,"a") :| [(3,"b")])) == Data.Set.NonEmpty.fromList (3 :| [5]) --keysSet :: NEIntMap a -> NEIntSet -- | O(n). Convert the map to a non-empty list of key/value pairs. -- --
-- toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")]) --toList :: NEIntMap a -> NonEmpty (Key, a) -- | O(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")]) --toAscList :: NEIntMap a -> NonEmpty (Key, a) -- | O(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")]) --toDescList :: NEIntMap a -> NonEmpty (Key, a) -- | O(n). Filter all values that satisfy the predicate. -- -- Returns a potentially empty map (IntMap), because we could -- potentailly filter out all items in the original NEIntMap. -- --
-- 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.empty --filter :: (a -> Bool) -> NEIntMap a -> IntMap a -- | O(n). Filter all keys/values that satisfy the predicate. -- -- Returns a potentially empty map (IntMap), because we could -- potentailly filter out all items in the original NEIntMap. -- --
-- filterWithKey (\k _ -> k > 4) (fromList ((5,"a") :| [(3,"b")])) == Data.IntMap.singleton 5 "a" --filterWithKey :: (Key -> a -> Bool) -> NEIntMap a -> IntMap a -- | O(m*log(n/m + 1)), m <= n. Restrict an NEIntMap to -- only those keys found in a Set. -- --
-- m `restrictKeys` s = filterWithKey (k _ -> k `member` s) m -- m `restrictKeys` s = m `intersection` fromSet (const ()) s --restrictKeys :: NEIntMap a -> IntSet -> IntMap a -- | O(m*log(n/m + 1)), m <= n. Remove all keys in a Set -- from an NEIntMap. -- --
-- m `withoutKeys` s = filterWithKey (k _ -> k `notMember` s) m -- m `withoutKeys` s = m `difference` fromSet (const ()) s --withoutKeys :: NEIntMap a -> IntSet -> IntMap a -- | O(n). Partition the map according to a predicate. -- -- Returns a These with potentially two non-empty maps: -- --
-- 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")])) --partition :: (a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a) -- | O(n). Partition the map according to a predicate. -- -- Returns a These with potentially two non-empty maps: -- --
-- 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")])) --partitionWithKey :: (Key -> a -> Bool) -> NEIntMap a -> These (NEIntMap a) (NEIntMap a) -- | O(n). Map values and collect the Just results. -- -- Returns a potentially empty map (IntMap), because the function -- could potentially return Nothing on all items in the -- NEIntMap. -- --
-- 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" --mapMaybe :: (a -> Maybe b) -> NEIntMap a -> IntMap b -- | O(n). Map keys/values and collect the Just results. -- -- Returns a potentially empty map (IntMap), because the function -- could potentially return Nothing on all items in the -- NEIntMap. -- --
-- 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"
--
mapMaybeWithKey :: (Key -> a -> Maybe b) -> NEIntMap a -> IntMap b
-- | O(n). Map values and separate the Left and Right
-- results.
--
-- Returns a These with potentially two non-empty maps:
--
-- -- 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")])) --mapEither :: (a -> Either b c) -> NEIntMap a -> These (NEIntMap b) (NEIntMap c) -- | O(n). Map keys/values and separate the Left and -- Right results. -- -- Returns a These with potentially two non-empty maps: -- --
-- 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")])) --mapEitherWithKey :: (Key -> a -> Either b c) -> NEIntMap a -> These (NEIntMap b) (NEIntMap c) -- | O(log n). The expression (split k map) is -- potentially a These containing up to two NEIntMaps 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. -- --
-- 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") == Nothing --split :: Key -> NEIntMap a -> Maybe (These (NEIntMap a) (NEIntMap a)) -- | O(log n). The expression (splitLookup k map) -- splits a map just like split but also returns lookup -- k map, as the first field in the These: -- --
-- 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" --splitLookup :: Key -> NEIntMap a -> These a (These (NEIntMap a) (NEIntMap a)) -- | O(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. splitRoot :: NEIntMap a -> NonEmpty (NEIntMap a) -- | O(m*log(n/m + 1)), m <= n. This function is defined as -- (isSubmapOf = isSubmapOfBy (==)). isSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool -- | O(m*log(n/m + 1)), m <= n. The expression -- (isSubmapOfBy f t1 t2) returns True if all keys -- in t1 are in tree t2, and when f returns -- True when applied to their respective values. For example, the -- following expressions are all True: -- --
-- isSubmapOfBy (==) (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 False:
--
--
-- 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)
--
isSubmapOfBy :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool
-- | O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a
-- submap but not equal). Defined as (isProperSubmapOf =
-- isProperSubmapOfBy (==)).
isProperSubmapOf :: Eq a => NEIntMap a -> NEIntMap a -> Bool
-- | O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a
-- submap but not equal). The expression (isProperSubmapOfBy f
-- m1 m2) returns True when m1 and m2 are
-- not equal, all keys in m1 are in m2, and when
-- f returns True when applied to their respective
-- values. For example, the following expressions are all True:
--
-- -- isProperSubmapOfBy (==) (singleton 1 1) (fromList ((1,1) :| [(2,2)])) -- isProperSubmapOfBy (<=) (singleton 1 1) (fromList ((1,1) :| [(2,2)])) ---- -- But the following are all False: -- --
-- 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)])) --isProperSubmapOfBy :: (a -> b -> Bool) -> NEIntMap a -> NEIntMap b -> Bool -- | O(1). The minimal key of the map. Note that this is total, -- making lookupMin obsolete. It is constant-time, so has better -- asymptotics than Data.IntMap.lookupMin and -- Data.IntMap.findMin, as well. -- --
-- findMin (fromList ((5,"a") :| [(3,"b")])) == (3,"b") --findMin :: NEIntMap a -> (Key, a) -- | O(log n). The maximal key of the map. Note that this is total, -- making lookupMin obsolete. -- --
-- findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a") --findMax :: NEIntMap a -> (Key, a) -- | O(1). Delete the minimal key. Returns a potentially empty map -- (IntMap), because we might end up deleting the final key in a -- singleton map. It is constant-time, so has better asymptotics than -- deleteMin. -- --
-- deleteMin (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.IntMap.fromList [(5,"a"), (7,"c")] -- deleteMin (singleton 5 "a") == Data.IntMap.empty --deleteMin :: NEIntMap a -> IntMap a -- | O(log n). Delete the maximal key. Returns a potentially empty -- map (IntMap), 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.empty --deleteMax :: NEIntMap a -> IntMap a -- | O(1). Delete and find the minimal key-value pair. It is -- constant-time, so has better asymptotics that -- Data.IntMap.minView for IntMap. -- -- Note that unlike Data.IntMap.deleteFindMin for IntMap, -- this cannot ever fail, and so is a total function. However, the result -- IntMap 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")]) --deleteFindMin :: NEIntMap a -> ((Key, a), IntMap a) -- | O(log n). Delete and find the minimal key-value pair. -- -- Note that unlike Data.IntMap.deleteFindMax for IntMap, -- this cannot ever fail, and so is a total function. However, the result -- IntMap 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")]) --deleteFindMax :: NEIntMap a -> ((Key, a), IntMap a) -- | O(1) if delete, O(log n) otherwise. Update the value at -- the minimal key. Returns a potentially empty map (IntMap), -- because we might end up deleting the final key in the map if the -- function returns Nothing. See adjustMin 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"
--
updateMin :: (a -> Maybe a) -> NEIntMap a -> IntMap a
-- | O(log n). Update the value at the maximal key. Returns a
-- potentially empty map (IntMap), because we might end up
-- deleting the final key in the map if the function returns
-- Nothing. See adjustMax 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"
--
updateMax :: (a -> Maybe a) -> NEIntMap a -> IntMap a
-- | O(1). A version of updateMin that disallows deletion,
-- allowing us to guarantee that the result is also non-empty.
adjustMin :: (a -> a) -> NEIntMap a -> NEIntMap a
-- | O(log n). A version of updateMax that disallows
-- deletion, allowing us to guarantee that the result is also non-empty.
adjustMax :: (a -> a) -> NEIntMap a -> NEIntMap a
-- | O(1) if delete, O(log n) otherwise. Update the value at
-- the minimal key. Returns a potentially empty map (IntMap),
-- because we might end up deleting the final key in the map if the
-- function returns Nothing. See adjustMinWithKey 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" --updateMinWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a -- | O(log n). Update the value at the maximal key. Returns a -- potentially empty map (IntMap), because we might end up -- deleting the final key in the map if the function returns -- Nothing. See adjustMaxWithKey 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" --updateMaxWithKey :: (Key -> a -> Maybe a) -> NEIntMap a -> IntMap a -- | O(1). A version of adjustMaxWithKey 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 -- updateMinWithKey in general. adjustMinWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a -- | O(log n). A version of updateMaxWithKey that disallows -- deletion, allowing us to guarantee that the result is also non-empty. adjustMaxWithKey :: (Key -> a -> a) -> NEIntMap a -> NEIntMap a -- | O(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 -- IntMap. -- -- Note that unlike Data.IntMap.minView for IntMap, this -- cannot ever fail, so doesn't need to return in a Maybe. -- However, the result IntMap 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")
--
minView :: NEIntMap a -> (a, IntMap a)
-- | O(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 IntMap, this
-- cannot ever fail, so doesn't need to return in a Maybe.
-- However, the result IntMap 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")
--
maxView :: NEIntMap a -> (a, IntMap a)
-- | O(n). Test if the internal map structure is valid.
valid :: NEIntMap a -> Bool
-- | Unsafe internal-use functions used in the implementation of
-- Data.Map.NonEmpty. These functions can potentially be used to
-- break the abstraction of NEMap and produce unsound maps, so be
-- wary!
module Data.Map.NonEmpty.Internal
-- | A non-empty (by construction) map from keys k to values
-- a. At least one key-value pair exists in an NEMap
-- k v at all times.
--
-- Functions that take an NEMap can safely operate on it
-- with the assumption that it has at least one key-value pair.
--
-- Functions that return an NEMap 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 insert) return NEMap, but functions that
-- might potentially return an empty map (like delete) return a
-- Map instead.
--
-- You can directly construct an NEMap with the API from
-- Data.Map.NonEmpty; it's more or less the same as constructing a
-- normal Map, except you don't have access to empty. There
-- are also a few ways to construct an NEMap from a Map:
--
-- -- singleton 1 'a' == fromList ((1, 'a') :| []) -- size (singleton 1 'a') == 1 --singleton :: k -> a -> NEMap k a -- | O(log n). Smart constructor for an NEMap from a -- Map. Returns Nothing if the Map was originally -- actually empty, and Just n with an NEMap, if -- the Map was not empty. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- -- See IsNonEmpty for a pattern synonym that lets you "match on" -- the possiblity of a Map being an NEMap. -- --
-- nonEmptyMap (Data.Map.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")])) --nonEmptyMap :: Map k a -> Maybe (NEMap k a) -- | O(log n). A general continuation-based way to consume a -- Map as if it were an NEMap. withNonEmpty def -- f will take a Map. If map is empty, it will evaluate to -- def. Otherwise, a non-empty map NEMap will be fed to -- the function f instead. -- --
-- nonEmptyMap == withNonEmpty Nothing Just --withNonEmpty :: r -> (NEMap k a -> r) -> Map k a -> r -- | O(n*log n). Build a non-empty map from a non-empty list of -- key/value pairs. See also fromAscList. If the list contains -- more than one value for the same key, the last value for the key is -- retained. -- --
-- fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")]) -- fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")]) --fromList :: Ord k => NonEmpty (k, a) -> NEMap k a -- | O(n). Convert the map to a non-empty list of key/value pairs. -- --
-- toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")]) --toList :: NEMap k a -> NonEmpty (k, a) -- | O(n). Map a function over all values in the map. -- --
-- map (++ "x") (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "bx") :| [(5, "ax")]) --map :: (a -> b) -> NEMap k a -> NEMap k b -- | O(log n). Insert with a function, combining new value and old -- value. insertWith f key value mp will insert the pair -- (key, value) into mp if key does not exist in the map. If the -- key does exist, the function will insert the pair (key, f -- new_value old_value). -- -- See insertMapWith for a version where the first argument is a -- Map. -- --
-- insertWith (++) 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "xxxa")]) -- insertWith (++) 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) --insertWith :: Ord k => (a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a -- | O(m*log(n/m + 1)), m <= n. The expression (union -- t1 t2) takes the left-biased union of t1 and -- t2. It prefers t1 when duplicate keys are -- encountered, i.e. (union == unionWith -- const). -- --
-- union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")]) --union :: Ord k => NEMap k a -> NEMap k a -> NEMap k a -- | The 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")]) --unions :: (Foldable1 f, Ord k) => f (NEMap k a) -> NEMap k a -- | O(n). Return all elements of the map in the ascending order of -- their keys. -- --
-- elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])
--
elems :: NEMap k a -> NonEmpty a
-- | O(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')])) == 3 --size :: NEMap k a -> Int -- | O(log n). Convert a non-empty map back into a normal -- possibly-empty map, for usage with functions that expect Map. -- -- Can be thought of as "obscuring" the non-emptiness of the map in its -- type. See the IsNotEmpty pattern. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toMap (fromList ((3,"a") :| [(5,"b")])) == Data.Map.fromList [(3,"a"), (5,"b")] --toMap :: NEMap k a -> Map k a -- | O(n). Fold the values in the map using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . elems. -- --
-- elemsList map = foldr (:) [] map ---- --
-- let f a len = len + (length a) -- foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldr :: (a -> b -> b) -> b -> NEMap k a -> b -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> NEMap k a -> b -- | O(n). A version of foldr that uses the value at the -- maximal key in the map as the starting value. -- -- Note that, unlike foldr1 for Map, this function is total -- if the input function is total. foldr1 :: (a -> a -> a) -> NEMap k a -> a -- | O(n). Fold the values in the map using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . elems. -- --
-- elemsList = reverse . foldl (flip (:)) [] ---- --
-- let f len a = len + (length a) -- foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldl :: (a -> b -> a) -> a -> NEMap k b -> a -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> NEMap k b -> a -- | O(n). A version of foldl that uses the value at the -- minimal key in the map as the starting value. -- -- Note that, unlike foldl1 for Map, this function is total -- if the input function is total. foldl1 :: (a -> a -> a) -> NEMap k a -> a -- | O(n). traverseWithKey f m == fromList -- $ traverse ((k, v) -> (,) k $ f k v) -- (toList m) That is, behaves exactly like a regular -- traverse except that the traversing function also has access to -- the key associated with a value. -- -- Use traverseWithKey1 whenever possible (if your -- Applicative also has Apply instance). This version is -- provided only for types that do not have Apply instance, since -- Apply is not at the moment (and might not ever be) an official -- superclass of Applicative. -- --
-- traverseWithKey f = unwrapApplicative . traverseWithKey1 (\k -> WrapApplicative . f k) --traverseWithKey :: Applicative t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b) -- | O(n). traverseWithKey1 f m == fromList -- $ traverse1 ((k, v) -> (,) k $ f k v) -- (toList m) -- -- That is, behaves exactly like a regular traverse1 except that -- the traversing function also has access to the key associated with a -- value. -- -- Is more general than traverseWithKey, since works with all -- Apply, and not just Applicative. traverseWithKey1 :: Apply t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b) -- | O(n). Fold the keys and values in the map using the given -- semigroup, such that -- --
-- foldMapWithKey f = fold1 . mapWithKey f ---- -- This can be an asymptotically faster than foldrWithKey or -- foldlWithKey for some monoids. foldMapWithKey :: Semigroup m => (k -> a -> m) -> NEMap k a -> m -- | O(log n). 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 Map. /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 Ord -- instance for the key type. insertMinMap :: k -> a -> Map k a -> Map k a -- | O(log n). 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 Map. /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 Ord -- instance for the key type. insertMaxMap :: k -> a -> Map k a -> Map k a -- | O(n). Test if the internal map structure is valid. valid :: Ord k => NEMap k a -> Bool instance (GHC.Classes.Eq k, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Map.NonEmpty.Internal.NEMap k a) instance (GHC.Classes.Ord k, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Map.NonEmpty.Internal.NEMap k a) instance Data.Functor.Classes.Eq2 Data.Map.NonEmpty.Internal.NEMap instance GHC.Classes.Eq k => Data.Functor.Classes.Eq1 (Data.Map.NonEmpty.Internal.NEMap k) instance Data.Functor.Classes.Ord2 Data.Map.NonEmpty.Internal.NEMap instance GHC.Classes.Ord k => Data.Functor.Classes.Ord1 (Data.Map.NonEmpty.Internal.NEMap k) instance Data.Functor.Classes.Show2 Data.Map.NonEmpty.Internal.NEMap instance GHC.Show.Show k => Data.Functor.Classes.Show1 (Data.Map.NonEmpty.Internal.NEMap k) instance (GHC.Classes.Ord k, GHC.Read.Read k) => Data.Functor.Classes.Read1 (Data.Map.NonEmpty.Internal.NEMap k) instance (GHC.Classes.Ord k, GHC.Read.Read k, GHC.Read.Read e) => GHC.Read.Read (Data.Map.NonEmpty.Internal.NEMap k e) instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.Map.NonEmpty.Internal.NEMap k a) instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Map.NonEmpty.Internal.NEMap k a) instance (Data.Data.Data k, Data.Data.Data a, GHC.Classes.Ord k) => Data.Data.Data (Data.Map.NonEmpty.Internal.NEMap k a) instance (Data.Aeson.Types.ToJSON.ToJSONKey k, Data.Aeson.Types.ToJSON.ToJSON a) => Data.Aeson.Types.ToJSON.ToJSON (Data.Map.NonEmpty.Internal.NEMap k a) instance (Data.Aeson.Types.FromJSON.FromJSONKey k, GHC.Classes.Ord k, Data.Aeson.Types.FromJSON.FromJSON a) => Data.Aeson.Types.FromJSON.FromJSON (Data.Map.NonEmpty.Internal.NEMap k a) instance GHC.Classes.Ord k => GHC.Base.Semigroup (Data.Map.NonEmpty.Internal.NEMap k a) instance GHC.Base.Functor (Data.Map.NonEmpty.Internal.NEMap k) instance Data.Foldable.Foldable (Data.Map.NonEmpty.Internal.NEMap k) instance Data.Traversable.Traversable (Data.Map.NonEmpty.Internal.NEMap k) instance Data.Semigroup.Foldable.Class.Foldable1 (Data.Map.NonEmpty.Internal.NEMap k) instance Data.Semigroup.Traversable.Class.Traversable1 (Data.Map.NonEmpty.Internal.NEMap k) instance Control.Comonad.Comonad (Data.Map.NonEmpty.Internal.NEMap k) -- | Unsafe internal-use functions used in the implementation of -- Data.Sequence.NonEmpty. These functions can potentially be used -- to break the abstraction of NESeq and produce unsound -- sequences, so be wary! module Data.Sequence.NonEmpty.Internal -- | A general-purpose non-empty (by construction) finite sequence type. -- -- Non-emptiness means that: -- --
-- nonEmptySeq == withNonEmpty Nothing Just --withNonEmpty :: r -> (NESeq a -> r) -> Seq a -> r -- | O(1). Convert a non-empty sequence back into a normal -- possibly-empty sequence, for usage with functions that expect -- Seq. -- -- Can be thought of as "obscuring" the non-emptiness of the map in its -- type. See the IsNotEmpty pattern. -- -- nonEmptySeq and maybe empty toSeq -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. toSeq :: NESeq a -> Seq a -- | <math>. A singleton sequence. singleton :: a -> NESeq a -- | <math>. The number of elements in the sequence. length :: NESeq a -> Int -- | <math>. Create a sequence from a finite list of elements. There -- is a function toNonEmpty in the opposite direction for all -- instances of the Foldable1 class, including NESeq. fromList :: NonEmpty a -> NESeq a -- | <math>. Convert a given sequence length and a function -- representing that sequence into a sequence. fromFunction :: Int -> (Int -> a) -> NESeq a -- | <math>. replicate n x is a sequence consisting of -- n copies of x. Is only defined when n is -- positive. replicate :: Int -> a -> NESeq a -- | <math>. 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, index fails -- with an error. -- --
-- xs `index` i = toList xs !! i ---- -- Caution: index 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 lookup -- or (!?). index :: NESeq a -> Int -> a -- | <math>. Add an element to the left end of a non-empty sequence. -- Mnemonic: a triangle with the single element at the pointy end. (<|) :: a -> NESeq a -> NESeq a infixr 5 <| -- | <math>. Concatenate two non-empty sequences. (><) :: NESeq a -> NESeq a -> NESeq a infixr 5 >< -- | <math>. Concatenate a non-empty sequence with a potentially -- empty sequence (Seq), to produce a guaranteed non-empty -- sequence. Mnemonic: like ><, but a pipe for the -- guarunteed non-empty side. (|><) :: NESeq a -> Seq a -> NESeq a infixr 5 |>< -- | Defined here but hidden; intended for use with RULES pragma. map :: (a -> b) -> NESeq a -> NESeq b -- | O(n). A generalization of foldMap1, -- foldMapWithIndex takes a folding function that also depends on -- the element's index, and applies it to every element in the sequence. foldMapWithIndex :: Semigroup m => (Int -> a -> m) -> NESeq a -> m -- | O(n). traverseWithIndex1 is a version of -- traverse1 that also offers access to the index of each element. traverseWithIndex1 :: Apply f => (Int -> a -> f b) -> NESeq a -> f (NESeq b) -- | <math>. Returns a sequence of all non-empty suffixes of this -- sequence, longest first. For example, -- --
-- tails (fromList (1:|[2,3])) = fromList (fromList (1:|[2,3]) :| [fromList (2:|[3]), fromList (3:|[])]) ---- -- Evaluating the <math>th suffix takes <math>, but -- evaluating every suffix in the sequence takes <math> due to -- sharing. tails :: NESeq a -> NESeq (NESeq a) -- | <math>. zip takes two sequences and returns a sequence of -- corresponding pairs. If one input is short, excess elements are -- discarded from the right end of the longer sequence. zip :: NESeq a -> NESeq b -> NESeq (a, b) -- | <math>. zipWith generalizes zip by zipping with -- the function given as the first argument, instead of a tupling -- function. For example, zipWith (+) is applied to two -- sequences to take the sequence of corresponding sums. zipWith :: (a -> b -> c) -> NESeq a -> NESeq b -> NESeq c -- | Unzip a sequence of pairs. -- --
-- unzip ps = ps `seq` (fmap fst ps) (fmap snd ps) ---- -- Example: -- --
-- unzip $ fromList ((1,"a") :| [(2,"b"), (3,"c")]) =
-- (fromList (1:|[2,3]), fromList ("a":|["b","c"]))
--
--
-- See the note about efficiency at unzipWith.
unzip :: NESeq (a, b) -> (NESeq a, NESeq b)
-- | CPP for new functions not in old containers
-- ---------------------------------------------
--
-- Compatibility layer for sortOn.
sortOnSeq :: Ord b => (a -> b) -> Seq a -> Seq a
-- | Compatibility layer for unstableSortOn.
unstableSortOnSeq :: Ord b => (a -> b) -> Seq a -> Seq a
-- | Compatibility layer for unzip.
unzipSeq :: Seq (a, b) -> (Seq a, Seq b)
-- | Compatibility layer for unzipWith.
unzipWithSeq :: (a -> (b, c)) -> Seq a -> (Seq b, Seq c)
instance Data.Traversable.Traversable Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Show.Show a => GHC.Show.Show (Data.Sequence.NonEmpty.Internal.NESeq a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Sequence.NonEmpty.Internal.NESeq a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Sequence.NonEmpty.Internal.NESeq a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Functor.Classes.Show1 Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Classes.Read1 Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Classes.Eq1 Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Classes.Ord1 Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Data.Data a => Data.Data.Data (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Aeson.Types.ToJSON.ToJSON a => Data.Aeson.Types.ToJSON.ToJSON (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Aeson.Types.FromJSON.FromJSON a => Data.Aeson.Types.FromJSON.FromJSON (Data.Sequence.NonEmpty.Internal.NESeq a)
instance GHC.Base.Semigroup (Data.Sequence.NonEmpty.Internal.NESeq a)
instance GHC.Base.Functor Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Bind.Class.Apply Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Base.Applicative Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Alt.Alt Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Bind.Class.Bind Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Base.Monad Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Extend.Extend Data.Sequence.NonEmpty.Internal.NESeq
instance Control.Comonad.Comonad Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Foldable.Foldable Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Semigroup.Foldable.Class.Foldable1 Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Semigroup.Traversable.Class.Traversable1 Data.Sequence.NonEmpty.Internal.NESeq
instance Control.Monad.Zip.MonadZip Data.Sequence.NonEmpty.Internal.NESeq
instance Control.Monad.Fix.MonadFix Data.Sequence.NonEmpty.Internal.NESeq
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Sequence.NonEmpty.Internal.NESeq a)
-- | -- import qualified Data.Sequence.NonEmpty as NESeq --module Data.Sequence.NonEmpty -- | A general-purpose non-empty (by construction) finite sequence type. -- -- Non-emptiness means that: -- --
-- safeHead :: Seq Int -> Int -- safeHead (IsNonEmpty (x :<|| _)) = x -- here, user provided a non-empty sequence, and n is the NESeq -- safeHead IsEmpty = 0 -- here the user provided an empty sequence ---- -- Matching on IsNonEmpty n means that the original -- Seq was not empty, and you have a verified-non-empty -- NESeq n to use. -- -- A case statement handling both IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsNonEmpty to -- convert a NESeq back into a Seq, obscuring its -- non-emptiness (see toSeq). pattern IsNonEmpty :: NESeq a -> Seq a -- | O(1). The IsNonEmpty and IsEmpty patterns allow -- you to treat a Seq as if it were either a IsNonEmpty -- n (where n is a NESeq) or an IsEmpty. -- -- Matching on IsEmpty means that the original Seq was -- empty. -- -- A case statement handling both IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsEmpty as an -- expression, and it will be interpreted as empty. -- -- See IsNonEmpty for more information. pattern IsEmpty :: Seq a -- | O(1). Smart constructor for an NESeq from a Seq. -- Returns Nothing if the Seq was originally actually -- empty, and Just n with an NESeq, if the -- Seq was not empty. -- -- nonEmptySeq and maybe empty toSeq -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- -- See IsNonEmpty for a pattern synonym that lets you "match on" -- the possiblity of a Seq being an NESeq. -- --
-- nonEmptySeq (Data.Sequence.fromList [1,2,3]) == Just (fromList (1) :| [2,3]) --nonEmptySeq :: Seq a -> Maybe (NESeq a) -- | O(1). Convert a non-empty sequence back into a normal -- possibly-empty sequence, for usage with functions that expect -- Seq. -- -- Can be thought of as "obscuring" the non-emptiness of the map in its -- type. See the IsNotEmpty pattern. -- -- nonEmptySeq and maybe empty toSeq -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. toSeq :: NESeq a -> Seq a -- | O(log n). A general continuation-based way to consume a -- Seq as if it were an NESeq. withNonEmpty def -- f will take a Seq. If map is empty, it will evaluate to -- def. Otherwise, a non-empty map NESeq will be fed to -- the function f instead. -- --
-- nonEmptySeq == withNonEmpty Nothing Just --withNonEmpty :: r -> (NESeq a -> r) -> Seq a -> r -- | O(1). Unsafe version of nonEmptySeq. Coerces a -- Seq into an NESeq, but is undefined (throws a runtime -- exception when evaluation is attempted) for an empty Seq. unsafeFromSeq :: Seq a -> NESeq a -- | Turn a Seq into a guarantted non-empty NESeq by adding -- an element at a given index. -- --
-- insertSeqAt 1 0 (Data.Sequence.fromList [1,2,3]) == fromList (1 :| [0,2,3]) --insertSeqAt :: Int -> a -> Seq a -> NESeq a -- | <math>. A singleton sequence. singleton :: a -> NESeq a -- | <math>. Add an element to the left end of a non-empty sequence. -- Mnemonic: a triangle with the single element at the pointy end. (<|) :: a -> NESeq a -> NESeq a infixr 5 <| -- | <math>. Add an element to the right end of a non-empty sequence. -- Mnemonic: a triangle with the single element at the pointy end. (|>) :: NESeq a -> a -> NESeq a infixl 5 |> -- | <math>. Concatenate two non-empty sequences. (><) :: NESeq a -> NESeq a -> NESeq a infixr 5 >< -- | <math>. Concatenate a non-empty sequence with a potentially -- empty sequence (Seq), to produce a guaranteed non-empty -- sequence. Mnemonic: like ><, but a pipe for the -- guarunteed non-empty side. (|><) :: NESeq a -> Seq a -> NESeq a infixr 5 |>< -- | <math>. Concatenate a non-empty sequence with a potentially -- empty sequence (Seq), to produce a guaranteed non-empty -- sequence. Mnemonic: like ><, but a pipe for the -- guarunteed non-empty side. (><|) :: Seq a -> NESeq a -> NESeq a infixr 5 ><| -- | <math>. Create a sequence from a finite list of elements. There -- is a function toNonEmpty in the opposite direction for all -- instances of the Foldable1 class, including NESeq. fromList :: NonEmpty a -> NESeq a -- | <math>. Convert a given sequence length and a function -- representing that sequence into a sequence. fromFunction :: Int -> (Int -> a) -> NESeq a -- | <math>. replicate n x is a sequence consisting of -- n copies of x. Is only defined when n is -- positive. replicate :: Int -> a -> NESeq a -- | replicateA is an Applicative version of -- replicate, and makes ( O(log n) ) calls to liftA2 and -- pure. Is only defined when n is positive. -- --
-- replicateA n x = sequenceA (replicate n x) ---- -- Is a more restrictive version of replicateA1. -- replicateA1 should be preferred whenever possible. replicateA :: Applicative f => Int -> f a -> f (NESeq a) -- | replicateA is an Apply version of replicate, and -- makes ( O(log n) ) calls to <.>. Is only defined when -- n is positive. -- --
-- replicateA1 n x = sequence1 (replicate n x) --replicateA1 :: Apply f => Int -> f a -> f (NESeq a) -- | An alias of replicateA. replicateM :: Applicative m => Int -> m a -> m (NESeq a) -- | O(log k). cycleTaking 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 . toList --cycleTaking :: Int -> NESeq a -> NESeq a -- | <math>. 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))))) --iterateN :: Int -> (a -> a) -> a -> NESeq a -- | Builds 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. unfoldr :: (b -> (a, Maybe b)) -> b -> NESeq a -- | unfoldl f x is equivalent to reverse -- (unfoldr (fmap swap . f) x). unfoldl :: (b -> (Maybe b, a)) -> b -> NESeq a -- | O(1). Retrieve the left-most item in a non-empty sequence. Note -- that this function is total. head :: NESeq a -> a -- | O(1). Delete the left-most item in a non-empty sequence. -- Returns a potentially empty sequence (Seq) in the case that the -- original NESeq contained only a single element. Note that this -- function is total. tail :: NESeq a -> Seq a -- | O(1). Retrieve the right-most item in a non-empty sequence. -- Note that this function is total. last :: NESeq a -> a -- | O(1). Delete the right-most item in a non-empty sequence. -- Returns a potentially empty sequence (Seq) in the case that the -- original NESeq contained only a single element. Note that this -- function is total. init :: NESeq a -> Seq a -- | <math>. The number of elements in the sequence. length :: NESeq a -> Int -- | scanl is similar to foldl, 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, ...] --scanl :: (a -> b -> a) -> a -> NESeq b -> NESeq a -- | scanl1 is a variant of scanl that has no starting value -- argument: -- --
-- scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...] --scanl1 :: (a -> a -> a) -> NESeq a -> NESeq a -- | scanr is the right-to-left dual of scanl. scanr :: (a -> b -> b) -> b -> NESeq a -> NESeq b -- | scanr1 is a variant of scanr that has no starting value -- argument. scanr1 :: (a -> a -> a) -> NESeq a -> NESeq a -- | <math>. Returns a sequence of all non-empty suffixes of this -- sequence, longest first. For example, -- --
-- tails (fromList (1:|[2,3])) = fromList (fromList (1:|[2,3]) :| [fromList (2:|[3]), fromList (3:|[])]) ---- -- Evaluating the <math>th suffix takes <math>, but -- evaluating every suffix in the sequence takes <math> due to -- sharing. tails :: NESeq a -> NESeq (NESeq a) -- | <math>. 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 <math>th prefix takes <math>, but -- evaluating every prefix in the sequence takes <math> due to -- sharing. inits :: NESeq a -> NESeq (NESeq a) -- | <math>. 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 -- <math> (for <math>) to <math> (for <math>). -- The true bound is more like <math> chunksOf :: Int -> NESeq a -> NESeq (NESeq a) -- | <math> where <math> is the prefix length. -- takeWhileL, applied to a predicate p and a sequence -- xs, returns the longest prefix (possibly empty) of -- xs of elements that satisfy p. -- -- Returns a possibly empty sequence (Seq) in the case that the -- predicate fails on the first item. takeWhileL :: (a -> Bool) -> NESeq a -> Seq a -- | <math> where <math> is the suffix length. -- takeWhileR, applied to a predicate p and a sequence -- xs, returns the longest suffix (possibly empty) of -- xs of elements that satisfy p. -- -- Returns a possibly empty sequence (Seq) in the case that the -- predicate fails on the first item. -- -- takeWhileR p xs is equivalent to reverse -- (takeWhileL p (reverse xs)). takeWhileR :: (a -> Bool) -> NESeq a -> Seq a -- | <math> where <math> is the prefix length. -- dropWhileL p xs returns the suffix remaining after -- takeWhileL p xs. -- -- Returns a possibly empty sequence (Seq) in the case that the -- predicate passes for all items. dropWhileL :: (a -> Bool) -> NESeq a -> Seq a -- | <math> where <math> is the suffix length. -- dropWhileR p xs returns the prefix remaining after -- takeWhileR p xs. -- -- Returns a possibly empty sequence (Seq) in the case that the -- predicate passes for all items. -- -- dropWhileR p xs is equivalent to reverse -- (dropWhileL p (reverse xs)). dropWhileR :: (a -> Bool) -> NESeq a -> Seq a -- | <math> where <math> is the prefix length. spanl, -- applied to a predicate p and a sequence xs, returns -- a These based on the point where the predicate fails: -- --
-- sortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator"])
--
--
-- If, instead, sortBy had been used, length would be
-- evaluated on every comparison, giving <math> evaluations, rather
-- than <math>.
--
-- If f is very cheap (for example a record selector, or
-- fst), sortBy (compare `on` f)
-- will be faster than sortOn f.
sortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a
-- | <math>. unstableSort sorts the specified NESeq by
-- the natural ordering of its elements, but the sort is not stable. This
-- algorithm is frequently faster and uses less memory than sort.
unstableSort :: Ord a => NESeq a -> NESeq a
-- | <math>. A generalization of unstableSort,
-- unstableSortBy takes an arbitrary comparator and sorts the
-- specified sequence. The sort is not stable. This algorithm is
-- frequently faster and uses less memory than sortBy.
unstableSortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a
-- | <math>. unstableSortOn sorts the specified NESeq
-- by comparing the results of a key function applied to each element.
-- unstableSortOn f is equivalent to
-- unstableSortBy (compare `on` f), 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 unstableSortOn might be to sort a
-- NESeq of strings according to their length.
--
--
-- unstableSortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator]")
--
--
-- If, instead, unstableSortBy had been used, length would
-- be evaluated on every comparison, giving <math> evaluations,
-- rather than <math>.
--
-- If f is very cheap (for example a record selector, or
-- fst), unstableSortBy (compare `on`
-- f) will be faster than unstableSortOn f.
unstableSortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a
-- | <math>. The element at the specified position, counting from 0.
-- If the specified position is negative or at least the length of the
-- sequence, lookup returns Nothing.
--
-- Unlike index, this can be used to retrieve an element without
-- forcing it.
lookup :: Int -> NESeq a -> Maybe a
-- | <math>. A flipped, infix version of lookup.
(!?) :: NESeq a -> Int -> Maybe a
-- | <math>. 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, index fails
-- with an error.
--
-- -- xs `index` i = toList xs !! i ---- -- Caution: index 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 lookup -- or (!?). index :: NESeq a -> Int -> a -- | <math>. Update the element at the specified position. If the -- position is out of range, the original sequence is returned. -- adjust can lead to poor performance and even memory leaks, -- because it does not force the new value before installing it in the -- sequence. adjust' should usually be preferred. adjust :: (a -> a) -> Int -> NESeq a -> NESeq a -- | <math>. 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 --adjust' :: (a -> a) -> Int -> NESeq a -> NESeq a -- | <math>. Replace the element at the specified position. If the -- position is out of range, the original sequence is returned. update :: Int -> a -> NESeq a -> NESeq a -- | <math>. The first i elements of a sequence. If -- i is negative, take i s yields the empty -- sequence. If the sequence contains fewer than i elements, the -- whole sequence is returned. take :: Int -> NESeq a -> Seq a -- | <math>. Elements of a sequence after the first i. If -- i is negative, drop i s yields the whole -- sequence. If the sequence contains fewer than i elements, the -- empty sequence is returned. drop :: Int -> NESeq a -> Seq a -- | <math>. insertAt 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]) ---- --
-- insertAt i x xs = take i xs >< singleton x >< drop i xs --insertAt :: Int -> a -> NESeq a -> NESeq a -- | <math>. 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] --deleteAt :: Int -> NESeq a -> Seq a -- | <math>. Split a sequence at a given position. -- --
-- 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] --intersperse :: a -> NESeq a -> NESeq a -- | <math>. zip takes two sequences and returns a sequence of -- corresponding pairs. If one input is short, excess elements are -- discarded from the right end of the longer sequence. zip :: NESeq a -> NESeq b -> NESeq (a, b) -- | <math>. zipWith generalizes zip by zipping with -- the function given as the first argument, instead of a tupling -- function. For example, zipWith (+) is applied to two -- sequences to take the sequence of corresponding sums. zipWith :: (a -> b -> c) -> NESeq a -> NESeq b -> NESeq c -- | <math>. zip3 takes three sequences and returns a sequence -- of triples, analogous to zip. zip3 :: NESeq a -> NESeq b -> NESeq c -> NESeq (a, b, c) -- | <math>. zipWith3 takes a function which combines three -- elements, as well as three sequences and returns a sequence of their -- point-wise combinations, analogous to zipWith. zipWith3 :: (a -> b -> c -> d) -> NESeq a -> NESeq b -> NESeq c -> NESeq d -- | <math>. zip4 takes four sequences and returns a sequence -- of quadruples, analogous to zip. zip4 :: NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq (a, b, c, d) -- | <math>. zipWith4 takes a function which combines four -- elements, as well as four sequences and returns a sequence of their -- point-wise combinations, analogous to zipWith. zipWith4 :: (a -> b -> c -> d -> e) -> NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq e -- | Unzip a sequence of pairs. -- --
-- unzip ps = ps `seq` (fmap fst ps) (fmap snd ps) ---- -- Example: -- --
-- unzip $ fromList ((1,"a") :| [(2,"b"), (3,"c")]) =
-- (fromList (1:|[2,3]), fromList ("a":|["b","c"]))
--
--
-- See the note about efficiency at unzipWith.
unzip :: NESeq (a, b) -> (NESeq a, NESeq b)
-- | <math>. Unzip a sequence using a function to divide elements.
--
-- -- unzipWith f xs == unzip (fmap f xs) ---- -- Efficiency note: -- -- unzipWith produces its two results in lockstep. If you -- calculate unzipWith f xs and fully force either 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 -- fmap to extract each component sequence. unzipWith :: (a -> (b, c)) -> NESeq a -> (NESeq b, NESeq c) -- | Unsafe internal-use functions used in the implementation of -- Data.Set.NonEmpty. These functions can potentially be used to -- break the abstraction of NESet and produce unsound sets, so be -- wary! module Data.Set.NonEmpty.Internal -- | A non-empty (by construction) set of values a. At least one -- value exists in an NESet a at all times. -- -- Functions that take an NESet can safely operate on it -- with the assumption that it has at least one item. -- -- Functions that return an NESet 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 insert) return NESet, but functions that -- might potentially return an empty map (like delete) return a -- Set instead. -- -- You can directly construct an NESet with the API from -- Data.Set.NonEmpty; it's more or less the same as constructing a -- normal Set, except you don't have access to empty. There -- are also a few ways to construct an NESet from a Set: -- --
-- nonEmptySet (Data.Set.fromList [3,5]) == Just (fromList (3:|[5])) --nonEmptySet :: Set a -> Maybe (NESet a) -- | O(log n). A general continuation-based way to consume a -- Set as if it were an NESet. withNonEmpty def -- f will take a Set. If set is empty, it will evaluate to -- def. Otherwise, a non-empty set NESet will be fed to -- the function f instead. -- --
-- nonEmptySet == withNonEmpty Nothing Just --withNonEmpty :: r -> (NESet a -> r) -> Set a -> r -- | O(log n). Convert a non-empty set back into a normal -- possibly-empty map, for usage with functions that expect Set. -- -- Can be thought of as "obscuring" the non-emptiness of the set in its -- type. See the IsNotEmpty pattern. -- -- nonEmptySet and maybe empty toSet -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toSet (fromList ((3,"a") :| [(5,"b")])) == Data.Set.fromList [(3,"a"), (5,"b")] --toSet :: NESet a -> Set a -- | O(1). Create a singleton set. singleton :: a -> NESet a -- | O(n*log n). Create a set from a list of elements. fromList :: Ord a => NonEmpty a -> NESet a -- | O(n). Convert the set to a non-empty list of elements. toList :: NESet a -> NonEmpty a -- | O(1). The number of elements in the set. Guaranteed to be -- greater than zero. size :: NESet a -> Int -- | O(m*log(n/m + 1)), m <= n. The union of two sets, preferring -- the first set when equal elements are encountered. union :: Ord a => NESet a -> NESet a -> NESet a -- | The union of a non-empty list of sets unions :: (Foldable1 f, Ord a) => f (NESet a) -> NESet a -- | O(n). Fold the elements in the set using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . toAscList. -- -- For example, -- --
-- elemsList set = foldr (:) [] set --foldr :: (a -> b -> b) -> b -> NESet a -> b -- | O(n). Fold the elements in the set using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . toAscList. -- -- For example, -- --
-- descElemsList set = foldl (flip (:)) [] set --foldl :: (a -> b -> a) -> a -> NESet b -> a -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> NESet a -> b -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> NESet b -> a -- | Used for cartesianProduct newtype MergeNESet a MergeNESet :: NESet a -> MergeNESet a [getMergeNESet] :: MergeNESet a -> NESet a -- | Unsafely merge two disjoint sets. Only legal if all items in the first -- set are less than all items in the second set merge :: NESet a -> NESet a -> NESet a -- | O(n). Test if the internal set structure is valid. valid :: Ord a => NESet a -> Bool -- | O(log n). Insert new value into a set where values are -- strictly greater than the new values That is, the new value -- must be strictly less than all values present in the -- Set. /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 Ord -- instance for the value type. insertMinSet :: a -> Set a -> Set a -- | O(log n). Insert new value into a set where values are -- /strictly less than the new value. That is, the new value must be -- strictly greater than all values present in the Set. -- 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 Ord -- instance for the value type. insertMaxSet :: a -> Set a -> Set a -- | CPP for new functions not in old containers -- --------------------------------------------- -- -- Comptability layer for disjoint. disjointSet :: Ord a => Set a -> Set a -> Bool -- | Comptability layer for powerSet. powerSetSet :: Set a -> Set (Set a) -- | Comptability layer for disjointUnion. disjointUnionSet :: Set a -> Set b -> Set (Either a b) -- | Comptability layer for cartesianProduct. cartesianProductSet :: Set a -> Set b -> Set (a, b) instance GHC.Base.Semigroup (Data.Set.NonEmpty.Internal.MergeNESet a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Set.NonEmpty.Internal.NESet a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Set.NonEmpty.Internal.NESet a) instance GHC.Show.Show a => GHC.Show.Show (Data.Set.NonEmpty.Internal.NESet a) instance (GHC.Read.Read a, GHC.Classes.Ord a) => GHC.Read.Read (Data.Set.NonEmpty.Internal.NESet a) instance Data.Functor.Classes.Eq1 Data.Set.NonEmpty.Internal.NESet instance Data.Functor.Classes.Ord1 Data.Set.NonEmpty.Internal.NESet instance Data.Functor.Classes.Show1 Data.Set.NonEmpty.Internal.NESet instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Set.NonEmpty.Internal.NESet a) instance (Data.Data.Data a, GHC.Classes.Ord a) => Data.Data.Data (Data.Set.NonEmpty.Internal.NESet a) instance Data.Aeson.Types.ToJSON.ToJSON a => Data.Aeson.Types.ToJSON.ToJSON (Data.Set.NonEmpty.Internal.NESet a) instance (Data.Aeson.Types.FromJSON.FromJSON a, GHC.Classes.Ord a) => Data.Aeson.Types.FromJSON.FromJSON (Data.Set.NonEmpty.Internal.NESet a) instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.Set.NonEmpty.Internal.NESet a) instance Data.Foldable.Foldable Data.Set.NonEmpty.Internal.NESet instance Data.Semigroup.Foldable.Class.Foldable1 Data.Set.NonEmpty.Internal.NESet -- |
-- import qualified Data.Set.NonEmpty as NES --module Data.Set.NonEmpty -- | A non-empty (by construction) set of values a. At least one -- value exists in an NESet a at all times. -- -- Functions that take an NESet can safely operate on it -- with the assumption that it has at least one item. -- -- Functions that return an NESet 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 insert) return NESet, but functions that -- might potentially return an empty map (like delete) return a -- Set instead. -- -- You can directly construct an NESet with the API from -- Data.Set.NonEmpty; it's more or less the same as constructing a -- normal Set, except you don't have access to empty. There -- are also a few ways to construct an NESet from a Set: -- --
-- myFunc :: Set X -> Y -- myFunc (IsNonEmpty n) = -- here, the user provided a non-empty set, and n is the NESet -- myFunc IsEmpty = -- here, the user provided an empty set ---- -- Matching on IsNonEmpty n means that the original -- Set was not empty, and you have a verified-non-empty -- NESet 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 IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsNonEmpty to -- convert a NESet back into a Set, obscuring its -- non-emptiness (see toSet). pattern IsNonEmpty :: NESet a -> Set a -- | O(1). The IsNonEmpty and IsEmpty patterns allow -- you to treat a Set as if it were either a IsNonEmpty -- n (where n is a NESet) or an IsEmpty. -- -- Matching on IsEmpty means that the original Set was -- empty. -- -- A case statement handling both IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsEmpty as an -- expression, and it will be interpreted as empty. -- -- See IsNonEmpty for more information. pattern IsEmpty :: Set a -- | O(log n). Smart constructor for an NESet from a -- Set. Returns Nothing if the Set was originally -- actually empty, and Just n with an NESet, if -- the Set was not empty. -- -- nonEmptySet and maybe empty toSet -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- -- See IsNonEmpty for a pattern synonym that lets you "match on" -- the possiblity of a Set being an NESet. -- --
-- nonEmptySet (Data.Set.fromList [3,5]) == Just (fromList (3:|[5])) --nonEmptySet :: Set a -> Maybe (NESet a) -- | O(log n). Convert a non-empty set back into a normal -- possibly-empty map, for usage with functions that expect Set. -- -- Can be thought of as "obscuring" the non-emptiness of the set in its -- type. See the IsNotEmpty pattern. -- -- nonEmptySet and maybe empty toSet -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toSet (fromList ((3,"a") :| [(5,"b")])) == Data.Set.fromList [(3,"a"), (5,"b")] --toSet :: NESet a -> Set a -- | O(log n). A general continuation-based way to consume a -- Set as if it were an NESet. withNonEmpty def -- f will take a Set. If set is empty, it will evaluate to -- def. Otherwise, a non-empty set NESet will be fed to -- the function f instead. -- --
-- nonEmptySet == withNonEmpty Nothing Just --withNonEmpty :: r -> (NESet a -> r) -> Set a -> r -- | O(log n). Convert a Set into an NESet 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 insertSetMin 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" --insertSet :: Ord a => a -> Set a -> NESet a -- | O(1) Convert a Set into an NESet 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])) == False --insertSetMin :: a -> Set a -> NESet a -- | O(log n) Convert a Set into an NESet 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 insertSet, it saves a -- constant factor for key comparison (so may be helpful if comparison is -- expensive) and also does not require an Ord 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])) == False --insertSetMax :: a -> Set a -> NESet a -- | O(log n). Unsafe version of nonEmptySet. Coerces a -- Set into an NESet, but is undefined (throws a runtime -- exception when evaluation is attempted) for an empty Set. unsafeFromSet :: Set a -> NESet a -- | O(1). Create a singleton set. singleton :: a -> NESet a -- | O(n*log n). Create a set from a list of elements. fromList :: Ord a => NonEmpty a -> NESet a -- | O(n). Build a set from an ascending list in linear time. /The -- precondition (input list is ascending) is not checked./ fromAscList :: Eq a => NonEmpty a -> NESet a -- | O(n). Build a set from a descending list in linear time. The -- precondition (input list is descending) is not checked. fromDescList :: Eq a => NonEmpty a -> NESet a -- | O(n). Build a set from an ascending list of distinct elements -- in linear time. The precondition (input list is strictly ascending) -- is not checked. fromDistinctAscList :: NonEmpty a -> NESet a -- | O(n). Build a set from a descending list of distinct elements -- in linear time. The precondition (input list is strictly -- descending) is not checked. fromDistinctDescList :: NonEmpty a -> NESet a -- | Calculate the power set of a non-empty: the set of all its (non-empty) -- subsets. -- --
-- t `member` powerSet s == t `isSubsetOf` 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. powerSet :: forall a. () => NESet a -> NESet (NESet a) -- | O(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. insert :: Ord a => a -> NESet a -> NESet a -- | O(log n). Delete an element from a set. delete :: Ord a => a -> NESet a -> Set a -- | O(log n). Is the element in the set? member :: Ord a => a -> NESet a -> Bool -- | O(log n). Is the element not in the set? notMember :: Ord a => a -> NESet a -> Bool -- | O(log n). Find largest element smaller than the given one. -- --
-- lookupLT 3 (fromList (3 :| [5])) == Nothing -- lookupLT 5 (fromList (3 :| [5])) == Just 3 --lookupLT :: Ord a => a -> NESet a -> Maybe a -- | O(log n). Find smallest element greater than the given one. -- --
-- lookupLT 4 (fromList (3 :| [5])) == Just 5 -- lookupLT 5 (fromList (3 :| [5])) == Nothing --lookupGT :: Ord a => a -> NESet a -> Maybe a -- | O(log n). 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 --lookupLE :: Ord a => a -> NESet a -> Maybe a -- | O(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 --lookupGE :: Ord a => a -> NESet a -> Maybe a -- | O(1). The number of elements in the set. Guaranteed to be -- greater than zero. size :: NESet a -> Int -- | O(n+m). Is this a subset? (s1 `isSubsetOf` s2) tells -- whether s1 is a subset of s2. isSubsetOf :: Ord a => NESet a -> NESet a -> Bool -- | O(n+m). Is this a proper subset? (ie. a subset but not equal). isProperSubsetOf :: Ord a => NESet a -> NESet a -> Bool -- | O(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])) == False --disjoint :: Ord a => NESet a -> NESet a -> Bool -- | O(m*log(n/m + 1)), m <= n. The union of two sets, preferring -- the first set when equal elements are encountered. union :: Ord a => NESet a -> NESet a -> NESet a -- | The union of a non-empty list of sets unions :: (Foldable1 f, Ord a) => f (NESet a) -> NESet a -- | O(m*log(n/m + 1)), m <= n. Difference of two sets. -- -- Returns a potentially empty set (Set) because the first set -- might be a subset of the second set, and therefore have all of its -- elements removed. difference :: Ord a => NESet a -> NESet a -> Set a -- | Same as difference. (\\) :: Ord a => NESet a -> NESet a -> Set a -- | O(m*log(n/m + 1)), m <= n. The intersection of two sets. -- -- Returns a potentially empty set (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:|[])). intersection :: Ord a => NESet a -> NESet a -> Set a -- | 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')])
--
cartesianProduct :: NESet a -> NESet b -> NESet (a, b)
-- | Calculate the disjoint union of two sets.
--
-- -- disjointUnion xs ys = map Left xs `union` map Right ys ---- -- Example: -- --
-- disjointUnion (fromList (1:|[2])) (fromList ("hi":|["bye"])) =
-- fromList (Left 1 :| [Left 2, Right "hi", Right "bye"])
--
disjointUnion :: NESet a -> NESet b -> NESet (Either a b)
-- | O(n). Filter all elements that satisfy the predicate.
--
-- Returns a potentially empty set (Set) because the predicate
-- might filter out all items in the original non-empty set.
filter :: (a -> Bool) -> NESet a -> Set a
-- | O(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 spanAntitone.
--
-- Returns a potentially empty set (Set) because the predicate
-- might fail on the first input.
--
-- -- takeWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.takeWhile p . toList -- takeWhileAntitone p = filter p --takeWhileAntitone :: (a -> Bool) -> NESet a -> Set a -- | O(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 spanAntitone. -- -- Returns a potentially empty set (Set) because the predicate -- might be true for all items. -- --
-- dropWhileAntitone p = Data.Set.fromDistinctAscList . Data.List.NonEmpty.dropWhile p . toList -- dropWhileAntitone p = filter (not . p) --dropWhileAntitone :: (a -> Bool) -> NESet a -> Set a -- | O(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 These with potentially two non-empty sets: -- --
-- 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). spanAntitone :: (a -> Bool) -> NESet a -> These (NESet a) (NESet a) -- | O(n). Partition the map according to a predicate. -- -- Returns a These with potentially two non-empty sets: -- --
-- 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])) --partition :: (a -> Bool) -> NESet a -> These (NESet a) (NESet a) -- | O(log n). The expression (split x set) is -- potentially a These containing up to two NESets 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. -- --
-- 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) == Nothing --split :: Ord a => a -> NESet a -> Maybe (These (NESet a) (NESet a)) -- | O(log n). The expression (splitMember x set) -- splits a set just like split but also returns member -- 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) --splitMember :: Ord a => a -> NESet a -> (Bool, Maybe (These (NESet a) (NESet a))) -- | O(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. splitRoot :: NESet a -> NonEmpty (NESet a) -- | O(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 size 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]))) == False --lookupIndex :: Ord a => a -> NESet a -> Maybe Int -- | O(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 size of the -- set. Calls error when the element is not a member 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 set --findIndex :: Ord a => a -> NESet a -> Int -- | O(log n). Retrieve an element by its index, i.e. by its -- zero-based index in the sorted sequence of elements. If the -- index is out of range (less than zero, greater or equal to -- size of the set), error is called. -- --
-- elemAt 0 (fromList (5:|[3])) == 3 -- elemAt 1 (fromList (5:|[3])) == 5 -- elemAt 2 (fromList (5:|[3])) Error: index out of range --elemAt :: Int -> NESet a -> a -- | O(log n). Delete the element at index, i.e. by its -- zero-based index in the sorted sequence of elements. If the -- index is out of range (less than zero, greater or equal to -- size of the set), error is called. -- -- Returns a potentially empty set (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 range --deleteAt :: Int -> NESet a -> Set a -- | Take a given number of elements in order, beginning with the smallest -- ones. -- -- Returns a potentailly empty set (Set), which can only happen -- when calling take 0. -- --
-- take n = Data.Set.fromDistinctAscList . Data.List.NonEmpty.take n . toAscList --take :: Int -> NESet a -> Set a -- | Drop a given number of elements in order, beginning with the smallest -- ones. -- -- Returns a potentailly empty set (Set), in the case that -- drop 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 . toAscList --drop :: Int -> NESet a -> Set a -- | O(log n). Split a set at a particular index i. -- --
-- and [x < y ==> f x < f y | x <- ls, y <- ls] -- ==> mapMonotonic f s == map f s -- where ls = Data.Foldable.toList s --mapMonotonic :: (a -> b) -> NESet a -> NESet b -- | O(n). Fold the elements in the set using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . toAscList. -- -- For example, -- --
-- elemsList set = foldr (:) [] set --foldr :: (a -> b -> b) -> b -> NESet a -> b -- | O(n). Fold the elements in the set using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . toAscList. -- -- For example, -- --
-- descElemsList set = foldl (flip (:)) [] set --foldl :: (a -> b -> a) -> a -> NESet b -> a -- | A variant of foldr that has no base case, and thus may only be -- applied to non-empty structures. -- --
-- foldr1 f = foldr1 f . toList --foldr1 :: Foldable t => (a -> a -> a) -> t a -> a -- | A variant of foldl that has no base case, and thus may only be -- applied to non-empty structures. -- --
-- foldl1 f = foldl1 f . toList --foldl1 :: Foldable t => (a -> a -> a) -> t a -> a -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> NESet a -> b -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> NESet b -> a -- | O(n). A strict version of foldr1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldr1' :: (a -> a -> a) -> NESet a -> a -- | O(n). A strict version of foldl1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldl1' :: (a -> a -> a) -> NESet a -> a -- | O(1). The minimal element of a set. Note that this is total, -- making lookupMin obsolete. It is constant-time, so has better -- asymptotics than Data.Set.lookupMin and -- Data.Map.findMin as well. -- --
-- findMin (fromList (5 :| [3])) == 3 --findMin :: NESet a -> a -- | O(log n). The maximal key of a set Note that this is total, -- making lookupMin obsolete. -- --
-- findMax (fromList (5 :| [3])) == 5 --findMax :: NESet a -> a -- | O(1). Delete the minimal element. Returns a potentially empty -- set (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.empty --deleteMin :: NESet a -> Set a -- | O(log n). Delete the maximal element. Returns a potentially -- empty set (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.empty --deleteMax :: NESet a -> Set a -- | O(1). Delete and find the minimal element. It is constant-time, -- so has better asymptotics that Data.Set.minView for -- Set. -- -- Note that unlike Data.Set.deleteFindMin for Set, this -- cannot ever fail, and so is a total function. However, the result -- Set 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]) --deleteFindMin :: NESet a -> (a, Set a) -- | O(log n). Delete and find the minimal element. -- -- Note that unlike Data.Set.deleteFindMax for Set, this -- cannot ever fail, and so is a total function. However, the result -- Set 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]) --deleteFindMax :: NESet a -> (a, Set a) -- | O(n). An alias of toAscList. The elements of a set in -- ascending order. elems :: NESet a -> NonEmpty a -- | O(n). Convert the set to a non-empty list of elements. toList :: NESet a -> NonEmpty a -- | O(n). Convert the set to an ascending non-empty list of -- elements. toAscList :: NESet a -> NonEmpty a -- | O(n). Convert the set to a descending non-empty list of -- elements. toDescList :: NESet a -> NonEmpty a -- | O(n). Test if the internal set structure is valid. valid :: Ord a => NESet a -> Bool -- |
-- import qualified Data.Map.NonEmpty as NEM ---- -- At the moment, this package does not provide a variant strict on -- values for these functions, like containers does. This is a -- planned future implementation (PR's are appreciated). For now, you can -- simulate a strict interface by manually forcing values before -- returning results. module Data.Map.NonEmpty -- | A non-empty (by construction) map from keys k to values -- a. At least one key-value pair exists in an NEMap -- k v at all times. -- -- Functions that take an NEMap can safely operate on it -- with the assumption that it has at least one key-value pair. -- -- Functions that return an NEMap 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 insert) return NEMap, but functions that -- might potentially return an empty map (like delete) return a -- Map instead. -- -- You can directly construct an NEMap with the API from -- Data.Map.NonEmpty; it's more or less the same as constructing a -- normal Map, except you don't have access to empty. There -- are also a few ways to construct an NEMap from a Map: -- --
-- myFunc :: Map K X -> Y -- myFunc (IsNonEmpty n) = -- here, the user provided a non-empty map, and n is the NEMap -- myFunc IsEmpty = -- here, the user provided an empty map. ---- -- Matching on IsNonEmpty n means that the original -- Map was not empty, and you have a verified-non-empty -- NEMap 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 IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsNonEmpty to -- convert a NEMap back into a Map, obscuring its -- non-emptiness (see toMap). pattern IsNonEmpty :: NEMap k a -> Map k a -- | O(1). The IsNonEmpty and IsEmpty patterns allow -- you to treat a Map as if it were either a IsNonEmpty -- n (where n is a NEMap) or an IsEmpty. -- -- Matching on IsEmpty means that the original Map was -- empty. -- -- A case statement handling both IsNonEmpty and IsEmpty -- provides complete coverage. -- -- This is a bidirectional pattern, so you can use IsEmpty as an -- expression, and it will be interpreted as empty. -- -- See IsNonEmpty for more information. pattern IsEmpty :: Map k a -- | O(log n). Smart constructor for an NEMap from a -- Map. Returns Nothing if the Map was originally -- actually empty, and Just n with an NEMap, if -- the Map was not empty. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- -- See IsNonEmpty for a pattern synonym that lets you "match on" -- the possiblity of a Map being an NEMap. -- --
-- nonEmptyMap (Data.Map.fromList [(3,"a"), (5,"b")]) == Just (fromList ((3,"a") :| [(5,"b")])) --nonEmptyMap :: Map k a -> Maybe (NEMap k a) -- | O(log n). Convert a non-empty map back into a normal -- possibly-empty map, for usage with functions that expect Map. -- -- Can be thought of as "obscuring" the non-emptiness of the map in its -- type. See the IsNotEmpty pattern. -- -- nonEmptyMap and maybe empty toMap -- form an isomorphism: they are perfect structure-preserving inverses of -- eachother. -- --
-- toMap (fromList ((3,"a") :| [(5,"b")])) == Data.Map.fromList [(3,"a"), (5,"b")] --toMap :: NEMap k a -> Map k a -- | O(log n). A general continuation-based way to consume a -- Map as if it were an NEMap. withNonEmpty def -- f will take a Map. If map is empty, it will evaluate to -- def. Otherwise, a non-empty map NEMap will be fed to -- the function f instead. -- --
-- nonEmptyMap == withNonEmpty Nothing Just --withNonEmpty :: r -> (NEMap k a -> r) -> Map k a -> r -- | O(log n). Convert a Map into an NEMap 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 insertMapMin 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" --insertMap :: Ord k => k -> a -> Map k a -> NEMap k a -- | O(log n). Convert a Map into an NEMap 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")]) --insertMapWith :: Ord k => (a -> a -> a) -> k -> a -> Map k a -> NEMap k a -- | O(log n). Convert a Map into an NEMap 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" --insertMapWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> Map k a -> NEMap k a -- | O(1) Convert a Map into an NEMap 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")])) == False --insertMapMin :: k -> a -> Map k a -> NEMap k a -- | O(log n) Convert a Map into an NEMap 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 insertMap, it saves a -- constant factor for key comparison (so may be helpful if comparison is -- expensive) and also does not require an Ord 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")])) == False --insertMapMax :: k -> a -> Map k a -> NEMap k a -- | O(log n). Unsafe version of nonEmptyMap. Coerces a -- Map into an NEMap, but is undefined (throws a runtime -- exception when evaluation is attempted) for an empty Map. unsafeFromMap :: Map k a -> NEMap k a -- | O(1). A map with a single element. -- --
-- singleton 1 'a' == fromList ((1, 'a') :| []) -- size (singleton 1 'a') == 1 --singleton :: k -> a -> NEMap k a -- | O(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")]) --fromSet :: (k -> a) -> NESet k -> NEMap k a -- | O(n*log n). Build a non-empty map from a non-empty list of -- key/value pairs. See also fromAscList. If the list contains -- more than one value for the same key, the last value for the key is -- retained. -- --
-- fromList ((5,"a") :| [(3,"b"), (5, "c")]) == fromList ((5,"c") :| [(3,"b")]) -- fromList ((5,"c") :| [(3,"b"), (5, "a")]) == fromList ((5,"a") :| [(3,"b")]) --fromList :: Ord k => NonEmpty (k, a) -> NEMap k a -- | O(n*log n). Build a map from a non-empty list of key/value -- pairs with a combining function. See also fromAscListWith. -- --
-- fromListWith (++) ((5,"a") :| [(5,"b"), (3,"b"), (3,"a"), (5,"a")]) == fromList ((3, "ab") :| [(5, "aba")]) --fromListWith :: Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a -- | O(n*log n). Build a map from a non-empty list of key/value -- pairs with a combining function. See also fromAscListWithKey. -- --
-- 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")]) --fromListWithKey :: Ord k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a -- | O(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")])) == False --fromAscList :: Eq k => NonEmpty (k, a) -> NEMap k a -- | O(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"))]) == False --fromAscListWith :: Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a -- | O(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")])) == False --fromAscListWithKey :: Eq k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a -- | O(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")])) == False --fromDistinctAscList :: NonEmpty (k, a) -> NEMap k a -- | O(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")])) == False --fromDescList :: Eq k => NonEmpty (k, a) -> NEMap k a -- | O(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")])) == False --fromDescListWith :: Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a -- | O(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")])) == False --fromDescListWithKey :: Eq k => (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a -- | O(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")])) == False --fromDistinctDescList :: NonEmpty (k, a) -> NEMap k a -- | O(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. insert is equivalent to insertWith -- const. -- -- See insertMap for a version where the first argument is a -- Map. -- --
-- insert 5 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'x')]) -- insert 7 'x' (fromList ((5,'a') :| [(3,'b')])) == fromList ((3, 'b') :| [(5, 'a'), (7, 'x')]) --insert :: Ord k => k -> a -> NEMap k a -> NEMap k a -- | O(log n). Insert with a function, combining new value and old -- value. insertWith f key value mp will insert the pair -- (key, value) into mp if key does not exist in the map. If the -- key does exist, the function will insert the pair (key, f -- new_value old_value). -- -- See insertMapWith for a version where the first argument is a -- Map. -- --
-- insertWith (++) 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "xxxa")]) -- insertWith (++) 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) --insertWith :: Ord k => (a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a -- | O(log n). Insert with a function, combining key, new value and -- old value. insertWithKey f key value mp will insert -- the pair (key, value) into mp if key does not exist in the -- map. If the key does exist, the function will insert the pair -- (key,f key new_value old_value). Note that the key passed to -- f is the same key passed to insertWithKey. -- -- See insertMapWithKey for a version where the first argument is -- a Map. -- --
-- let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value -- insertWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "5:xxx|a")]) -- insertWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "b") :| [(5, "a"), (7, "xxx")]) --insertWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a -- | O(log n). Combines insert operation with old value retrieval. -- The expression (insertLookupWithKey f k x map) is a -- pair where the first element is equal to (lookup k -- map) and the second element equal to (insertWithKey f -- k x map). -- --
-- let f key new_value old_value = (show key) ++ ":" ++ new_value ++ "|" ++ old_value -- insertLookupWithKey f 5 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Just "a", fromList ((3, "b") :| [(5, "5:xxx|a")])) -- insertLookupWithKey f 7 "xxx" (fromList ((5,"a") :| [(3,"b")])) == (Nothing, fromList ((3, "b") :| [(5, "a"), (7, "xxx")])) ---- -- 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")])) --insertLookupWithKey :: Ord k => (k -> a -> a -> a) -> k -> a -> NEMap k a -> (Maybe a, NEMap k a) -- | O(log n). Delete a key and its value from the non-empty map. A -- potentially empty map (Map) is returned, since this might -- delete the last item in the NEMap. When the key is not a member -- of the map, is equivalent to toMap. -- --
-- 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")] --delete :: Ord k => k -> NEMap k a -> Map k a -- | O(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")])
--
adjust :: Ord k => (a -> a) -> k -> NEMap k a -> NEMap k a
-- | O(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")]) --adjustWithKey :: Ord k => (k -> a -> a) -> k -> NEMap k a -> NEMap k a -- | O(log n). The expression (update f k map) -- updates the value x at k (if it is in the map). If -- (f x) is Nothing, the element is deleted. If it is -- (Just y), the key k is bound to the new value -- y. -- -- Returns a potentially empty map (Map), because we can't know -- ahead of time if the function returns Nothing and deletes the -- final item in the NEMap. -- --
-- 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" --update :: Ord k => (a -> Maybe a) -> k -> NEMap k a -> Map k a -- | O(log n). The expression (updateWithKey f k -- map) updates the value x at k (if it is in the -- map). If (f k x) is Nothing, the element is deleted. -- If it is (Just y), the key k is bound to the -- new value y. -- -- Returns a potentially empty map (Map), because we can't know -- ahead of time if the function returns Nothing and deletes the -- final item in the NEMap. -- --
-- 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" --updateWithKey :: Ord k => (k -> a -> Maybe a) -> k -> NEMap k a -> Map k a -- | O(log n). Lookup and update. See also updateWithKey. 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 (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") --updateLookupWithKey :: Ord k => (k -> a -> Maybe a) -> k -> NEMap k a -> (Maybe a, Map k a) -- | O(log n). The expression (alter f k map) alters -- the value x at k, or absence thereof. alter -- can be used to insert, delete, or update a value in a Map. In -- short : Data.Map.lookup k (alter f k m) = f (lookup -- k m). -- -- Returns a potentially empty map (Map), because we can't know -- ahead of time if the function returns Nothing and deletes the -- final item in the NEMap. -- -- See alterF' for a version that disallows deletion, and so -- therefore can return NEMap. -- --
-- 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")] --alter :: Ord k => (Maybe a -> Maybe a) -> k -> NEMap k a -> Map k a -- | O(log n). The expression (alterF f k map) -- alters the value x at k, or absence thereof. -- alterF can be used to inspect, insert, delete, or update a -- value in a Map. In short: Data.Map.lookup k <$> -- alterF f k m = f (lookup 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 Map, alterF can be -- considered to be a unifying generalization of lookup and -- delete; however, as a constrast, it cannot be used to implement -- insert, because it must return a Map instead of an -- NEMap (because the function might delete the final item in the -- NEMap). When used with trivial functors like Identity -- and Const, it is often slightly slower than specialized -- lookup and delete. However, when the functor is -- non-trivial and key comparison is not particularly cheap, it is the -- fastest way. -- -- See alterF' for a version that disallows deletion, and so -- therefore can return NEMap and be used to implement -- insert -- -- Note on rewrite rules: -- -- This module includes GHC rewrite rules to optimize alterF for -- the Const and Identity functors. In general, these rules -- improve performance. The sole exception is that when using -- Identity, 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 Identity type. -- -- Note: Unlike Data.Map.alterF for Map, alterF is -- not a flipped version of the at 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. alterF :: (Ord k, Functor f) => (Maybe a -> f (Maybe a)) -> k -> NEMap k a -> f (Map k a) -- | O(log n). Variant of alter that disallows deletion. -- Allows us to guarantee that the result is also a non-empty Map. alter' :: Ord k => (Maybe a -> a) -> k -> NEMap k a -> NEMap k a -- | O(log n). Variant of alterF that disallows deletion. -- Allows us to guarantee that the result is also a non-empty Map. -- -- Like Data.Map.alterF for Map, can be used to -- generalize and unify lookup and insert. However, because -- it disallows deletion, it cannot be used to implement delete. -- -- See alterF for usage information and caveats. -- -- Note: Neither alterF nor alterF' can be considered -- flipped versions of the at 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 Identity exposes an -- inconsistency in undefined behavior for Data.Map. -- Data.Map.alterF will actually maintain the original -- key in the map when used with Identity; however, -- Data.Map.insertWith will replace the orginal key in -- the map. The rewrite rule for alterF' has chosen to be faithful -- to Data.Map.insertWith, and not -- Data.Map.alterF, for the sake of a cleaner implementation. alterF' :: (Ord k, Functor f) => (Maybe a -> f a) -> k -> NEMap k a -> f (NEMap k a) -- | O(log n). Lookup the value at a key in the map. -- -- The function will return the corresponding value as (Just -- value), or Nothing if the key isn't in the map. -- -- 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:
--
-- -- John's currency: Just "Euro" -- Pete's currency: Nothing --lookup :: Ord k => k -> NEMap k a -> Maybe a -- | O(log n). Find the value at a key. Returns Nothing when -- the element can not be found. -- --
-- fromList ((5, 'a') :| [(3, 'b')]) !? 1 == Nothing ---- --
-- fromList ((5, 'a') :| [(3, 'b')]) !? 5 == Just 'a' --(!?) :: Ord k => NEMap k a -> k -> Maybe a infixl 9 !? -- | O(log n). Find the value at a key. Calls error 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' --(!) :: Ord k => NEMap k a -> k -> a infixl 9 ! -- | O(log n). The expression (findWithDefault def k -- map) returns the value at key k or returns default value -- def when the key is not in the map. -- --
-- findWithDefault 'x' 1 (fromList ((5,'a') :| [(3,'b')])) == 'x' -- findWithDefault 'x' 5 (fromList ((5,'a') :| [(3,'b')])) == 'a' --findWithDefault :: Ord k => a -> k -> NEMap k a -> a -- | O(log n). Is the key a member of the map? See also -- notMember. -- --
-- member 5 (fromList ((5,'a') :| [(3,'b')])) == True -- member 1 (fromList ((5,'a') :| [(3,'b')])) == False --member :: Ord k => k -> NEMap k a -> Bool -- | O(log n). Is the key not a member of the map? See also -- member. -- --
-- notMember 5 (fromList ((5,'a') :| [(3,'b')])) == False -- notMember 1 (fromList ((5,'a') :| [(3,'b')])) == True --notMember :: Ord k => k -> NEMap k a -> Bool -- | O(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') --lookupLT :: Ord k => k -> NEMap k a -> Maybe (k, a) -- | O(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')])) == Nothing --lookupGT :: Ord k => k -> NEMap k a -> Maybe (k, a) -- | O(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') --lookupLE :: Ord k => k -> NEMap k a -> Maybe (k, a) -- | O(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')])) == Nothing --lookupGE :: Ord k => k -> NEMap k a -> Maybe (k, a) -- | Special 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 NESet, NESeq, and -- NEIntMap); this can be witnessed using the function -- absurd . fold1. absurdNEMap :: NEMap Void a -> b -- | O(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')])) == 3 --size :: NEMap k a -> Int -- | O(m*log(n/m + 1)), m <= n. The expression (union -- t1 t2) takes the left-biased union of t1 and -- t2. It prefers t1 when duplicate keys are -- encountered, i.e. (union == unionWith -- const). -- --
-- union (fromList ((5, "a") :| [(3, "b")])) (fromList ((5, "A") :| [(7, "C")])) == fromList ((3, "b") :| [(5, "a"), (7, "C")]) --union :: Ord k => NEMap k a -> NEMap k a -> NEMap k a -- | O(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")]) --unionWith :: Ord k => (a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a -- | O(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")]) --unionWithKey :: Ord k => (k -> a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a -- | The 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")]) --unions :: (Foldable1 f, Ord k) => f (NEMap k a) -> NEMap k a -- | The union of a non-empty list of maps, with a combining operation: -- (unionsWith f == foldl1 (unionWith f)). -- --
-- unionsWith (++) (fromList ((5, "a") :| [(3, "b")]) :| [fromList ((5, "A") :| [(7, "C")]), fromList ((5, "A3") :| [(3, "B3")])]) -- == fromList ((3, "bB3") :| [(5, "aAA3"), (7, "C")]) --unionsWith :: (Foldable1 f, Ord k) => (a -> a -> a) -> f (NEMap k a) -> NEMap k a -- | O(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 (Map), 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" --difference :: Ord k => NEMap k a -> NEMap k b -> Map k a -- | Same as difference. (\\) :: Ord k => NEMap k a -> NEMap k b -> Map k a -- | O(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 Nothing, the element is discarded -- (proper set difference). If it returns (Just y), the -- element is updated with a new value y. -- -- Returns a potentially empty map (Map), in case the first map is -- a subset of the second map and the function returns Nothing 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" --differenceWith :: Ord k => (a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a -- | O(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 Nothing, the element is discarded -- (proper set difference). If it returns (Just y), the -- element is updated with a new value y. -- -- Returns a potentially empty map (Map), in case the first map is -- a subset of the second map and the function returns Nothing 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" --differenceWithKey :: Ord k => (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a -- | O(m*log(n/m + 1)), m <= n. Intersection of two maps. Return -- data in the first map for the keys existing in both maps. -- (intersection m1 m2 == intersectionWith const -- m1 m2). -- -- Returns a potentially empty map (Map), 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" --intersection :: Ord k => NEMap k a -> NEMap k b -> Map k a -- | O(m*log(n/m + 1)), m <= n. Intersection with a combining -- function. -- -- Returns a potentially empty map (Map), 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" --intersectionWith :: Ord k => (a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c -- | O(m*log(n/m + 1)), m <= n. Intersection with a combining -- function. -- -- Returns a potentially empty map (Map), 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" --intersectionWithKey :: Ord k => (k -> a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c -- | O(n). Map a function over all values in the map. -- --
-- map (++ "x") (fromList ((5,"a") :| [(3,"b")])) == fromList ((3, "bx") :| [(5, "ax")]) --map :: (a -> b) -> NEMap k a -> NEMap k b -- | O(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")]) --mapWithKey :: (k -> a -> b) -> NEMap k a -> NEMap k b -- | O(n). traverseWithKey1 f m == fromList -- $ traverse1 ((k, v) -> (,) k $ f k v) -- (toList m) -- -- That is, behaves exactly like a regular traverse1 except that -- the traversing function also has access to the key associated with a -- value. -- -- Is more general than traverseWithKey, since works with all -- Apply, and not just Applicative. traverseWithKey1 :: Apply t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b) -- | O(n). traverseWithKey f m == fromList -- $ traverse ((k, v) -> (,) k $ f k v) -- (toList m) That is, behaves exactly like a regular -- traverse except that the traversing function also has access to -- the key associated with a value. -- -- Use traverseWithKey1 whenever possible (if your -- Applicative also has Apply instance). This version is -- provided only for types that do not have Apply instance, since -- Apply is not at the moment (and might not ever be) an official -- superclass of Applicative. -- --
-- traverseWithKey f = unwrapApplicative . traverseWithKey1 (\k -> WrapApplicative . f k) --traverseWithKey :: Applicative t => (k -> a -> t b) -> NEMap k a -> t (NEMap k b) -- | O(n). Traverse keys/values and collect the Just results. -- -- Returns a potentially empty map (Map), our function might -- return Nothing on every item in the NEMap. -- -- Is more general than traverseWithKey, since works with all -- Apply, and not just Applicative. traverseMaybeWithKey1 :: Apply t => (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b) -- | O(n). Traverse keys/values and collect the Just results. -- -- Returns a potentially empty map (Map), our function might -- return Nothing on every item in the NEMap. -- -- Use traverseMaybeWithKey1 whenever possible (if your -- Applicative also has Apply instance). This version is -- provided only for types that do not have Apply instance, since -- Apply is not at the moment (and might not ever be) an official -- superclass of Applicative. traverseMaybeWithKey :: Applicative t => (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b) -- | O(n). The function mapAccum 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")]))
--
mapAccum :: (a -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
-- | O(n). The function mapAccumWithKey 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")]))
--
mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
-- | O(n). The function mapAccumRWithKey threads an
-- accumulating argument through the map in descending order of keys.
mapAccumRWithKey :: (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
-- | O(n*log n). mapKeys f s is the map obtained by
-- applying f to each key of s.
--
-- The size of the result may be smaller if f maps two or more
-- distinct keys to the same new key. In this case the value at the
-- 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" --mapKeys :: Ord k2 => (k1 -> k2) -> NEMap k1 a -> NEMap k2 a -- | O(n*log n). mapKeysWith c f s is the map -- obtained by applying f to each key of s. -- -- The size of the result may be smaller if f maps two or more -- distinct keys to the same new key. In this case the associated values -- will be combined using c. 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" --mapKeysWith :: Ord k2 => (a -> a -> a) -> (k1 -> k2) -> NEMap k1 a -> NEMap k2 a -- | O(n). mapKeysMonotonic f s == mapKeys f -- s, but works only when f is strictly monotonic. That is, -- for any values x and y, if x < -- y then f x < f y. The precondition is -- not checked. Semi-formally, we have: -- --
-- and [x < y ==> f x < f y | x <- ls, y <- ls] -- ==> mapKeysMonotonic f s == mapKeys f s -- where ls = keys s ---- -- This means that f maps distinct original keys to distinct -- resulting keys. This function has better performance than -- mapKeys. -- -- 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")]))) == False --mapKeysMonotonic :: (k1 -> k2) -> NEMap k1 a -> NEMap k2 a -- | O(n). Fold the values in the map using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . elems. -- --
-- elemsList map = foldr (:) [] map ---- --
-- let f a len = len + (length a) -- foldr f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldr :: (a -> b -> b) -> b -> NEMap k a -> b -- | O(n). Fold the values in the map using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . elems. -- --
-- elemsList = reverse . foldl (flip (:)) [] ---- --
-- let f len a = len + (length a) -- foldl f 0 (fromList ((5,"a") :| [(3,"bbb")])) == 4 --foldl :: (a -> b -> a) -> a -> NEMap k b -> a -- | O(n). A version of foldr that uses the value at the -- maximal key in the map as the starting value. -- -- Note that, unlike foldr1 for Map, this function is total -- if the input function is total. foldr1 :: (a -> a -> a) -> NEMap k a -> a -- | O(n). A version of foldl that uses the value at the -- minimal key in the map as the starting value. -- -- Note that, unlike foldl1 for Map, this function is total -- if the input function is total. foldl1 :: (a -> a -> a) -> NEMap k a -> a -- | O(n). Fold the keys and values in the map using the given -- right-associative binary operator, such that foldrWithKey f -- z == foldr (uncurry f) z . toAscList. -- -- For example, -- --
-- keysList map = foldrWithKey (\k x ks -> k:ks) [] map --foldrWithKey :: (k -> a -> b -> b) -> b -> NEMap k a -> b -- | O(n). Fold the keys and values in the map using the given -- left-associative binary operator, such that foldlWithKey f -- z == foldl (\z' (kx, x) -> f z' kx x) z . -- toAscList. -- -- For example, -- --
-- keysList = reverse . foldlWithKey (\ks k x -> k:ks) [] --foldlWithKey :: (a -> k -> b -> a) -> a -> NEMap k b -> a -- | O(n). Fold the keys and values in the map using the given -- semigroup, such that -- --
-- foldMapWithKey f = fold1 . mapWithKey f ---- -- This can be an asymptotically faster than foldrWithKey or -- foldlWithKey for some monoids. foldMapWithKey :: Semigroup m => (k -> a -> m) -> NEMap k a -> m -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> NEMap k a -> b -- | O(n). A strict version of foldr1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldr1' :: (a -> a -> a) -> NEMap k a -> a -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> NEMap k b -> a -- | O(n). A strict version of foldl1. Each application of -- the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldl1' :: (a -> a -> a) -> NEMap k a -> a -- | O(n). A strict version of foldrWithKey. Each application -- of the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldrWithKey' :: (k -> a -> b -> b) -> b -> NEMap k a -> b -- | O(n). A strict version of foldlWithKey. Each application -- of the operator is evaluated before using the result in the next -- application. This function is strict in the starting value. foldlWithKey' :: (a -> k -> b -> a) -> a -> NEMap k b -> a -- | O(n). Return all elements of the map in the ascending order of -- their keys. -- --
-- elems (fromList ((5,"a") :| [(3,"b")])) == ("b" :| ["a"])
--
elems :: NEMap k a -> NonEmpty a
-- | O(n). Return all keys of the map in ascending order.
--
-- -- keys (fromList ((5,"a") :| [(3,"b")])) == (3 :| [5]) --keys :: NEMap k a -> NonEmpty k -- | O(n). An alias for toAscList. Return all key/value pairs -- in the map in ascending key order. -- --
-- assocs (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")]) --assocs :: NEMap k a -> NonEmpty (k, a) -- | O(n). The non-empty set of all keys of the map. -- --
-- keysSet (fromList ((5,"a") :| [(3,"b")])) == Data.Set.NonEmpty.fromList (3 :| [5]) --keysSet :: NEMap k a -> NESet k -- | O(n). Convert the map to a non-empty list of key/value pairs. -- --
-- toList (fromList ((5,"a") :| [(3,"b")])) == ((3,"b") :| [(5,"a")]) --toList :: NEMap k a -> NonEmpty (k, a) -- | O(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")]) --toAscList :: NEMap k a -> NonEmpty (k, a) -- | O(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")]) --toDescList :: NEMap k a -> NonEmpty (k, a) -- | O(n). Filter all values that satisfy the predicate. -- -- Returns a potentially empty map (Map), because we could -- potentailly filter out all items in the original NEMap. -- --
-- 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.empty --filter :: (a -> Bool) -> NEMap k a -> Map k a -- | O(n). Filter all keys/values that satisfy the predicate. -- -- Returns a potentially empty map (Map), because we could -- potentailly filter out all items in the original NEMap. -- --
-- filterWithKey (\k _ -> k > 4) (fromList ((5,"a") :| [(3,"b")])) == Data.Map.singleton 5 "a" --filterWithKey :: (k -> a -> Bool) -> NEMap k a -> Map k a -- | O(m*log(n/m + 1)), m <= n. Restrict an NEMap to only -- those keys found in a Set. -- --
-- m `restrictKeys` s = filterWithKey (k _ -> k `member` s) m -- m `restrictKeys` s = m `intersection` fromSet (const ()) s --restrictKeys :: Ord k => NEMap k a -> Set k -> Map k a -- | O(m*log(n/m + 1)), m <= n. Remove all keys in a Set -- from an NEMap. -- --
-- m `withoutKeys` s = filterWithKey (k _ -> k `notMember` s) m -- m `withoutKeys` s = m `difference` fromSet (const ()) s --withoutKeys :: Ord k => NEMap k a -> Set k -> Map k a -- | O(n). Partition the map according to a predicate. -- -- Returns a These with potentially two non-empty maps: -- --
-- 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")])) --partition :: (a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a) -- | O(n). Partition the map according to a predicate. -- -- Returns a These with potentially two non-empty maps: -- --
-- 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")])) --partitionWithKey :: (k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a) -- | O(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 -- spanAntitone. -- -- Returns a potentially empty map (Map), because the predicate -- might fail on the first input. -- --
-- takeWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.takeWhile (p . fst) . Data.Foldable.toList -- takeWhileAntitone p = filterWithKey (k _ -> p k) --takeWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a -- | O(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 -- spanAntitone. -- --
-- dropWhileAntitone p = Data.Map.fromDistinctAscList . Data.List.dropWhile (p . fst) . Data.Foldable.toList -- dropWhileAntitone p = filterWithKey (k -> not (p k)) --dropWhileAntitone :: (k -> Bool) -> NEMap k a -> Map k a -- | O(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 These with potentially two non-empty maps: -- --
-- spanAntitone 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). spanAntitone :: (k -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a) -- | O(n). Map values and collect the Just results. -- -- Returns a potentially empty map (Map), because the function -- could potentially return Nothing on all items in the -- NEMap. -- --
-- 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" --mapMaybe :: (a -> Maybe b) -> NEMap k a -> Map k b -- | O(n). Map keys/values and collect the Just results. -- -- Returns a potentially empty map (Map), because the function -- could potentially return Nothing on all items in the -- NEMap. -- --
-- 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"
--
mapMaybeWithKey :: (k -> a -> Maybe b) -> NEMap k a -> Map k b
-- | O(n). Map values and separate the Left and Right
-- results.
--
-- Returns a These with potentially two non-empty maps:
--
-- -- 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")])) --mapEither :: (a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c) -- | O(n). Map keys/values and separate the Left and -- Right results. -- -- Returns a These with potentially two non-empty maps: -- --
-- 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")])) --mapEitherWithKey :: (k -> a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c) -- | O(log n). The expression (split k map) is -- potentially a These containing up to two NEMaps 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. -- --
-- 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") == Nothing --split :: Ord k => k -> NEMap k a -> Maybe (These (NEMap k a) (NEMap k a)) -- | O(log n). The expression (splitLookup k map) -- splits a map just like split but also returns lookup -- k map, as the first field in the These: -- --
-- 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" --splitLookup :: Ord k => k -> NEMap k a -> These a (These (NEMap k a) (NEMap k a)) -- | O(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. splitRoot :: NEMap k a -> NonEmpty (NEMap k a) -- | O(m*log(n/m + 1)), m <= n. This function is defined as -- (isSubmapOf = isSubmapOfBy (==)). isSubmapOf :: (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool -- | O(m*log(n/m + 1)), m <= n. The expression -- (isSubmapOfBy f t1 t2) returns True if all keys -- in t1 are in tree t2, and when f returns -- True when applied to their respective values. For example, the -- following expressions are all True: -- --
-- isSubmapOfBy (==) (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 False:
--
--
-- 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)
--
isSubmapOfBy :: Ord k => (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
-- | O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a
-- submap but not equal). Defined as (isProperSubmapOf =
-- isProperSubmapOfBy (==)).
isProperSubmapOf :: (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool
-- | O(m*log(n/m + 1)), m <= n. Is this a proper submap? (ie. a
-- submap but not equal). The expression (isProperSubmapOfBy f
-- m1 m2) returns True when m1 and m2 are
-- not equal, all keys in m1 are in m2, and when
-- f returns True when applied to their respective
-- values. For example, the following expressions are all True:
--
-- -- isProperSubmapOfBy (==) (singleton 1 1) (fromList ((1,1) :| [(2,2)])) -- isProperSubmapOfBy (<=) (singleton 1 1) (fromList ((1,1) :| [(2,2)])) ---- -- But the following are all False: -- --
-- 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)])) --isProperSubmapOfBy :: Ord k => (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool -- | O(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 size 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")]))) == False --lookupIndex :: Ord k => k -> NEMap k a -> Maybe Int -- | O(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 size of the map. -- Calls error when the key is not a member of the map. -- --
-- findIndex 2 (fromList ((5,"a") :| [(3,"b")])) Error: element is not in the map -- findIndex 3 (fromList ((5,"a") :| [(3,"b")])) == 0 -- findIndex 5 (fromList ((5,"a") :| [(3,"b")])) == 1 -- findIndex 6 (fromList ((5,"a") :| [(3,"b")])) Error: element is not in the map --findIndex :: Ord k => k -> NEMap k a -> Int -- | O(log n). Retrieve an element by its index, i.e. by its -- zero-based index in the sequence sorted by keys. If the index -- is out of range (less than zero, greater or equal to size of -- the map), error 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 range --elemAt :: Int -> NEMap k a -> (k, a) -- | O(log n). Update the element at index, i.e. by its -- zero-based index in the sequence sorted by keys. If the index -- is out of range (less than zero, greater or equal to size of -- the map), error is called. -- -- Returns a possibly empty map (Map), because the function might -- end up deleting the last key in the map. See adjustAt 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 range --updateAt :: (k -> a -> Maybe a) -> Int -> NEMap k a -> Map k a -- | O(log n). Variant of updateAt that disallows deletion. -- Allows us to guarantee that the result is also a non-empty Map. adjustAt :: (k -> a -> a) -> Int -> NEMap k a -> NEMap k a -- | O(log n). Delete the element at index, i.e. by its -- zero-based index in the sequence sorted by keys. If the index -- is out of range (less than zero, greater or equal to size of -- the map), error is called. -- -- Returns a potentially empty map (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 range --deleteAt :: Int -> NEMap k a -> Map k a -- | Take a given number of entries in key order, beginning with the -- smallest keys. -- -- Returns a possibly empty map (Map), which can only happen if we -- call take 0. -- --
-- take n = Data.Map.fromDistinctAscList . Data.List.NonEmpty.take n . toList --take :: Int -> NEMap k a -> Map k a -- | Drop a given number of entries in key order, beginning with the -- smallest keys. -- -- Returns a possibly empty map (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 . toList --drop :: Int -> NEMap k a -> Map k a -- | O(log n). Split a map at a particular index i. -- --
-- findMin (fromList ((5,"a") :| [(3,"b")])) == (3,"b") --findMin :: NEMap k a -> (k, a) -- | O(log n). The maximal key of the map. Note that this is total, -- making lookupMin obsolete. -- --
-- findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a") --findMax :: NEMap k a -> (k, a) -- | O(1). Delete the minimal key. Returns a potentially empty map -- (Map), because we might end up deleting the final key in a -- singleton map. It is constant-time, so has better asymptotics than -- deleteMin. -- --
-- deleteMin (fromList ((5,"a") :| [(3,"b"), (7,"c")])) == Data.Map.fromList [(5,"a"), (7,"c")] -- deleteMin (singleton 5 "a") == Data.Map.empty --deleteMin :: NEMap k a -> Map k a -- | O(log n). Delete the maximal key. Returns a potentially empty -- map (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.empty --deleteMax :: NEMap k a -> Map k a -- | O(1). Delete and find the minimal key-value pair. It is -- constant-time, so has better asymptotics that -- Data.Map.minView for Map. -- -- Note that unlike Data.Map.deleteFindMin for Map, this -- cannot ever fail, and so is a total function. However, the result -- Map 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")]) --deleteFindMin :: NEMap k a -> ((k, a), Map k a) -- | O(log n). Delete and find the minimal key-value pair. -- -- Note that unlike Data.Map.deleteFindMax for Map, this -- cannot ever fail, and so is a total function. However, the result -- Map 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")]) --deleteFindMax :: NEMap k a -> ((k, a), Map k a) -- | O(1) if delete, O(log n) otherwise. Update the value at -- the minimal key. Returns a potentially empty map (Map), because -- we might end up deleting the final key in the map if the function -- returns Nothing. See adjustMin 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"
--
updateMin :: (a -> Maybe a) -> NEMap k a -> Map k a
-- | O(log n). Update the value at the maximal key. Returns a
-- potentially empty map (Map), because we might end up deleting
-- the final key in the map if the function returns Nothing. See
-- adjustMax 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"
--
updateMax :: (a -> Maybe a) -> NEMap k a -> Map k a
-- | O(1). A version of updateMin that disallows deletion,
-- allowing us to guarantee that the result is also non-empty.
adjustMin :: (a -> a) -> NEMap k a -> NEMap k a
-- | O(log n). A version of updateMax that disallows
-- deletion, allowing us to guarantee that the result is also non-empty.
adjustMax :: (a -> a) -> NEMap k a -> NEMap k a
-- | O(1) if delete, O(log n) otherwise. Update the value at
-- the minimal key. Returns a potentially empty map (Map), because
-- we might end up deleting the final key in the map if the function
-- returns Nothing. See adjustMinWithKey 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" --updateMinWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a -- | O(log n). Update the value at the maximal key. Returns a -- potentially empty map (Map), because we might end up deleting -- the final key in the map if the function returns Nothing. See -- adjustMaxWithKey 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" --updateMaxWithKey :: (k -> a -> Maybe a) -> NEMap k a -> Map k a -- | O(1). A version of adjustMaxWithKey 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 -- updateMinWithKey in general. adjustMinWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a -- | O(log n). A version of updateMaxWithKey that disallows -- deletion, allowing us to guarantee that the result is also non-empty. adjustMaxWithKey :: (k -> a -> a) -> NEMap k a -> NEMap k a -- | O(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 Map. -- -- Note that unlike Data.Map.minView for Map, this cannot -- ever fail, so doesn't need to return in a Maybe. However, the -- result Map 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")
--
minView :: NEMap k a -> (a, Map k a)
-- | O(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 Map, this
-- cannot ever fail, so doesn't need to return in a Maybe.
-- However, the result Map 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")
--
maxView :: NEMap k a -> (a, Map k a)
-- | O(n). Test if the internal map structure is valid.
valid :: Ord k => NEMap k a -> Bool
-- | (x == empty) ==> isEmpty x
(x == empty) ==> isNothing (nonEmpty x)
isEmpty x ==> isNothing (nonEmpty x)
unsafeToNonEmpty x == fromJust (nonEmpty x)
-- safeHead :: [Int] -> Int -- safeHead (IsNonEmpty (x :| _)) = x -- here, the list was not empty -- safehead IsEmpty = 0 -- here, the list was empty ---- -- Matching on IsNonEmpty n means that the original input -- was not empty, and you have a verified-non-empty n :: -- NE 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 IsNonEmpty and -- NonEmpty, even though the two are meant to provide complete -- coverage. However, many instances of HasNonEmpty (like -- NEMap, NEIntMap, NESet, NEIntSet) will -- provide their own monomorphic versions of these patterns that can be -- verified as complete covers by GHC. -- -- This is a bidirectional pattern, so you can use IsNonEmpty to -- convert a NE s back into an s, "obscuring" -- its non-emptiness (see fromNonEmpty). pattern IsNonEmpty :: HasNonEmpty s => NE s -> s -- | The IsNonEmpty and IsEmpty patterns allow you to treat a -- s as if it were either a IsNonEmpty n (where -- n is a non-empty version of s, type NE -- s) or an IsEmpty. -- -- Matching on IsEmpty means that the original item was empty. -- -- This is a bidirectional pattern, so you can use IsEmpty as an -- expression, and it will be interpreted as empty. -- -- 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 IsNonEmpty and -- NonEmpty, even though the two are meant to provide complete -- coverage. However, many instances of HasNonEmpty (like -- NEMap, NEIntMap, NESet, NEIntSet) will -- provide their own monomorphic versions of these patterns that can be -- verified as complete covers by GHC. -- -- See IsNonEmpty for more information. pattern IsEmpty :: HasNonEmpty s => s -- | Useful function for mapping over the "non-empty" representation of a -- type. overNonEmpty :: (HasNonEmpty s, HasNonEmpty t) => (NE s -> NE t) -> s -> t -- | Useful function for applying a function on the "non-empty" -- representation of a type. -- -- If you want a continuation taking NE s -> 'Maybe -- r', you can use withNonEmpty Nothing. onNonEmpty :: HasNonEmpty s => (NE s -> r) -> s -> Maybe r instance Data.Containers.NonEmpty.HasNonEmpty [a] instance Data.Containers.NonEmpty.HasNonEmpty (Data.Map.Internal.Map k a) instance Data.Containers.NonEmpty.HasNonEmpty (Data.IntMap.Internal.IntMap a) instance Data.Containers.NonEmpty.HasNonEmpty (Data.Set.Internal.Set a) instance Data.Containers.NonEmpty.HasNonEmpty Data.IntSet.Internal.IntSet instance Data.Containers.NonEmpty.HasNonEmpty (Data.Sequence.Internal.Seq a) instance Data.Containers.NonEmpty.HasNonEmpty (Data.Vector.Vector a)