-- 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.5.0

-- | 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:
--   
--   
--   
- The nonEmptyMap smart constructor will convert a
--   IntMap k a into a Maybe (NEIntMap k
--   a), returning Nothing if the original IntMap was
--   empty.
--   
- You can use the insertIntMap family of functions to insert
--   a value into a IntMap to create a guaranteed
--   NEIntMap.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a IntMap to reveal it as either containing a
--   NEIntMap or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a IntMap and treating it as if it were an
--   NEIntMap.
--   
--   
--   You can convert an NEIntMap into a IntMap with
--   toMap or IsNonEmpty, essentially "obscuring" the
--   non-empty property from the type.
data NEIntMap a
NEIntMap :: !Key -> a -> !IntMap a -> NEIntMap a

-- | invariant: must be smaller than smallest key in map
[neimK0] :: NEIntMap a -> !Key
[neimV0] :: NEIntMap a -> a
[neimIntMap] :: NEIntMap a -> !IntMap a
type Key = Int

-- | 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(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(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
instance Data.Functor.Alt.Alt Data.IntMap.NonEmpty.Internal.NEIntMap
instance Control.Comonad.Comonad Data.IntMap.NonEmpty.Internal.NEIntMap
instance GHC.Internal.Data.Data.Data a => GHC.Internal.Data.Data.Data (Data.IntMap.NonEmpty.Internal.NEIntMap a)
instance Data.Functor.Classes.Eq1 Data.IntMap.NonEmpty.Internal.NEIntMap
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.IntMap.NonEmpty.Internal.NEIntMap a)
instance Data.Foldable1.Foldable1 Data.IntMap.NonEmpty.Internal.NEIntMap
instance GHC.Internal.Data.Foldable.Foldable Data.IntMap.NonEmpty.Internal.NEIntMap
instance Data.Aeson.Types.FromJSON.FromJSON a => Data.Aeson.Types.FromJSON.FromJSON (Data.IntMap.NonEmpty.Internal.NEIntMap a)
instance GHC.Internal.Base.Functor Data.IntMap.NonEmpty.Internal.NEIntMap
instance Data.Functor.Invariant.Invariant Data.IntMap.NonEmpty.Internal.NEIntMap
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.IntMap.NonEmpty.Internal.NEIntMap a)
instance Data.Functor.Classes.Ord1 Data.IntMap.NonEmpty.Internal.NEIntMap
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.IntMap.NonEmpty.Internal.NEIntMap a)
instance Data.Functor.Classes.Read1 Data.IntMap.NonEmpty.Internal.NEIntMap
instance GHC.Internal.Read.Read e => GHC.Internal.Read.Read (Data.IntMap.NonEmpty.Internal.NEIntMap e)
instance GHC.Internal.Base.Semigroup (Data.IntMap.NonEmpty.Internal.NEIntMap a)
instance Data.Functor.Classes.Show1 Data.IntMap.NonEmpty.Internal.NEIntMap
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (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.Semigroup.Traversable.Class.Traversable1 Data.IntMap.NonEmpty.Internal.NEIntMap
instance GHC.Internal.Data.Traversable.Traversable 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:
--   
--   
--   
- The nonEmptySet smart constructor will convert a
--   IntSet a into a Maybe (NEIntSet
--   a), returning Nothing if the original IntSet was
--   empty.
--   
- You can use the insertIntSet family of functions to insert
--   a value into a IntSet to create a guaranteed
--   NEIntSet.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a IntSet to reveal it as either containing a
--   NEIntSet or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a IntSet and treating it as if it were an
--   NEIntSet.
--   
--   
--   You can convert an NEIntSet into a IntSet with
--   toSet or IsNonEmpty, essentially "obscuring" the
--   non-empty property from the type.
data NEIntSet
NEIntSet :: !Key -> !IntSet -> NEIntSet

-- | invariant: must be smaller than smallest value in set
[neisV0] :: NEIntSet -> !Key
[neisIntSet] :: NEIntSet -> !IntSet
type Key = Int

-- | 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). 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
instance GHC.Internal.Data.Data.Data Data.IntSet.NonEmpty.Internal.NEIntSet
instance GHC.Classes.Eq Data.IntSet.NonEmpty.Internal.NEIntSet
instance Data.Aeson.Types.FromJSON.FromJSON Data.IntSet.NonEmpty.Internal.NEIntSet
instance Control.DeepSeq.NFData Data.IntSet.NonEmpty.Internal.NEIntSet
instance GHC.Classes.Ord Data.IntSet.NonEmpty.Internal.NEIntSet
instance GHC.Internal.Read.Read Data.IntSet.NonEmpty.Internal.NEIntSet
instance GHC.Internal.Base.Semigroup Data.IntSet.NonEmpty.Internal.NEIntSet
instance GHC.Internal.Show.Show Data.IntSet.NonEmpty.Internal.NEIntSet
instance Data.Aeson.Types.ToJSON.ToJSON Data.IntSet.NonEmpty.Internal.NEIntSet

-- | 
Non-Empty Finite Integer Sets
--   
--   The NEIntSet type represents a non-empty set of integers.
--   
--   See documentation for NEIntSet for information on how to
--   convert and manipulate such non-empty set.
--   
--   This module essentially re-imports the API of Data.IntSet and
--   its IntSet type, along with semantics and asymptotics. In most
--   situations, asymptotics are different only by a constant factor. In
--   some situations, asmyptotics are even better (constant-time instead of
--   log-time).
--   
--   Because NEIntSet is implemented using IntSet, all of the
--   caveats of using IntSet apply (such as the limitation of the
--   maximum size of sets).
--   
--   All functions take non-empty sets as inputs. In situations where their
--   results can be guarunteed to also be non-empty, they also return
--   non-empty sets. In situations where their results could potentially be
--   empty, IntSet is returned instead.
--   
--   Some functions (partition, split) have modified return
--   types to account for possible configurations of non-emptiness.
--   
--   This module is intended to be imported qualified, to avoid name
--   clashes with Prelude and Data.IntSet functions:
--   
--   
--   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:
--   
--   
--   
- The nonEmptySet smart constructor will convert a
--   IntSet a into a Maybe (NEIntSet
--   a), returning Nothing if the original IntSet was
--   empty.
--   
- You can use the insertIntSet family of functions to insert
--   a value into a IntSet to create a guaranteed
--   NEIntSet.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a IntSet to reveal it as either containing a
--   NEIntSet or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a IntSet and treating it as if it were an
--   NEIntSet.
--   
--   
--   You can convert an NEIntSet into a IntSet with
--   toSet or IsNonEmpty, essentially "obscuring" the
--   non-empty property from the type.
data NEIntSet
type Key = Int

-- | O(1) match, O(log n) usage of contents. 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.
--   
--   For example, you can pattern match on 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:
--   
--   
--   
- This n1 means that the predicate was true for all
--   items.
--   
- That n2 means that the predicate was false for all
--   items.
--   
- These n1 n2 gives n1 (all of the items
--   that were true for the predicate) and n2 (all of the items
--   that were false for the predicate).
--   
--   
--   See also split.
--   
--   
--   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.
--   
--   
--   
- Nothing means that x was the only value in the the
--   original set, and so there are no items before or after it.
--   
- Just (This n1) means x was larger
--   than or equal to all items in the set, and n1 is the entire
--   original set (minus x, if it was present)
--   
- Just (That n2) means x was smaller
--   than or equal to all items in the set, and n2 is the entire
--   original set (minus x, if it was present)
--   
- Just (These n1 n2) gives n1 (the
--   set of all values from the original set less than x) and
--   n2 (the set of all values from the original set greater than
--   x).
--   
--   
--   
--   split 2 (fromList (5 :| [3])) == Just (That  (fromList (3 :| [5]))      )
--   split 3 (fromList (5 :| [3])) == Just (That  (singleton 5)              )
--   split 4 (fromList (5 :| [3])) == Just (These (singleton 3) (singleton 5))
--   split 5 (fromList (5 :| [3])) == Just (This  (singleton 3)              )
--   split 6 (fromList (5 :| [3])) == Just (This  (fromList (3 :| [5]))      )
--   split 5 (singleton 5)         == 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

-- | 
Non-Empty Finite Integer-Indexed Maps (lazy interface)
--   
--   The NEIntMap v type represents a non-empty finite map
--   (sometimes called a dictionary) from integer keys to values of type
--   v. An NEIntMap is strict in its keys but lazy in its
--   values.
--   
--   See documentation for NEIntMap for information on how to
--   convert and manipulate such non-empty maps.
--   
--   This module essentially re-imports the API of Data.IntMap.Lazy
--   and its IntMap type, along with semantics and asymptotics. In
--   most situations, asymptotics are different only by a constant factor.
--   In some situations, asmyptotics are even better (constant-time instead
--   of log-time).
--   
--   Because NEIntMap is implemented using IntMap, all of the
--   caveats of using IntMap apply (such as the limitation of the
--   maximum size of maps).
--   
--   All functions take non-empty maps as inputs. In situations where their
--   results can be guarunteed to also be non-empty, they also return
--   non-empty maps. In situations where their results could potentially be
--   empty, IntMap is returned instead.
--   
--   Some variants of functions (like alter', alterF',
--   adjustMin, adjustMax, adjustMinWithKey,
--   adjustMaxWithKey) are provided in a way restructured to
--   preserve guaruntees of non-empty maps being returned.
--   
--   Some functions (like mapEither, partition, split)
--   have modified return types to account for possible configurations of
--   non-emptiness.
--   
--   This module is intended to be imported qualified, to avoid name
--   clashes with Prelude and Data.IntMap functions:
--   
--   
--   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:
--   
--   
--   
- The nonEmptyMap smart constructor will convert a
--   IntMap k a into a Maybe (NEIntMap k
--   a), returning Nothing if the original IntMap was
--   empty.
--   
- You can use the insertIntMap family of functions to insert
--   a value into a IntMap to create a guaranteed
--   NEIntMap.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a IntMap to reveal it as either containing a
--   NEIntMap or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a IntMap and treating it as if it were an
--   NEIntMap.
--   
--   
--   You can convert an NEIntMap into a IntMap with
--   toMap or IsNonEmpty, essentially "obscuring" the
--   non-empty property from the type.
data NEIntMap a
type Key = Int

-- | O(1) match, O(log n) usage of contents. 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.
--   
--   For example, you can pattern match on 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:
--   
--   
--   
- This n1 means that the predicate was true for all
--   items.
--   
- That n2 means that the predicate was false for all
--   items.
--   
- These n1 n2 gives n1 (all of the items
--   that were true for the predicate) and n2 (all of the items
--   that were false for the predicate).
--   
--   
--   See also split.
--   
--   
--   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:
--   
--   
--   
- This n1 means that the predicate was true for all
--   items, returning the original map.
--   
- That n2 means that the predicate was false for all
--   items, returning the original map.
--   
- These n1 n2 gives n1 (all of the items
--   that were true for the predicate) and n2 (all of the items
--   that were false for the predicate).
--   
--   
--   See also split.
--   
--   
--   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:
--   
--   
--   
- This n1 means that the results were all
--   Left.
--   
- That n2 means that the results were all
--   Right.
--   
- These n1 n2 gives n1 (the map where the
--   results were Left) and n2 (the map where the results
--   were Right)
--   
--   
--   
--   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:
--   
--   
--   
- This n1 means that the results were all
--   Left.
--   
- That n2 means that the results were all
--   Right.
--   
- These n1 n2 gives n1 (the map where the
--   results were Left) and n2 (the map where the results
--   were Right)
--   
--   
--   
--   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.
--   
--   
--   
- Nothing means that k was the only key in the the
--   original map, and so there are no items before or after it.
--   
- Just (This n1) means k was larger
--   than or equal to all items in the map, and n1 is the entire
--   original map (minus k, if it was present)
--   
- Just (That n2) means k was smaller
--   than or equal to all items in the map, and n2 is the entire
--   original map (minus k, if it was present)
--   
- Just (These n1 n2) gives n1 (the
--   map of all keys from the original map less than k) and
--   n2 (the map of all keys from the original map greater than
--   k)
--   
--   
--   
--   split 2 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (fromList ((3,"b") :| [(5,"a")]))  )
--   split 3 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (singleton 5 "a")                  )
--   split 4 (fromList ((5,"a") :| [(3,"b")])) == Just (These (singleton 3 "b") (singleton 5 "a"))
--   split 5 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (singleton 3 "b")                  )
--   split 6 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (fromList ((3,"b") :| [(5,"a")]))  )
--   split 5 (singleton 5 "a")                 == 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:
--   
--   
--   
- The nonEmptyMap smart constructor will convert a
--   Map k a into a Maybe (NEMap k
--   a), returning Nothing if the original Map was
--   empty.
--   
- You can use the insertMap family of functions to insert a
--   value into a Map to create a guaranteed NEMap.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a Map to reveal it as either containing a
--   NEMap or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a Map and treating it as if it were an
--   NEMap.
--   
--   
--   You can convert an NEMap into a Map with toMap or
--   IsNonEmpty, essentially "obscuring" the non-empty property from
--   the type.
data NEMap k a
NEMap :: !k -> a -> !Map k a -> NEMap k a

-- | invariant: must be smaller than smallest key in map
[nemK0] :: NEMap k a -> !k
[nemV0] :: NEMap k a -> a
[nemMap] :: NEMap k a -> !Map 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(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.Ord k => Data.Functor.Alt.Alt (Data.Map.NonEmpty.Internal.NEMap k)
instance Control.Comonad.Comonad (Data.Map.NonEmpty.Internal.NEMap k)
instance (GHC.Internal.Data.Data.Data k, GHC.Internal.Data.Data.Data a, GHC.Classes.Ord k) => GHC.Internal.Data.Data.Data (Data.Map.NonEmpty.Internal.NEMap k a)
instance GHC.Classes.Eq k => Data.Functor.Classes.Eq1 (Data.Map.NonEmpty.Internal.NEMap k)
instance Data.Functor.Classes.Eq2 Data.Map.NonEmpty.Internal.NEMap
instance (GHC.Classes.Eq k, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Map.NonEmpty.Internal.NEMap k a)
instance Data.Foldable1.Foldable1 (Data.Map.NonEmpty.Internal.NEMap k)
instance GHC.Internal.Data.Foldable.Foldable (Data.Map.NonEmpty.Internal.NEMap k)
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.Internal.Base.Functor (Data.Map.NonEmpty.Internal.NEMap k)
instance Data.Functor.Invariant.Invariant (Data.Map.NonEmpty.Internal.NEMap k)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Map.NonEmpty.Internal.NEMap k a)
instance GHC.Classes.Ord k => Data.Functor.Classes.Ord1 (Data.Map.NonEmpty.Internal.NEMap k)
instance Data.Functor.Classes.Ord2 Data.Map.NonEmpty.Internal.NEMap
instance (GHC.Classes.Ord k, GHC.Classes.Ord a) => GHC.Classes.Ord (Data.Map.NonEmpty.Internal.NEMap k a)
instance (GHC.Classes.Ord k, GHC.Internal.Read.Read k) => Data.Functor.Classes.Read1 (Data.Map.NonEmpty.Internal.NEMap k)
instance (GHC.Classes.Ord k, GHC.Internal.Read.Read k, GHC.Internal.Read.Read e) => GHC.Internal.Read.Read (Data.Map.NonEmpty.Internal.NEMap k e)
instance GHC.Classes.Ord k => GHC.Internal.Base.Semigroup (Data.Map.NonEmpty.Internal.NEMap k a)
instance GHC.Internal.Show.Show k => Data.Functor.Classes.Show1 (Data.Map.NonEmpty.Internal.NEMap k)
instance Data.Functor.Classes.Show2 Data.Map.NonEmpty.Internal.NEMap
instance (GHC.Internal.Show.Show k, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (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.Semigroup.Traversable.Class.Traversable1 (Data.Map.NonEmpty.Internal.NEMap k)
instance GHC.Internal.Data.Traversable.Traversable (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:
--   
--   
--   
- Functions that take an NESeq can safely operate on
--   it with the assumption that it has at least value.
--   
- Functions that return an NESeq provide an assurance
--   that the result has at least one value.
--   
--   
--   Data.Sequence.NonEmpty re-exports the API of
--   Data.Sequence, faithfully reproducing asymptotics, typeclass
--   constraints, and semantics. Functions that ensure that input and
--   output maps are both non-empty (like <|) return
--   NESeq, but functions that might potentially return an empty map
--   (like tail) return a Seq instead.
--   
--   You can directly construct an NESeq with the API from
--   Data.Sequence.NonEmpty; it's more or less the same as
--   constructing a normal Seq, except you don't have access to
--   empty. There are also a few ways to construct an NESeq
--   from a Seq:
--   
--   
--   
- The nonEmptySeq smart constructor will convert a
--   Seq a into a Maybe (NESeq a),
--   returning Nothing if the original Seq was empty.
--   
- You can use :<||, :||>, and insertSeqAt
--   to insert a value into a Seq to create a guaranteed
--   NESeq.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a Seq to reveal it as either containing a
--   NESeq or an empty sequence.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a Seq and treating it as if it were an
--   NESeq.
--   
--   
--   You can convert an NESeq into a Seq with toSeq or
--   IsNonEmpty, essentially "obscuring" the non-empty property from
--   the type.
data NESeq a
NESeq :: a -> !Seq a -> NESeq a
[nesHead] :: NESeq a -> a
[nesTail] :: NESeq a -> !Seq a
infixr 5 `NESeq`
infixr 5 `NESeq`

-- | O(1). An abstract constructor for an NESeq that consists
--   of a "head" a and a "tail" Seq a. Similar to
--   :| for NonEmpty.
--   
--   Can be used to match on the head and tail of an NESeq, and also
--   used to construct an NESeq by consing an item to the
--   beginnong of a Seq, ensuring that the result is non-empty.
pattern (:<||) :: a -> Seq a -> NESeq a
infixr 5 :<||

-- | O(1). An abstract constructor for an NESeq that consists
--   of a "init" Seq a and a "last" a. Similar to
--   :| for NonEmpty, but at the end of the list instead of
--   at the beginning.
--   
--   Can be used to match on the init and last of an NESeq, and also
--   used to construct an NESeq by snocing an item to the end
--   of a Seq, ensuring that the result is non-empty.
pattern (:||>) :: Seq a -> a -> NESeq a
infixl 5 :||>

-- | 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). 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)
instance Data.Functor.Alt.Alt Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Base.Applicative Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Bind.Class.Apply Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Bind.Class.Bind Data.Sequence.NonEmpty.Internal.NESeq
instance Control.Comonad.Comonad Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Data.Data.Data a => GHC.Internal.Data.Data.Data (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Functor.Classes.Eq1 Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Functor.Extend.Extend Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Foldable1.Foldable1 Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Data.Foldable.Foldable Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Aeson.Types.FromJSON.FromJSON a => Data.Aeson.Types.FromJSON.FromJSON (Data.Sequence.NonEmpty.Internal.NESeq a)
instance GHC.Internal.Base.Functor Data.Sequence.NonEmpty.Internal.NESeq
instance Data.Functor.Invariant.Invariant Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Control.Monad.Fix.MonadFix Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Base.Monad Data.Sequence.NonEmpty.Internal.NESeq
instance Control.Monad.Zip.MonadZip Data.Sequence.NonEmpty.Internal.NESeq
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Functor.Classes.Ord1 Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Functor.Classes.Read1 Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Read.Read a => GHC.Internal.Read.Read (Data.Sequence.NonEmpty.Internal.NESeq a)
instance GHC.Internal.Base.Semigroup (Data.Sequence.NonEmpty.Internal.NESeq a)
instance Data.Functor.Classes.Show1 Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (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.Semigroup.Traversable.Class.Traversable1 Data.Sequence.NonEmpty.Internal.NESeq
instance GHC.Internal.Data.Traversable.Traversable Data.Sequence.NonEmpty.Internal.NESeq

-- | 
Non-Empty Finite Sequences
--   
--   | An NESeq a is a non-empty (but finite) sequence of
--   values of type a. Generally has the same interface as
--   NonEmpty. This is a non-empty version of Seq from
--   Data.Sequence.
--   
--   The main differences between this type and NonEmpty are:
--   
--   
--   
- You cannot have infinite NESeqs
--   
- You have constant-time consing from either end, and constant-time
--   unconsing as well (through <|, |>, :<||,
--   and :||>)
--   
- Concatenation (><, |><,
--   ><|) is logarithmic-time.
--   
- You have logarithmic-time indexing and updating at a given
--   index.
--   
--   
--   While asymptotics are often better than for NonEmpty, there is
--   a decent constant factor involved in most operations.
--   
--   See documentation for NESeq for information on how to convert
--   and manipulate such non-empty sequences
--   
--   This module essentially re-imports the API of
--   Data.Sequence.Lazy and its Seq type, along with
--   semantics and asymptotics.
--   
--   Because NESeq is implemented using Seq, all of the
--   caveats of using Seq apply.
--   
--   All functions take non-empty sequences as inputs. In situations where
--   their results can be guarunteed to also be non-empty, they also return
--   non-empty maps. In situations where their results could potentially be
--   empty, Seq is returned instead.
--   
--   Some functions (like spanl, spanr, breakl,
--   breakr, partition, splitAt) have modified return
--   types to account for possible configurations of non-emptiness.
--   
--   Some functions (head, last, tail, init)
--   are provided because they are total for non-empty sequences.
--   
--   This module is intended to be imported qualified, to avoid name
--   clashes with Prelude and Data.Sequence functions:
--   
--   
--   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:
--   
--   
--   
- Functions that take an NESeq can safely operate on
--   it with the assumption that it has at least value.
--   
- Functions that return an NESeq provide an assurance
--   that the result has at least one value.
--   
--   
--   Data.Sequence.NonEmpty re-exports the API of
--   Data.Sequence, faithfully reproducing asymptotics, typeclass
--   constraints, and semantics. Functions that ensure that input and
--   output maps are both non-empty (like <|) return
--   NESeq, but functions that might potentially return an empty map
--   (like tail) return a Seq instead.
--   
--   You can directly construct an NESeq with the API from
--   Data.Sequence.NonEmpty; it's more or less the same as
--   constructing a normal Seq, except you don't have access to
--   empty. There are also a few ways to construct an NESeq
--   from a Seq:
--   
--   
--   
- The nonEmptySeq smart constructor will convert a
--   Seq a into a Maybe (NESeq a),
--   returning Nothing if the original Seq was empty.
--   
- You can use :<||, :||>, and insertSeqAt
--   to insert a value into a Seq to create a guaranteed
--   NESeq.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a Seq to reveal it as either containing a
--   NESeq or an empty sequence.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a Seq and treating it as if it were an
--   NESeq.
--   
--   
--   You can convert an NESeq into a Seq with toSeq or
--   IsNonEmpty, essentially "obscuring" the non-empty property from
--   the type.
data NESeq a

-- | O(1). An abstract constructor for an NESeq that consists
--   of a "head" a and a "tail" Seq a. Similar to
--   :| for NonEmpty.
--   
--   Can be used to match on the head and tail of an NESeq, and also
--   used to construct an NESeq by consing an item to the
--   beginnong of a Seq, ensuring that the result is non-empty.
pattern (:<||) :: a -> Seq a -> NESeq a

-- | O(1). An abstract constructor for an NESeq that consists
--   of a "init" Seq a and a "last" a. Similar to
--   :| for NonEmpty, but at the end of the list instead of
--   at the beginning.
--   
--   Can be used to match on the init and last of an NESeq, and also
--   used to construct an NESeq by snocing an item to the end
--   of a Seq, ensuring that the result is non-empty.
pattern (:||>) :: Seq a -> a -> NESeq a
infixr 5 `NESeq`
infixl 5 :||>
infixr 5 :<||

-- | 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.
--   
--   For example, you can pattern match on a Seq:
--   
--   
--   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:
--   
--   
--   
- This ys means that the predicate was true for all
--   items, and ys is the entire original sequence.
--   
- That zs means that the predicate failed on the
--   first item, and zs is the entire original sequence.
--   
- These ys zs gives ys (the prefix of
--   elements that satisfy the predicae) and zs (the remainder of
--   the sequence)
--   
spanl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)

-- | <math> where <math> is the suffix length. spanr,
--   applied to a predicate p and a sequence xs, returns
--   a These based on the point where the predicate fails:
--   
--   
--   
- This ys means that the predicate was true for all
--   items, and ys is the entire original sequence.
--   
- That zs means that the predicate failed on the
--   first item, and zs is the entire original sequence.
--   
- These ys zs gives ys (the suffix of
--   elements that satisfy the predicae) and zs (the remainder of
--   the sequence, before the suffix)
--   
spanr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)

-- | <math> where <math> is the breakpoint index.
--   
--   breakl p is spanl (not . p).
breakl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)

-- | <math> where <math> is the breakpoint index.
--   
--   breakr p is spanr (not . p).
breakr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)

-- | <math>. The partition function takes a predicate
--   p and a sequence xs and returns sequences of those
--   elements which do and do not satisfy the predicate, as a These:
--   
--   
--   
- This ys means that the predicate was true for all
--   items, and ys is the entire original sequence.
--   
- That zs means that the predicate failed on the
--   first item, and zs is the entire original sequence.
--   
- These ys zs gives ys (the sequence of
--   elements for which the predicate was true) and zs (the
--   sequence of elements for which the predicate was false).
--   
partition :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)

-- | <math>. The filter function takes a predicate p
--   and a sequence xs and returns a sequence of those elements
--   which satisfy the predicate.
--   
--   Returns a potentially empty sequence (Seq) in the case that the
--   predicate fails for all items in the sequence.
filter :: (a -> Bool) -> NESeq a -> Seq a

-- | <math>. sort sorts the specified NESeq by the
--   natural ordering of its elements. The sort is stable. If stability is
--   not required, unstableSort can be slightly faster.
sort :: Ord a => NESeq a -> NESeq a

-- | <math>. sortBy sorts the specified NESeq according
--   to the specified comparator. The sort is stable. If stability is not
--   required, unstableSortBy can be slightly faster.
sortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a

-- | <math>. sortOn sorts the specified NESeq by
--   comparing the results of a key function applied to each element.
--   sortOn f is equivalent to sortBy
--   (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 sortOn might be to sort a NESeq of
--   strings according to their length:
--   
--   
--   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.
--   
--   
--   
- This ys means that the given position was longer
--   than the length of the list, and ys is the entire original
--   system.
--   
- That zs means that the given position was zero or
--   smaller, and so zs is the entire original sequence.
--   
- These ys zs gives ys (the sequence of
--   elements before the given position, take n xs) and
--   zs (the sequence of elements after the given position,
--   drop n xs).
--   
splitAt :: Int -> NESeq a -> These (NESeq a) (NESeq a)

-- | elemIndexL finds the leftmost index of the specified element,
--   if it is present, and otherwise Nothing.
elemIndexL :: Eq a => a -> NESeq a -> Maybe Int

-- | elemIndicesL finds the indices of the specified element, from
--   left to right (i.e. in ascending order).
elemIndicesL :: Eq a => a -> NESeq a -> [Int]

-- | elemIndexR finds the rightmost index of the specified element,
--   if it is present, and otherwise Nothing.
elemIndexR :: Eq a => a -> NESeq a -> Maybe Int

-- | elemIndicesR finds the indices of the specified element, from
--   right to left (i.e. in descending order).
elemIndicesR :: Eq a => a -> NESeq a -> [Int]

-- | findIndexL p xs finds the index of the leftmost
--   element that satisfies p, if any exist.
findIndexL :: (a -> Bool) -> NESeq a -> Maybe Int

-- | findIndicesL p finds all indices of elements that
--   satisfy p, in ascending order.
findIndicesL :: (a -> Bool) -> NESeq a -> [Int]

-- | findIndexR p xs finds the index of the rightmost
--   element that satisfies p, if any exist.
findIndexR :: (a -> Bool) -> NESeq a -> Maybe Int

-- | findIndicesR p finds all indices of elements that
--   satisfy p, in descending order.
findIndicesR :: (a -> Bool) -> NESeq a -> [Int]

-- | 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

-- | foldlWithIndex is a version of foldl that also provides
--   access to the index of each element.
foldlWithIndex :: (b -> Int -> a -> b) -> b -> NESeq a -> b

-- | foldrWithIndex is a version of foldr that also provides
--   access to the index of each element.
foldrWithIndex :: (Int -> a -> b -> b) -> b -> NESeq a -> b

-- | A generalization of fmap, mapWithIndex takes a mapping
--   function that also depends on the element's index, and applies it to
--   every element in the sequence.
mapWithIndex :: (Int -> a -> b) -> NESeq a -> NESeq b

-- | traverseWithIndex is a version of traverse that also
--   offers access to the index of each element.
--   
--   Is a more restrictive version of traverseWithIndex1;
--   traverseWithIndex1 should be used whenever possible.
traverseWithIndex :: Applicative f => (Int -> a -> f b) -> NESeq a -> f (NESeq b)

-- | 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>. The reverse of a sequence.
reverse :: NESeq a -> NESeq a

-- | <math>. Intersperse an element between the elements of a
--   sequence.
--   
--   
--   intersperse a empty = empty
--   intersperse a (singleton x) = singleton x
--   intersperse a (fromList [x,y]) = fromList [x,a,y]
--   intersperse a (fromList [x,y,z]) = fromList [x,a,y,a,z]
--   
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:
--   
--   
--   
- The nonEmptySet smart constructor will convert a
--   Set a into a Maybe (NESet a),
--   returning Nothing if the original Set was empty.
--   
- You can use the insertSet family of functions to insert a
--   value into a Set to create a guaranteed NESet.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a Set to reveal it as either containing a
--   NESet or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a Set and treating it as if it were an
--   NESet.
--   
--   
--   You can convert an NESet into a Set with toSet or
--   IsNonEmpty, essentially "obscuring" the non-empty property from
--   the type.
data NESet a
NESet :: !a -> !Set a -> NESet a

-- | invariant: must be smaller than smallest value in set
[nesV0] :: NESet a -> !a
[nesSet] :: NESet a -> !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). 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
instance (GHC.Internal.Data.Data.Data a, GHC.Classes.Ord a) => GHC.Internal.Data.Data.Data (Data.Set.NonEmpty.Internal.NESet a)
instance Data.Functor.Classes.Eq1 Data.Set.NonEmpty.Internal.NESet
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Set.NonEmpty.Internal.NESet a)
instance Data.Foldable1.Foldable1 Data.Set.NonEmpty.Internal.NESet
instance GHC.Internal.Data.Foldable.Foldable Data.Set.NonEmpty.Internal.NESet
instance (Data.Aeson.Types.FromJSON.FromJSON a, GHC.Classes.Ord a) => Data.Aeson.Types.FromJSON.FromJSON (Data.Set.NonEmpty.Internal.NESet a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Set.NonEmpty.Internal.NESet a)
instance Data.Functor.Classes.Ord1 Data.Set.NonEmpty.Internal.NESet
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Set.NonEmpty.Internal.NESet a)
instance (GHC.Internal.Read.Read a, GHC.Classes.Ord a) => GHC.Internal.Read.Read (Data.Set.NonEmpty.Internal.NESet a)
instance GHC.Internal.Base.Semigroup (Data.Set.NonEmpty.Internal.MergeNESet a)
instance GHC.Classes.Ord a => GHC.Internal.Base.Semigroup (Data.Set.NonEmpty.Internal.NESet a)
instance Data.Functor.Classes.Show1 Data.Set.NonEmpty.Internal.NESet
instance GHC.Internal.Show.Show a => GHC.Internal.Show.Show (Data.Set.NonEmpty.Internal.NESet a)
instance Data.Aeson.Types.ToJSON.ToJSON a => Data.Aeson.Types.ToJSON.ToJSON (Data.Set.NonEmpty.Internal.NESet a)

-- | 
Non-Empty Finite Sets
--   
--   The NESet e type represents a non-empty set of
--   elements of type e. Most operations require that e
--   be an instance of the Ord class. A NESet is strict in
--   its elements.
--   
--   See documentation for NESet for information on how to convert
--   and manipulate such non-empty set.
--   
--   This module essentially re-imports the API of Data.Set and its
--   Set type, along with semantics and asymptotics. In most
--   situations, asymptotics are different only by a constant factor. In
--   some situations, asmyptotics are even better (constant-time instead of
--   log-time). All typeclass constraints are identical to their
--   Data.Set counterparts.
--   
--   Because NESet is implemented using Set, all of the
--   caveats of using Set apply (such as the limitation of the
--   maximum size of sets).
--   
--   All functions take non-empty sets as inputs. In situations where their
--   results can be guarunteed to also be non-empty, they also return
--   non-empty sets. In situations where their results could potentially be
--   empty, Set is returned instead.
--   
--   Some functions (partition, spanAntitone, split)
--   have modified return types to account for possible configurations of
--   non-emptiness.
--   
--   This module is intended to be imported qualified, to avoid name
--   clashes with Prelude and Data.Set functions:
--   
--   
--   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:
--   
--   
--   
- The nonEmptySet smart constructor will convert a
--   Set a into a Maybe (NESet a),
--   returning Nothing if the original Set was empty.
--   
- You can use the insertSet family of functions to insert a
--   value into a Set to create a guaranteed NESet.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a Set to reveal it as either containing a
--   NESet or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a Set and treating it as if it were an
--   NESet.
--   
--   
--   You can convert an NESet into a Set with toSet or
--   IsNonEmpty, essentially "obscuring" the non-empty property from
--   the type.
data NESet a

-- | O(1) match, O(log n) usage of contents. 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.
--   
--   For example, you can pattern match on 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 :: 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:
--   
--   
--   
- This n1 means that the predicate never failed for
--   any item, returning the original set
--   
- That n2 means that the predicate failed for the
--   first item, returning the original set
--   
- These n1 n2 gives n1 (the set up to the
--   point where the predicate stops holding) and n2 (the set
--   starting from the point where the predicate stops holding)
--   
--   
--   
--   spanAntitone p xs = partition p xs
--   
--   
--   Note: if p is not actually antitone, then
--   spanAntitone will split the set at some unspecified
--   point where the predicate switches from holding to not holding (where
--   the predicate is seen to hold before the first element and to fail
--   after the last element).
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:
--   
--   
--   
- This n1 means that the predicate was true for all
--   items.
--   
- That n2 means that the predicate was false for all
--   items.
--   
- These n1 n2 gives n1 (all of the items
--   that were true for the predicate) and n2 (all of the items
--   that were false for the predicate).
--   
--   
--   See also split.
--   
--   
--   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.
--   
--   
--   
- Nothing means that x was the only value in the the
--   original set, and so there are no items before or after it.
--   
- Just (This n1) means x was larger
--   than or equal to all items in the set, and n1 is the entire
--   original set (minus x, if it was present)
--   
- Just (That n2) means x was smaller
--   than or equal to all items in the set, and n2 is the entire
--   original set (minus x, if it was present)
--   
- Just (These n1 n2) gives n1 (the
--   set of all values from the original set less than x) and
--   n2 (the set of all values from the original set greater than
--   x).
--   
--   
--   
--   split 2 (fromList (5 :| [3])) == Just (That  (fromList (3 :| [5]))      )
--   split 3 (fromList (5 :| [3])) == Just (That  (singleton 5)              )
--   split 4 (fromList (5 :| [3])) == Just (These (singleton 3) (singleton 5))
--   split 5 (fromList (5 :| [3])) == Just (This  (singleton 3)              )
--   split 6 (fromList (5 :| [3])) == Just (This  (fromList (3 :| [5]))      )
--   split 5 (singleton 5)         == 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.
--   
--   
--   
- This n1 means that there are less than i
--   items in the set, and n1 is the original set.
--   
- That n2 means i was 0; we dropped 0
--   items, so n2 is the original set.
--   
- These n1 n2 gives n1 (taking i
--   items from the original set) and n2 (dropping i
--   items from the original set))
--   
splitAt :: Int -> NESet a -> These (NESet a) (NESet a)

-- | 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 :: Ord b => (a -> b) -> NESet a -> NESet b

-- | O(n). mapMonotonic f s == map f s, but
--   works only when f is strictly increasing. The precondition
--   is not checked. Semi-formally, we have:
--   
--   
--   and [x < y ==> f x < f y | x <- ls, y <- ls]
--                       ==> mapMonotonic f s == map f s
--       where ls = Data.Foldable.toList 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.
--   
--   This function is non-total and will raise a runtime exception if the
--   structure happens to be empty.
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> foldr1 (+) [1..4]
--   10
--   
--   
--   
--   >>> foldr1 (+) []
--   Exception: Prelude.foldr1: empty list
--   
--   
--   
--   >>> foldr1 (+) Nothing
--   *** Exception: foldr1: empty structure
--   
--   
--   
--   >>> foldr1 (-) [1..4]
--   -2
--   
--   
--   
--   >>> foldr1 (&&) [True, False, True, True]
--   False
--   
--   
--   
--   >>> foldr1 (||) [False, False, True, True]
--   True
--   
--   
--   
--   >>> foldr1 (+) [1..]
--   * Hangs forever *
--   
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.
--   
--   This function is non-total and will raise a runtime exception if the
--   structure happens to be empty.
--   
--   
--   foldl1 f = foldl1 f . toList
--   
--   
--   
Examples
--   
--   Basic usage:
--   
--   
--   >>> foldl1 (+) [1..4]
--   10
--   
--   
--   
--   >>> foldl1 (+) []
--   *** Exception: Prelude.foldl1: empty list
--   
--   
--   
--   >>> foldl1 (+) Nothing
--   *** Exception: foldl1: empty structure
--   
--   
--   
--   >>> foldl1 (-) [1..4]
--   -8
--   
--   
--   
--   >>> foldl1 (&&) [True, False, True, True]
--   False
--   
--   
--   
--   >>> foldl1 (||) [False, False, True, True]
--   True
--   
--   
--   
--   >>> foldl1 (+) [1..]
--   * Hangs forever *
--   
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

-- | 
Non-Empty Finite Maps (lazy interface)
--   
--   The NEMap k v type represents a non-empty finite map
--   (sometimes called a dictionary) from keys of type k to values
--   of type v. An NEMap is strict in its keys but lazy in
--   its values.
--   
--   See documentation for NEMap for information on how to convert
--   and manipulate such non-empty maps.
--   
--   This module essentially re-imports the API of Data.Map.Lazy and
--   its Map type, along with semantics and asymptotics. In most
--   situations, asymptotics are different only by a constant factor. In
--   some situations, asmyptotics are even better (constant-time instead of
--   log-time). All typeclass constraints are identical to their
--   Data.Map counterparts.
--   
--   Because NEMap is implemented using Map, all of the
--   caveats of using Map apply (such as the limitation of the
--   maximum size of maps).
--   
--   All functions take non-empty maps as inputs. In situations where their
--   results can be guarunteed to also be non-empty, they also return
--   non-empty maps. In situations where their results could potentially be
--   empty, Map is returned instead.
--   
--   Some variants of functions (like alter', alterF',
--   adjustAt, adjustMin, adjustMax,
--   adjustMinWithKey, adjustMaxWithKey) are provided in a
--   way restructured to preserve guaruntees of non-empty maps being
--   returned.
--   
--   Some functions (like mapEither, partition,
--   spanAntitone, split) have modified return types to
--   account for possible configurations of non-emptiness.
--   
--   This module is intended to be imported qualified, to avoid name
--   clashes with Prelude and Data.Map functions:
--   
--   
--   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:
--   
--   
--   
- The nonEmptyMap smart constructor will convert a
--   Map k a into a Maybe (NEMap k
--   a), returning Nothing if the original Map was
--   empty.
--   
- You can use the insertMap family of functions to insert a
--   value into a Map to create a guaranteed NEMap.
--   
- You can use the IsNonEmpty and IsEmpty patterns to
--   "pattern match" on a Map to reveal it as either containing a
--   NEMap or an empty map.
--   
- withNonEmpty offers a continuation-based interface for
--   deconstructing a Map and treating it as if it were an
--   NEMap.
--   
--   
--   You can convert an NEMap into a Map with toMap or
--   IsNonEmpty, essentially "obscuring" the non-empty property from
--   the type.
data NEMap k a

-- | O(1) match, O(log n) usage of contents. 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.
--   
--   For example, you can pattern match on 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:
--   
--   
--   
- This n1 means that the predicate was true for all
--   items.
--   
- That n2 means that the predicate was false for all
--   items.
--   
- These n1 n2 gives n1 (all of the items
--   that were true for the predicate) and n2 (all of the items
--   that were false for the predicate).
--   
--   
--   See also split.
--   
--   
--   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:
--   
--   
--   
- This n1 means that the predicate was true for all
--   items, returning the original map.
--   
- That n2 means that the predicate was false for all
--   items, returning the original map.
--   
- These n1 n2 gives n1 (all of the items
--   that were true for the predicate) and n2 (all of the items
--   that were false for the predicate).
--   
--   
--   See also split.
--   
--   
--   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:
--   
--   
--   
- This n1 means that the predicate never failed for
--   any item, returning the original map.
--   
- That n2 means that the predicate failed for the
--   first item, returning the original map.
--   
- These n1 n2 gives n1 (the map up to the
--   point where the predicate on the keys stops holding) and n2
--   (the map starting from the point where the predicate stops
--   holding)
--   
--   
--   
--   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:
--   
--   
--   
- This n1 means that the results were all
--   Left.
--   
- That n2 means that the results were all
--   Right.
--   
- These n1 n2 gives n1 (the map where the
--   results were Left) and n2 (the map where the results
--   were Right)
--   
--   
--   
--   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:
--   
--   
--   
- This n1 means that the results were all
--   Left.
--   
- That n2 means that the results were all
--   Right.
--   
- These n1 n2 gives n1 (the map where the
--   results were Left) and n2 (the map where the results
--   were Right)
--   
--   
--   
--   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.
--   
--   
--   
- Nothing means that k was the only key in the the
--   original map, and so there are no items before or after it.
--   
- Just (This n1) means k was larger
--   than or equal to all items in the map, and n1 is the entire
--   original map (minus k, if it was present)
--   
- Just (That n2) means k was smaller
--   than or equal to all items in the map, and n2 is the entire
--   original map (minus k, if it was present)
--   
- Just (These n1 n2) gives n1 (the
--   map of all keys from the original map less than k) and
--   n2 (the map of all keys from the original map greater than
--   k)
--   
--   
--   
--   split 2 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (fromList ((3,"b") :| [(5,"a")]))  )
--   split 3 (fromList ((5,"a") :| [(3,"b")])) == Just (That  (singleton 5 "a")                  )
--   split 4 (fromList ((5,"a") :| [(3,"b")])) == Just (These (singleton 3 "b") (singleton 5 "a"))
--   split 5 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (singleton 3 "b")                  )
--   split 6 (fromList ((5,"a") :| [(3,"b")])) == Just (This  (fromList ((3,"b") :| [(5,"a")]))  )
--   split 5 (singleton 5 "a")                 == 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.
--   
--   
--   
- This n1 means that there are less than i
--   items in the map, and n1 is the original map.
--   
- That n2 means i was 0; we dropped 0
--   items, so n2 is the original map.
--   
- These n1 n2 gives n1 (taking i
--   items from the original map) and n2 (dropping i
--   items from the original map))
--   
splitAt :: Int -> NEMap k a -> These (NEMap k a) (NEMap k a)

-- | 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.Map.lookupMin and
--   Data.Map.findMin, as well.
--   
--   
--   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

-- | 
Non-Empty Typeclass
--   
--   Provides the typeclass HasNonEmpty, which abstracts over
--   different types which have a "non-empty" variant.
--   
--   Used to convert between and in between possibly-empty and non-empty
--   types. Instances are provided for all modules in this package, as well
--   as for NonEmpty in base and NonEmptyVector.
module Data.Containers.NonEmpty

-- | If s is an instance of HasNonEmpty, it means that
--   there is a corresponding "non-empty" version of s,
--   NE s.
--   
--   In order for things to be well-behaved, we expect that nonEmpty
--   and maybe empty fromNonEmpty should form an
--   isomorphism (or that withNonEmpty empty
--   fromNonEmpty == id. In addition, the following properties
--   should hold for most exectations:
--   
--   
--   
- 
(x == empty) ==> isEmpty x

--   
- 
(x == empty) ==> isNothing (nonEmpty x)

--   
- 
isEmpty x ==> isNothing (nonEmpty x)

--   
- 
unsafeToNonEmpty x == fromJust (nonEmpty x)

--   
- Usually, not (isEmpty x) ==> isJust (nonEmpty x), but
--   this isn't necessary.
--   
class HasNonEmpty s where {
    
    -- | <tt><a>NE</a> s</tt> is the "non-empty" version of <tt>s</tt>.
    type NE s = (t :: Type) | t -> s;
}

-- | "Smart constructor" for NE s given a (potentailly
--   empty) s. Will return Nothing if the s was
--   empty, and Just n if the s was not empty,
--   with n :: NE s.
--   
--   Should form an isomorphism with maybe empty
--   fromNonEmpty.
nonEmpty :: HasNonEmpty s => s -> Maybe (NE s)

-- | Convert a NE s (non-empty s) back into an
--   s, "obscuring" its non-emptiness from its type.
fromNonEmpty :: HasNonEmpty s => NE s -> s

-- | Continuation-based version of nonEmpty, which can be more
--   efficient in certain situations.
--   
--   withNonEmpty empty fromNonEmpty should
--   be id.
withNonEmpty :: HasNonEmpty s => r -> (NE s -> r) -> s -> r

-- | An empty s.
empty :: HasNonEmpty s => s

-- | Check if an s is empty.
isEmpty :: HasNonEmpty s => s -> Bool

-- | Unsafely coerce an s into an NE s (non-empty
--   s). Is undefined (throws a runtime exception when evaluation
--   is attempted) when the s is empty.
unsafeToNonEmpty :: HasNonEmpty s => s -> NE 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.
--   
--   For example, you can pattern match on a list to get a NonEmpty
--   (non-empty list):
--   
--   
--   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 (Data.IntMap.Internal.IntMap a)
instance Data.Containers.NonEmpty.HasNonEmpty Data.IntSet.Internal.IntSet
instance Data.Containers.NonEmpty.HasNonEmpty [a]
instance Data.Containers.NonEmpty.HasNonEmpty (Data.Map.Internal.Map k a)
instance Data.Containers.NonEmpty.HasNonEmpty (Data.Sequence.Internal.Seq a)
instance Data.Containers.NonEmpty.HasNonEmpty (Data.Set.Internal.Set a)
instance Data.Containers.NonEmpty.HasNonEmpty (Data.Vector.Vector a)
