    {-# LANGUAGE BangPatterns #-}
    {-# LANGUAGE EmptyCase #-}
    {-# LANGUAGE LambdaCase #-}
    {-# LANGUAGE PatternSynonyms #-}
    {-# LANGUAGE ViewPatterns #-}

    -- |
    -- Module      : Data.Map.NonEmpty
    -- Copyright   : (c) Justin Le 2018
    -- License     : BSD3
    --
    -- Maintainer  : justin@jle.im
    -- Stability   : experimental
    -- Portability : non-portable
    --
    -- = 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 (
      -- * Non-Empty Map type
      NEMap,

      -- ** Conversions between empty and non-empty maps
      pattern IsNonEmpty,
      pattern IsEmpty,
      nonEmptyMap,
      toMap,
      withNonEmpty,
      insertMap,
      insertMapWith,
      insertMapWithKey,
      insertMapMin,
      insertMapMax,
      unsafeFromMap,

      -- * Construction
      singleton,
      fromSet,

      -- ** From Unordered Lists
      fromList,
      fromListWith,
      fromListWithKey,

      -- ** From Ascending Lists
      fromAscList,
      fromAscListWith,
      fromAscListWithKey,
      fromDistinctAscList,

      -- ** From Descending Lists
      fromDescList,
      fromDescListWith,
      fromDescListWithKey,
      fromDistinctDescList,

      -- * Insertion
      insert,
      insertWith,
      insertWithKey,
      insertLookupWithKey,

      -- * Deletion\/Update
      delete,
      adjust,
      adjustWithKey,
      update,
      updateWithKey,
      updateLookupWithKey,
      alter,
      alterF,
      alter',
      alterF',

      -- * Query

      -- ** Lookup
      lookup,
      (!?),
      (!),
      findWithDefault,
      member,
      notMember,
      lookupLT,
      lookupGT,
      lookupLE,
      lookupGE,
      absurdNEMap,

      -- ** Size
      size,

      -- * Combine

      -- ** Union
      union,
      unionWith,
      unionWithKey,
      unions,
      unionsWith,

      -- ** Difference
      difference,
      (\\),
      differenceWith,
      differenceWithKey,

      -- ** Intersection
      intersection,
      intersectionWith,
      intersectionWithKey,
      -- -- ** Unsafe general combining function
      -- , mergeWithKey

      -- * Traversal

      -- ** Map
      map,
      mapWithKey,
      traverseWithKey1,
      traverseWithKey,
      traverseMaybeWithKey1,
      traverseMaybeWithKey,
      mapAccum,
      mapAccumWithKey,
      mapAccumRWithKey,
      mapKeys,
      mapKeysWith,
      mapKeysMonotonic,

      -- * Folds
      foldr,
      foldl,
      foldr1,
      foldl1,
      foldrWithKey,
      foldlWithKey,
      foldMapWithKey,

      -- ** Strict folds
      foldr',
      foldr1',
      foldl',
      foldl1',
      foldrWithKey',
      foldlWithKey',

      -- * Conversion
      elems,
      keys,
      assocs,
      keysSet,

      -- ** Lists
      toList,

      -- ** Ordered lists
      toAscList,
      toDescList,

      -- * Filter
      filter,
      filterWithKey,
      restrictKeys,
      withoutKeys,
      partition,
      partitionWithKey,
      takeWhileAntitone,
      dropWhileAntitone,
      spanAntitone,
      mapMaybe,
      mapMaybeWithKey,
      mapEither,
      mapEitherWithKey,
      split,
      splitLookup,
      splitRoot,

      -- * Submap
      isSubmapOf,
      isSubmapOfBy,
      isProperSubmapOf,
      isProperSubmapOfBy,

      -- * Indexed
      lookupIndex,
      findIndex,
      elemAt,
      updateAt,
      adjustAt,
      deleteAt,
      take,
      drop,
      splitAt,

      -- * Min\/Max
      findMin,
      findMax,
      deleteMin,
      deleteMax,
      deleteFindMin,
      deleteFindMax,
      updateMin,
      updateMax,
      adjustMin,
      adjustMax,
      updateMinWithKey,
      updateMaxWithKey,
      adjustMinWithKey,
      adjustMaxWithKey,
      minView,
      maxView,

      -- * Debugging
      valid,
    ) where

    import Control.Applicative
    import Data.Bifunctor
    import qualified Data.Foldable as F
    import Data.Function
    import Data.Functor.Apply
    import Data.Functor.Identity
    import Data.List.NonEmpty (NonEmpty (..))
    import qualified Data.List.NonEmpty as NE
    import Data.Map (Map)
    import qualified Data.Map as M
    import Data.Map.NonEmpty.Internal
    import Data.Maybe hiding (mapMaybe)
    import qualified Data.Maybe as Maybe
    import Data.Semigroup.Foldable (Foldable1)
    import qualified Data.Semigroup.Foldable as F1
    import Data.Set (Set)
    import qualified Data.Set as S
    import Data.Set.NonEmpty.Internal (NESet (..))
    import Data.These
    import Data.Void
    import Prelude hiding (Foldable (..), drop, filter, lookup, map, splitAt, take)

    -- | /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
    pattern $mIsNonEmpty :: forall {r} {k} {a}.
    Map k a -> (NEMap k a -> r) -> ((# #) -> r) -> r
    $bIsNonEmpty :: forall k a. NEMap k a -> Map k a
    IsNonEmpty n <- (nonEmptyMap -> Just n)
      where
        IsNonEmpty NEMap k a
    n = NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n

    -- | /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 'Data.Map.empty'.
    --
    -- See 'IsNonEmpty' for more information.
    pattern IsEmpty :: Map k a
    pattern $mIsEmpty :: forall {r} {k} {a}. Map k a -> ((# #) -> r) -> ((# #) -> r) -> r
    $bIsEmpty :: forall k a. Map k a
    IsEmpty <- (M.null -> True)
      where
        IsEmpty = Map k a
    forall k a. Map k a
    M.empty

    {-# COMPLETE IsNonEmpty, IsEmpty #-}

    -- | /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
    unsafeFromMap :: forall k a. Map k a -> NEMap k a
    unsafeFromMap = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
    forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
    withNonEmpty NEMap k a
    forall {a}. a
    e NEMap k a -> NEMap k a
    forall a. a -> a
    id
      where
        e :: a
    e = [Char] -> a
    forall a. [Char] -> a
    errorWithoutStackTrace [Char]
    "NEMap.unsafeFromMap: empty map"
    {-# INLINE unsafeFromMap #-}

    -- | /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
    fromSet :: forall k a. (k -> a) -> NESet k -> NEMap k a
    fromSet k -> a
    f (NESet k
    k Set k
    ks) = k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k (k -> a
    f k
    k) ((k -> a) -> Set k -> Map k a
    forall k a. (k -> a) -> Set k -> Map k a
    M.fromSet k -> a
    f Set k
    ks)
    {-# INLINE fromSet #-}

    -- | /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
    lookup :: forall k a. Ord k => k -> NEMap k a -> Maybe a
    lookup k
    k (NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v
      Ordering
    GT -> k -> Map k a -> Maybe a
    forall k a. Ord k => k -> Map k a -> Maybe a
    M.lookup k
    k Map k a
    m
    {-# INLINE lookup #-}

    -- | /O(log n)/. Find the value at a key. Returns 'Nothing' when the
    -- element can not be found.
    --
    -- prop> fromList ((5, 'a') :| [(3, 'b')]) !? 1 == Nothing
    -- prop> fromList ((5, 'a') :| [(3, 'b')]) !? 5 == Just 'a'
    (!?) :: Ord k => NEMap k a -> k -> Maybe a
    !? :: forall k a. Ord k => NEMap k a -> k -> Maybe a
    (!?) = (k -> NEMap k a -> Maybe a) -> NEMap k a -> k -> Maybe a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip k -> NEMap k a -> Maybe a
    forall k a. Ord k => k -> NEMap k a -> Maybe a
    lookup
    {-# INLINE (!?) #-}

    -- | /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
    ! :: forall k a. Ord k => NEMap k a -> k -> a
    (!) NEMap k a
    m k
    k = a -> Maybe a -> a
    forall a. a -> Maybe a -> a
    fromMaybe a
    forall {a}. a
    e (Maybe a -> a) -> Maybe a -> a
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    m NEMap k a -> k -> Maybe a
    forall k a. Ord k => NEMap k a -> k -> Maybe a
    !? k
    k
      where
        e :: a
    e = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NEMap.!: given key is not an element in the map"
    {-# INLINE (!) #-}

    infixl 9 !?
    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
    findWithDefault :: forall k a. Ord k => a -> k -> NEMap k a -> a
    findWithDefault a
    def k
    k (NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> a
    def
      Ordering
    EQ -> a
    v
      Ordering
    GT -> a -> k -> Map k a -> a
    forall k a. Ord k => a -> k -> Map k a -> a
    M.findWithDefault a
    def k
    k Map k a
    m
    {-# INLINE findWithDefault #-}

    -- | /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
    member :: forall k a. Ord k => k -> NEMap k a -> Bool
    member k
    k (NEMap k
    k0 a
    _ Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> Bool
    False
      Ordering
    EQ -> Bool
    True
      Ordering
    GT -> k -> Map k a -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    M.member k
    k Map k a
    m
    {-# INLINE member #-}

    -- | /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
    notMember :: forall k a. Ord k => k -> NEMap k a -> Bool
    notMember k
    k (NEMap k
    k0 a
    _ Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> Bool
    True
      Ordering
    EQ -> Bool
    False
      Ordering
    GT -> k -> Map k a -> Bool
    forall k a. Ord k => k -> Map k a -> Bool
    M.notMember k
    k Map k a
    m
    {-# INLINE notMember #-}

    -- | /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)
    lookupLT :: forall k a. Ord k => k -> NEMap k a -> Maybe (k, a)
    lookupLT k
    k (NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> Maybe (k, a)
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> Maybe (k, a)
    forall a. Maybe a
    Nothing
      Ordering
    GT -> k -> Map k a -> Maybe (k, a)
    forall k v. Ord k => k -> Map k v -> Maybe (k, v)
    M.lookupLT k
    k Map k a
    m Maybe (k, a) -> Maybe (k, a) -> Maybe (k, a)
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (k, a) -> Maybe (k, a)
    forall a. a -> Maybe a
    Just (k
    k0, a
    v)
    {-# INLINE lookupLT #-}

    -- | /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)
    lookupGT :: forall k a. Ord k => k -> NEMap k a -> Maybe (k, a)
    lookupGT k
    k (NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> (k, a) -> Maybe (k, a)
    forall a. a -> Maybe a
    Just (k
    k0, a
    v)
      Ordering
    EQ -> Map k a -> Maybe (k, a)
    forall k a. Map k a -> Maybe (k, a)
    M.lookupMin Map k a
    m
      Ordering
    GT -> k -> Map k a -> Maybe (k, a)
    forall k v. Ord k => k -> Map k v -> Maybe (k, v)
    M.lookupGT k
    k Map k a
    m
    {-# INLINE lookupGT #-}

    -- | /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)
    lookupLE :: forall k a. Ord k => k -> NEMap k a -> Maybe (k, a)
    lookupLE k
    k (NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> Maybe (k, a)
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> (k, a) -> Maybe (k, a)
    forall a. a -> Maybe a
    Just (k
    k0, a
    v)
      Ordering
    GT -> k -> Map k a -> Maybe (k, a)
    forall k v. Ord k => k -> Map k v -> Maybe (k, v)
    M.lookupLE k
    k Map k a
    m Maybe (k, a) -> Maybe (k, a) -> Maybe (k, a)
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> (k, a) -> Maybe (k, a)
    forall a. a -> Maybe a
    Just (k
    k0, a
    v)
    {-# INLINE lookupLE #-}

    -- | /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)
    lookupGE :: forall k a. Ord k => k -> NEMap k a -> Maybe (k, a)
    lookupGE k
    k (NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> (k, a) -> Maybe (k, a)
    forall a. a -> Maybe a
    Just (k
    k0, a
    v)
      Ordering
    EQ -> (k, a) -> Maybe (k, a)
    forall a. a -> Maybe a
    Just (k
    k0, a
    v)
      Ordering
    GT -> k -> Map k a -> Maybe (k, a)
    forall k v. Ord k => k -> Map k v -> Maybe (k, v)
    M.lookupGE k
    k Map k a
    m
    {-# INLINE lookupGE #-}

    -- | /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
    unionWith :: forall k a.
    Ord k =>
    (a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
    unionWith a -> a -> a
    f n1 :: NEMap k a
    n1@(NEMap k
    k1 a
    v1 Map k a
    m1) n2 :: NEMap k a
    n2@(NEMap k
    k2 a
    v2 Map k a
    m2) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k1 k
    k2 of
      Ordering
    LT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k1 a
    v1 (Map k a -> NEMap k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> Map k a -> Map k a -> Map k a
    forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
    M.unionWith a -> a -> a
    f Map k a
    m1 (Map k a -> Map k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    n2
      Ordering
    EQ -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k1 (a -> a -> a
    f a
    v1 a
    v2) (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> Map k a -> Map k a -> Map k a
    forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
    M.unionWith a -> a -> a
    f Map k a
    m1 (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m2
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k2 a
    v2 (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> a) -> Map k a -> Map k a -> Map k a
    forall k a. Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a
    M.unionWith a -> a -> a
    f (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n1) (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m2
    {-# INLINE unionWith #-}

    -- | /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
    unionWithKey :: forall k a.
    Ord k =>
    (k -> a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
    unionWithKey k -> a -> a -> a
    f n1 :: NEMap k a
    n1@(NEMap k
    k1 a
    v1 Map k a
    m1) n2 :: NEMap k a
    n2@(NEMap k
    k2 a
    v2 Map k a
    m2) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k1 k
    k2 of
      Ordering
    LT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k1 a
    v1 (Map k a -> NEMap k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
    M.unionWithKey k -> a -> a -> a
    f Map k a
    m1 (Map k a -> Map k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    n2
      Ordering
    EQ -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k1 (k -> a -> a -> a
    f k
    k1 a
    v1 a
    v2) (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
    M.unionWithKey k -> a -> a -> a
    f Map k a
    m1 (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m2
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k2 a
    v2 (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> Map k a -> Map k a -> Map k a
    M.unionWithKey k -> a -> a -> a
    f (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n1) (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m2
    {-# INLINE unionWithKey #-}

    -- | The union of a non-empty list of maps, with a combining operation:
    --   (@'unionsWith' f == 'Data.Foldable.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
    unionsWith :: forall (f :: * -> *) k a.
    (Foldable1 f, Ord k) =>
    (a -> a -> a) -> f (NEMap k a) -> NEMap k a
    unionsWith a -> a -> a
    f (f (NEMap k a) -> NonEmpty (NEMap k a)
    forall a. f a -> NonEmpty a
    forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
    F1.toNonEmpty -> (NEMap k a
    m :| [NEMap k a]
    ms)) = (NEMap k a -> NEMap k a -> NEMap k a)
    -> NEMap k a -> [NEMap k a] -> NEMap k a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    F.foldl' ((a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
    forall k a.
    Ord k =>
    (a -> a -> a) -> NEMap k a -> NEMap k a -> NEMap k a
    unionWith a -> a -> a
    f) NEMap k a
    m [NEMap k a]
    ms
    {-# INLINE unionsWith #-}

    -- | /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
    difference :: forall k a b. Ord k => NEMap k a -> NEMap k b -> Map k a
    difference n1 :: NEMap k a
    n1@(NEMap k
    k1 a
    v1 Map k a
    m1) n2 :: NEMap k b
    n2@(NEMap k
    k2 b
    _ Map k b
    m2) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k1 k
    k2 of
      -- k1 is not in n2, so cannot be deleted
      Ordering
    LT -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k1 a
    v1 (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m1 Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    `M.difference` NEMap k b -> Map k b
    forall k a. NEMap k a -> Map k a
    toMap NEMap k b
    n2
      -- k2 deletes k1, and only k1
      Ordering
    EQ -> Map k a
    m1 Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    `M.difference` Map k b
    m2
      -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
      Ordering
    GT -> NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n1 Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    `M.difference` Map k b
    m2
    {-# INLINE difference #-}

    -- | Same as 'difference'.
    (\\) ::
      Ord k =>
      NEMap k a ->
      NEMap k b ->
      Map k a
    \\ :: forall k a b. Ord k => NEMap k a -> NEMap k b -> Map k a
    (\\) = NEMap k a -> NEMap k b -> Map k a
    forall k a b. Ord k => NEMap k a -> NEMap k b -> Map k a
    difference
    {-# INLINE (\\) #-}

    -- | /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
    differenceWith :: forall k a b.
    Ord k =>
    (a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
    differenceWith a -> b -> Maybe a
    f = (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
    forall k a b.
    Ord k =>
    (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
    differenceWithKey ((a -> b -> Maybe a) -> k -> a -> b -> Maybe a
    forall a b. a -> b -> a
    const a -> b -> Maybe a
    f)
    {-# INLINE differenceWith #-}

    -- | /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
    differenceWithKey :: forall k a b.
    Ord k =>
    (k -> a -> b -> Maybe a) -> NEMap k a -> NEMap k b -> Map k a
    differenceWithKey k -> a -> b -> Maybe a
    f n1 :: NEMap k a
    n1@(NEMap k
    k1 a
    v1 Map k a
    m1) n2 :: NEMap k b
    n2@(NEMap k
    k2 b
    v2 Map k b
    m2) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k1 k
    k2 of
      -- k1 is not in n2, so cannot be deleted
      Ordering
    LT -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k1 a
    v1 (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
    forall k a b.
    Ord k =>
    (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
    M.differenceWithKey k -> a -> b -> Maybe a
    f Map k a
    m1 (NEMap k b -> Map k b
    forall k a. NEMap k a -> Map k a
    toMap NEMap k b
    n2)
      -- k2 deletes k1, and only k1
      Ordering
    EQ -> (Map k a -> Map k a)
    -> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a -> Map k a
    forall a. a -> a
    id (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k1) (k -> a -> b -> Maybe a
    f k
    k1 a
    v1 b
    v2) ((k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
    forall k a b.
    Ord k =>
    (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
    M.differenceWithKey k -> a -> b -> Maybe a
    f Map k a
    m1 Map k b
    m2)
      -- k2 is not in n1, so cannot delete anything, so we can just difference n1 // m2.
      Ordering
    GT -> (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
    forall k a b.
    Ord k =>
    (k -> a -> b -> Maybe a) -> Map k a -> Map k b -> Map k a
    M.differenceWithKey k -> a -> b -> Maybe a
    f (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n1) Map k b
    m2
    {-# INLINE differenceWithKey #-}

    -- | /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
    intersection :: forall k a b. Ord k => NEMap k a -> NEMap k b -> Map k a
    intersection n1 :: NEMap k a
    n1@(NEMap k
    k1 a
    v1 Map k a
    m1) n2 :: NEMap k b
    n2@(NEMap k
    k2 b
    _ Map k b
    m2) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k1 k
    k2 of
      -- k1 is not in n2
      Ordering
    LT -> Map k a
    m1 Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    `M.intersection` NEMap k b -> Map k b
    forall k a. NEMap k a -> Map k a
    toMap NEMap k b
    n2
      -- k1 and k2 are a part of the result
      Ordering
    EQ -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k1 a
    v1 (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m1 Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    `M.intersection` Map k b
    m2
      -- k2 is not in n1
      Ordering
    GT -> NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n1 Map k a -> Map k b -> Map k a
    forall k a b. Ord k => Map k a -> Map k b -> Map k a
    `M.intersection` Map k b
    m2
    {-# INLINE intersection #-}

    -- | /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
    intersectionWith :: forall k a b c.
    Ord k =>
    (a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c
    intersectionWith a -> b -> c
    f = (k -> a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c
    forall k a b c.
    Ord k =>
    (k -> a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c
    intersectionWithKey ((a -> b -> c) -> k -> a -> b -> c
    forall a b. a -> b -> a
    const a -> b -> c
    f)
    {-# INLINE intersectionWith #-}

    -- | /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
    intersectionWithKey :: forall k a b c.
    Ord k =>
    (k -> a -> b -> c) -> NEMap k a -> NEMap k b -> Map k c
    intersectionWithKey k -> a -> b -> c
    f n1 :: NEMap k a
    n1@(NEMap k
    k1 a
    v1 Map k a
    m1) n2 :: NEMap k b
    n2@(NEMap k
    k2 b
    v2 Map k b
    m2) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k1 k
    k2 of
      -- k1 is not in n2
      Ordering
    LT -> (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
    forall k a b c.
    Ord k =>
    (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
    M.intersectionWithKey k -> a -> b -> c
    f Map k a
    m1 (NEMap k b -> Map k b
    forall k a. NEMap k a -> Map k a
    toMap NEMap k b
    n2)
      -- k1 and k2 are a part of the result
      Ordering
    EQ -> k -> c -> Map k c -> Map k c
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k1 (k -> a -> b -> c
    f k
    k1 a
    v1 b
    v2) (Map k c -> Map k c) -> Map k c -> Map k c
    forall a b. (a -> b) -> a -> b
    $ (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
    forall k a b c.
    Ord k =>
    (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
    M.intersectionWithKey k -> a -> b -> c
    f Map k a
    m1 Map k b
    m2
      -- k2 is not in n1
      Ordering
    GT -> (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
    forall k a b c.
    Ord k =>
    (k -> a -> b -> c) -> Map k a -> Map k b -> Map k c
    M.intersectionWithKey k -> a -> b -> c
    f (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n1) Map k b
    m2
    {-# INLINE intersectionWithKey #-}

    -- | /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
    foldr1' :: forall a k. (a -> a -> a) -> NEMap k a -> a
    foldr1' a -> a -> a
    f (NEMap k
    _ a
    v Map k a
    m) = case Map k a -> Maybe (a, Map k a)
    forall k a. Map k a -> Maybe (a, Map k a)
    M.maxView Map k a
    m of
      Maybe (a, Map k a)
    Nothing -> a
    v
      Just (a
    y, Map k a
    m') -> let !z :: a
    z = (a -> a -> a) -> a -> Map k a -> a
    forall a b k. (a -> b -> b) -> b -> Map k a -> b
    M.foldr' a -> a -> a
    f a
    y Map k a
    m' in a
    v a -> a -> a
    `f` a
    z
    {-# INLINE foldr1' #-}

    -- | /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
    foldl1' :: forall a k. (a -> a -> a) -> NEMap k a -> a
    foldl1' a -> a -> a
    f (NEMap k
    _ a
    v Map k a
    m) = (a -> a -> a) -> a -> Map k a -> a
    forall a b k. (a -> b -> a) -> a -> Map k b -> a
    M.foldl' a -> a -> a
    f a
    v Map k a
    m
    {-# INLINE foldl1' #-}

    -- | /O(n)/. Fold the keys and values in the map using the given right-associative
    -- binary operator, such that
    -- @'foldrWithKey' f z == 'Prelude.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
    foldrWithKey :: forall k a b. (k -> a -> b -> b) -> b -> NEMap k a -> b
    foldrWithKey k -> a -> b -> b
    f b
    z (NEMap k
    k a
    v Map k a
    m) = k -> a -> b -> b
    f k
    k a
    v (b -> b) -> (Map k a -> b) -> Map k a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> b -> b) -> b -> Map k a -> b
    forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
    M.foldrWithKey k -> a -> b -> b
    f b
    z (Map k a -> b) -> Map k a -> b
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE foldrWithKey #-}

    -- | /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
    foldrWithKey' :: forall k a b. (k -> a -> b -> b) -> b -> NEMap k a -> b
    foldrWithKey' k -> a -> b -> b
    f b
    z (NEMap k
    k a
    v Map k a
    m) = k -> a -> b -> b
    f k
    k a
    v b
    y
      where
        !y :: b
    y = (k -> a -> b -> b) -> b -> Map k a -> b
    forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
    M.foldrWithKey k -> a -> b -> b
    f b
    z Map k a
    m
    {-# INLINE foldrWithKey' #-}

    -- | /O(n)/. Fold the keys and values in the map using the given left-associative
    -- binary operator, such that
    -- @'foldlWithKey' f z == 'Prelude.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
    foldlWithKey :: forall a k b. (a -> k -> b -> a) -> a -> NEMap k b -> a
    foldlWithKey a -> k -> b -> a
    f a
    z (NEMap k
    k b
    v Map k b
    m) = (a -> k -> b -> a) -> a -> Map k b -> a
    forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
    M.foldlWithKey a -> k -> b -> a
    f (a -> k -> b -> a
    f a
    z k
    k b
    v) Map k b
    m
    {-# INLINE foldlWithKey #-}

    -- | /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
    foldlWithKey' :: forall a k b. (a -> k -> b -> a) -> a -> NEMap k b -> a
    foldlWithKey' a -> k -> b -> a
    f a
    z (NEMap k
    k b
    v Map k b
    m) = (a -> k -> b -> a) -> a -> Map k b -> a
    forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
    M.foldlWithKey' a -> k -> b -> a
    f a
    x Map k b
    m
      where
        !x :: a
    x = a -> k -> b -> a
    f a
    z k
    k b
    v
    {-# INLINE foldlWithKey' #-}

    -- | /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
    keys :: forall k a. NEMap k a -> NonEmpty k
    keys (NEMap k
    k a
    _ Map k a
    m) = k
    k k -> [k] -> NonEmpty k
    forall a. a -> [a] -> NonEmpty a
    :| Map k a -> [k]
    forall k a. Map k a -> [k]
    M.keys Map k a
    m
    {-# INLINE keys #-}

    -- | /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)
    assocs :: forall k a. NEMap k a -> NonEmpty (k, a)
    assocs = NEMap k a -> NonEmpty (k, a)
    forall k a. NEMap k a -> NonEmpty (k, a)
    toList
    {-# INLINE assocs #-}

    -- | /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
    keysSet :: forall k a. NEMap k a -> NESet k
    keysSet (NEMap k
    k a
    _ Map k a
    m) = k -> Set k -> NESet k
    forall a. a -> Set a -> NESet a
    NESet k
    k (Map k a -> Set k
    forall k a. Map k a -> Set k
    M.keysSet Map k a
    m)
    {-# INLINE keysSet #-}

    -- | /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
    mapWithKey :: forall k a b. (k -> a -> b) -> NEMap k a -> NEMap k b
    mapWithKey k -> a -> b
    f (NEMap k
    k a
    v Map k a
    m) = k -> b -> Map k b -> NEMap k b
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k (k -> a -> b
    f k
    k a
    v) ((k -> a -> b) -> Map k a -> Map k b
    forall k a b. (k -> a -> b) -> Map k a -> Map k b
    M.mapWithKey k -> a -> b
    f Map k a
    m)
    {-# NOINLINE [1] mapWithKey #-}

    {-# RULES
    "mapWithKey/mapWithKey" forall f g xs.
      mapWithKey f (mapWithKey g xs) =
        mapWithKey (\k a -> f k (g k a)) xs
    "mapWithKey/map" forall f g xs.
      mapWithKey f (map g xs) =
        mapWithKey (\k a -> f k (g a)) xs
    "map/mapWithKey" forall f g xs.
      map f (mapWithKey g xs) =
        mapWithKey (\k a -> f (g k a)) xs
      #-}

    -- | /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)
    toAscList :: forall k a. NEMap k a -> NonEmpty (k, a)
    toAscList = NEMap k a -> NonEmpty (k, a)
    forall k a. NEMap k a -> NonEmpty (k, a)
    toList
    {-# INLINE toAscList #-}

    -- | /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)
    toDescList :: forall k a. NEMap k a -> NonEmpty (k, a)
    toDescList (NEMap k
    k0 a
    v0 Map k a
    m) = (NonEmpty (k, a) -> k -> a -> NonEmpty (k, a))
    -> NonEmpty (k, a) -> Map k a -> NonEmpty (k, a)
    forall a k b. (a -> k -> b -> a) -> a -> Map k b -> a
    M.foldlWithKey' NonEmpty (k, a) -> k -> a -> NonEmpty (k, a)
    forall {a} {b}. NonEmpty (a, b) -> a -> b -> NonEmpty (a, b)
    go ((k
    k0, a
    v0) (k, a) -> [(k, a)] -> NonEmpty (k, a)
    forall a. a -> [a] -> NonEmpty a
    :| []) Map k a
    m
      where
        go :: NonEmpty (a, b) -> a -> b -> NonEmpty (a, b)
    go NonEmpty (a, b)
    xs a
    k b
    v = (a
    k, b
    v) (a, b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    forall a. a -> NonEmpty a -> NonEmpty a
    NE.<| NonEmpty (a, b)
    xs
    {-# INLINE toDescList #-}

    -- | /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
    insertMap :: forall k a. Ord k => k -> a -> Map k a -> NEMap k a
    insertMap k
    k a
    v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
    forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
    withNonEmpty (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v) (k -> a -> NEMap k a -> NEMap k a
    forall k a. Ord k => k -> a -> NEMap k a -> NEMap k a
    insert k
    k a
    v)
    {-# INLINE insertMap #-}

    -- | /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
    insertMapWith :: forall k a.
    Ord k =>
    (a -> a -> a) -> k -> a -> Map k a -> NEMap k a
    insertMapWith a -> a -> a
    f k
    k a
    v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
    forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
    withNonEmpty (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v) ((a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
    forall k a.
    Ord k =>
    (a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
    insertWith a -> a -> a
    f k
    k a
    v)
    {-# INLINE insertMapWith #-}

    -- | /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
    insertMapWithKey :: forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> Map k a -> NEMap k a
    insertMapWithKey k -> a -> a -> a
    f k
    k a
    v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
    forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
    withNonEmpty (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v) ((k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
    insertWithKey k -> a -> a -> a
    f k
    k a
    v)
    {-# INLINE insertMapWithKey #-}

    -- | /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
    insertMapMin :: forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin = k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap
    {-# INLINE insertMapMin #-}

    -- | /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
    insertMapMax :: forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMax k
    k a
    v = NEMap k a -> (NEMap k a -> NEMap k a) -> Map k a -> NEMap k a
    forall r k a. r -> (NEMap k a -> r) -> Map k a -> r
    withNonEmpty (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v) NEMap k a -> NEMap k a
    go
      where
        go :: NEMap k a -> NEMap k a
    go (NEMap k
    k0 a
    v0 Map k a
    m0) = k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v0 (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMaxMap k
    k a
    v (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m0
    {-# INLINE insertMapMax #-}

    -- | /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
    insert :: forall k a. Ord k => k -> a -> NEMap k a -> NEMap k a
    insert k
    k a
    v n :: NEMap k a
    n@(NEMap k
    k0 a
    v0 Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k a
    v (Map k a -> NEMap k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    n
      Ordering
    EQ -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k a
    v Map k a
    m
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v0 (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> a -> Map k a -> Map k a
    forall k a. Ord k => k -> a -> Map k a -> Map k a
    M.insert k
    k a
    v (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE insert #-}

    -- | /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
    insertWithKey :: forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
    insertWithKey k -> a -> a -> a
    f k
    k a
    v n :: NEMap k a
    n@(NEMap k
    k0 a
    v0 Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k a
    v (Map k a -> NEMap k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    n
      Ordering
    EQ -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k (k -> a -> a -> a
    f k
    k a
    v a
    v0) Map k a
    m
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v0 (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> Map k a -> Map k a
    M.insertWithKey k -> a -> a -> a
    f k
    k a
    v Map k a
    m
    {-# INLINE insertWithKey #-}

    -- | /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)
    insertLookupWithKey :: forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> NEMap k a -> (Maybe a, NEMap k a)
    insertLookupWithKey k -> a -> a -> a
    f k
    k a
    v n :: NEMap k a
    n@(NEMap k
    k0 a
    v0 Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> (Maybe a
    forall a. Maybe a
    Nothing, k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k a
    v (Map k a -> NEMap k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    n)
      Ordering
    EQ -> (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v, k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k (k -> a -> a -> a
    f k
    k a
    v a
    v0) Map k a
    m)
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v0 (Map k a -> NEMap k a)
    -> (Maybe a, Map k a) -> (Maybe a, NEMap k a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> Map k a -> (Maybe a, Map k a)
    M.insertLookupWithKey k -> a -> a -> a
    f k
    k a
    v Map k a
    m
    {-# INLINE insertLookupWithKey #-}

    -- | /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
    fromListWith :: forall k a. Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromListWith a -> a -> a
    f = (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromListWithKey ((a -> a -> a) -> k -> a -> a -> a
    forall a b. a -> b -> a
    const a -> a -> a
    f)
    {-# INLINE fromListWith #-}

    -- | /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
    fromListWithKey :: forall k a.
    Ord k =>
    (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromListWithKey k -> a -> a -> a
    f ((k
    k0, a
    v0) :| [(k, a)]
    xs) = (NEMap k a -> (k, a) -> NEMap k a)
    -> NEMap k a -> [(k, a)] -> NEMap k a
    forall b a. (b -> a -> b) -> b -> [a] -> b
    forall (t :: * -> *) b a.
    Foldable t =>
    (b -> a -> b) -> b -> t a -> b
    F.foldl' NEMap k a -> (k, a) -> NEMap k a
    go (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k0 a
    v0) [(k, a)]
    xs
      where
        go :: NEMap k a -> (k, a) -> NEMap k a
    go NEMap k a
    m (k
    k, a
    v) = (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
    forall k a.
    Ord k =>
    (k -> a -> a -> a) -> k -> a -> NEMap k a -> NEMap k a
    insertWithKey k -> a -> a -> a
    f k
    k a
    v NEMap k a
    m
        {-# INLINE go #-}
    {-# INLINE fromListWithKey #-}

    -- | /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
    fromAscList :: forall k a. Eq k => NonEmpty (k, a) -> NEMap k a
    fromAscList = NonEmpty (k, a) -> NEMap k a
    forall k a. NonEmpty (k, a) -> NEMap k a
    fromDistinctAscList (NonEmpty (k, a) -> NEMap k a)
    -> (NonEmpty (k, a) -> NonEmpty (k, a))
    -> NonEmpty (k, a)
    -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NonEmpty (k, a) -> NonEmpty (k, a)
    forall a b. Eq a => NonEmpty (a, b) -> NonEmpty (a, b)
    combineEq
    {-# INLINE fromAscList #-}

    -- | /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
    fromAscListWith :: forall k a. Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromAscListWith a -> a -> a
    f = (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    forall k a.
    Eq k =>
    (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromAscListWithKey ((a -> a -> a) -> k -> a -> a -> a
    forall a b. a -> b -> a
    const a -> a -> a
    f)
    {-# INLINE fromAscListWith #-}

    -- | /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
    fromAscListWithKey :: forall k a.
    Eq k =>
    (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromAscListWithKey k -> a -> a -> a
    f = NonEmpty (k, a) -> NEMap k a
    forall k a. NonEmpty (k, a) -> NEMap k a
    fromDistinctAscList (NonEmpty (k, a) -> NEMap k a)
    -> (NonEmpty (k, a) -> NonEmpty (k, a))
    -> NonEmpty (k, a)
    -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> a -> a) -> NonEmpty (k, a) -> NonEmpty (k, a)
    forall a b.
    Eq a =>
    (a -> b -> b -> b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    combineEqWith k -> a -> a -> a
    f
    {-# INLINE fromAscListWithKey #-}

    -- | /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
    fromDistinctAscList :: forall k a. NonEmpty (k, a) -> NEMap k a
    fromDistinctAscList ((k
    k, a
    v) :| [(k, a)]
    xs) =
      k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k a
    v
        (Map k a -> NEMap k a)
    -> ([(k, a)] -> Map k a) -> [(k, a)] -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(k, a)] -> Map k a
    forall k a. [(k, a)] -> Map k a
    M.fromDistinctAscList
        ([(k, a)] -> NEMap k a) -> [(k, a)] -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ [(k, a)]
    xs
    {-# INLINE fromDistinctAscList #-}

    -- | /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
    fromDescList :: forall k a. Eq k => NonEmpty (k, a) -> NEMap k a
    fromDescList = NonEmpty (k, a) -> NEMap k a
    forall k a. NonEmpty (k, a) -> NEMap k a
    fromDistinctDescList (NonEmpty (k, a) -> NEMap k a)
    -> (NonEmpty (k, a) -> NonEmpty (k, a))
    -> NonEmpty (k, a)
    -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NonEmpty (k, a) -> NonEmpty (k, a)
    forall a b. Eq a => NonEmpty (a, b) -> NonEmpty (a, b)
    combineEq
    {-# INLINE fromDescList #-}

    -- | /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
    fromDescListWith :: forall k a. Eq k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromDescListWith a -> a -> a
    f = (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    forall k a.
    Eq k =>
    (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromDescListWithKey ((a -> a -> a) -> k -> a -> a -> a
    forall a b. a -> b -> a
    const a -> a -> a
    f)
    {-# INLINE fromDescListWith #-}

    -- | /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
    fromDescListWithKey :: forall k a.
    Eq k =>
    (k -> a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromDescListWithKey k -> a -> a -> a
    f = NonEmpty (k, a) -> NEMap k a
    forall k a. NonEmpty (k, a) -> NEMap k a
    fromDistinctDescList (NonEmpty (k, a) -> NEMap k a)
    -> (NonEmpty (k, a) -> NonEmpty (k, a))
    -> NonEmpty (k, a)
    -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> a -> a) -> NonEmpty (k, a) -> NonEmpty (k, a)
    forall a b.
    Eq a =>
    (a -> b -> b -> b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    combineEqWith k -> a -> a -> a
    f
    {-# INLINE fromDescListWithKey #-}

    -- | /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
    --
    -- @since 0.5.8
    fromDistinctDescList :: NonEmpty (k, a) -> NEMap k a
    fromDistinctDescList :: forall k a. NonEmpty (k, a) -> NEMap k a
    fromDistinctDescList ((k
    k, a
    v) :| [(k, a)]
    xs) =
      k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMax k
    k a
    v
        (Map k a -> NEMap k a)
    -> ([(k, a)] -> Map k a) -> [(k, a)] -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . [(k, a)] -> Map k a
    forall k a. [(k, a)] -> Map k a
    M.fromDistinctDescList
        ([(k, a)] -> NEMap k a) -> [(k, a)] -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ [(k, a)]
    xs
    {-# INLINE fromDistinctDescList #-}

    -- | /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
    delete :: forall k a. Ord k => k -> NEMap k a -> Map k a
    delete k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n
      Ordering
    EQ -> Map k a
    m
      Ordering
    GT -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0 a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> Map k a -> Map k a
    forall k a. Ord k => k -> Map k a -> Map k a
    M.delete k
    k (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE delete #-}

    -- | /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
    adjust :: forall k a. Ord k => (a -> a) -> k -> NEMap k a -> NEMap k a
    adjust a -> a
    f = (k -> a -> a) -> k -> NEMap k a -> NEMap k a
    forall k a. Ord k => (k -> a -> a) -> k -> NEMap k a -> NEMap k a
    adjustWithKey ((a -> a) -> k -> a -> a
    forall a b. a -> b -> a
    const a -> a
    f)
    {-# INLINE adjust #-}

    -- | /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
    adjustWithKey :: forall k a. Ord k => (k -> a -> a) -> k -> NEMap k a -> NEMap k a
    adjustWithKey k -> a -> a
    f k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> NEMap k a
    n
      Ordering
    EQ -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 (k -> a -> a
    f k
    k0 a
    v) Map k a
    m
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> a) -> k -> Map k a -> Map k a
    forall k a. Ord k => (k -> a -> a) -> k -> Map k a -> Map k a
    M.adjustWithKey k -> a -> a
    f k
    k (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE adjustWithKey #-}

    -- | /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
    update :: forall k a. Ord k => (a -> Maybe a) -> k -> NEMap k a -> Map k a
    update a -> Maybe a
    f = (k -> a -> Maybe a) -> k -> NEMap k a -> Map k a
    forall k a.
    Ord k =>
    (k -> a -> Maybe a) -> k -> NEMap k a -> Map k a
    updateWithKey ((a -> Maybe a) -> k -> a -> Maybe a
    forall a b. a -> b -> a
    const a -> Maybe a
    f)
    {-# INLINE update #-}

    -- | /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
    updateWithKey :: forall k a.
    Ord k =>
    (k -> a -> Maybe a) -> k -> NEMap k a -> Map k a
    updateWithKey k -> a -> Maybe a
    f k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n
      Ordering
    EQ -> Map k a -> (a -> Map k a) -> Maybe a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a
    m ((a -> Map k a -> Map k a) -> Map k a -> a -> Map k a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0) Map k a
    m) (Maybe a -> Map k a) -> (a -> Maybe a) -> a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> a -> Maybe a
    f k
    k0 (a -> Map k a) -> a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ a
    v
      Ordering
    GT -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0 a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> Maybe a) -> k -> Map k a -> Map k a
    forall k a. Ord k => (k -> a -> Maybe a) -> k -> Map k a -> Map k a
    M.updateWithKey k -> a -> Maybe a
    f k
    k (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE updateWithKey #-}

    -- | /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)
    updateLookupWithKey :: forall k a.
    Ord k =>
    (k -> a -> Maybe a) -> k -> NEMap k a -> (Maybe a, Map k a)
    updateLookupWithKey k -> a -> Maybe a
    f k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> (Maybe a
    forall a. Maybe a
    Nothing, NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n)
      Ordering
    EQ ->
        let u :: Maybe a
    u = k -> a -> Maybe a
    f k
    k0 a
    v
         in (Maybe a
    u Maybe a -> Maybe a -> Maybe a
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v, Map k a -> (a -> Map k a) -> Maybe a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a
    m ((a -> Map k a -> Map k a) -> Map k a -> a -> Map k a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0) Map k a
    m) Maybe a
    u)
      Ordering
    GT -> (Map k a -> Map k a) -> (Maybe a, Map k a) -> (Maybe a, Map k a)
    forall a b. (a -> b) -> (Maybe a, a) -> (Maybe a, b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0 a
    v) ((Maybe a, Map k a) -> (Maybe a, Map k a))
    -> (Map k a -> (Maybe a, Map k a)) -> Map k a -> (Maybe a, Map k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
    forall k a.
    Ord k =>
    (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)
    M.updateLookupWithKey k -> a -> Maybe a
    f k
    k (Map k a -> (Maybe a, Map k a)) -> Map k a -> (Maybe a, Map k a)
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE updateLookupWithKey #-}

    -- | /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
    alter :: forall k a.
    Ord k =>
    (Maybe a -> Maybe a) -> k -> NEMap k a -> Map k a
    alter Maybe a -> Maybe a
    f k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> (Map k a -> Map k a)
    -> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a -> Map k a
    forall a. a -> a
    id (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k) (Maybe a -> Maybe a
    f Maybe a
    forall a. Maybe a
    Nothing) (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n)
      Ordering
    EQ -> (Map k a -> Map k a)
    -> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a -> Map k a
    forall a. a -> a
    id (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0) (Maybe a -> Maybe a
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)) Map k a
    m
      Ordering
    GT -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0 a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    forall k a.
    Ord k =>
    (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    M.alter Maybe a -> Maybe a
    f k
    k (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE alter #-}

    -- | /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 'Control.Lens.At.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)
    alterF :: forall k (f :: * -> *) a.
    (Ord k, Functor f) =>
    (Maybe a -> f (Maybe a)) -> k -> NEMap k a -> f (Map k a)
    alterF Maybe a -> f (Maybe a)
    f k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> (Maybe a -> Map k a -> Map k a) -> Map k a -> Maybe a -> Map k a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip ((Map k a -> Map k a)
    -> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a -> Map k a
    forall a. a -> a
    id (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k)) (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n) (Maybe a -> Map k a) -> f (Maybe a) -> f (Map k a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f (Maybe a)
    f Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> (Maybe a -> Map k a -> Map k a) -> Map k a -> Maybe a -> Map k a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip ((Map k a -> Map k a)
    -> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a -> Map k a
    forall a. a -> a
    id (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0)) Map k a
    m (Maybe a -> Map k a) -> f (Maybe a) -> f (Map k a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f (Maybe a)
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)
      Ordering
    GT -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0 a
    v (Map k a -> Map k a) -> f (Map k a) -> f (Map k a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
    forall (f :: * -> *) k a.
    (Functor f, Ord k) =>
    (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
    M.alterF Maybe a -> f (Maybe a)
    f k
    k Map k a
    m
    {-# INLINEABLE [2] alterF #-}

    -- if f ~ Const b, it's a lookup
    {-# RULES
    "alterF/Const" forall k (f :: Maybe a -> Const b (Maybe a)).
      alterF f k =
        Const . getConst . f . lookup k
      #-}

    -- if f ~ Identity, it's an 'alter'
    {-# RULES
    "alterF/Identity" forall k (f :: Maybe a -> Identity (Maybe a)).
      alterF f k =
        Identity . alter (runIdentity . f) k
      #-}

    -- | /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
    alter' :: forall k a. Ord k => (Maybe a -> a) -> k -> NEMap k a -> NEMap k a
    alter' Maybe a -> a
    f k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k (Maybe a -> a
    f Maybe a
    forall a. Maybe a
    Nothing) (Map k a -> NEMap k a)
    -> (NEMap k a -> Map k a) -> NEMap k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap (NEMap k a -> NEMap k a) -> NEMap k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    n
      Ordering
    EQ -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 (Maybe a -> a
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)) Map k a
    m
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    forall k a.
    Ord k =>
    (Maybe a -> Maybe a) -> k -> Map k a -> Map k a
    M.alter (a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> (Maybe a -> a) -> Maybe a -> Maybe a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Maybe a -> a
    f) k
    k (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE alter' #-}

    -- | /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 'Control.Lens.At.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)
    alterF' :: forall k (f :: * -> *) a.
    (Ord k, Functor f) =>
    (Maybe a -> f a) -> k -> NEMap k a -> f (NEMap k a)
    alterF' Maybe a -> f a
    f k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> (a -> Map k a -> NEMap k a) -> Map k a -> a -> NEMap k a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k) (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n) (a -> NEMap k a) -> f a -> f (NEMap k a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f a
    f Maybe a
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> (a -> Map k a -> NEMap k a) -> Map k a -> a -> NEMap k a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0) Map k a
    m (a -> NEMap k a) -> f a -> f (NEMap k a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Maybe a -> f a
    f (a -> Maybe a
    forall a. a -> Maybe a
    Just a
    v)
      Ordering
    GT -> k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v (Map k a -> NEMap k a) -> f (Map k a) -> f (NEMap k a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
    forall (f :: * -> *) k a.
    (Functor f, Ord k) =>
    (Maybe a -> f (Maybe a)) -> k -> Map k a -> f (Map k a)
    M.alterF ((a -> Maybe a) -> f a -> f (Maybe a)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Maybe a
    forall a. a -> Maybe a
    Just (f a -> f (Maybe a)) -> (Maybe a -> f a) -> Maybe a -> f (Maybe a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Maybe a -> f a
    f) k
    k Map k a
    m
    {-# INLINEABLE [2] alterF' #-}

    -- if f ~ Const b, it's a lookup
    {-# RULES
    "alterF'/Const" forall k (f :: Maybe a -> Const b a).
      alterF' f k =
        Const . getConst . f . lookup k
      #-}

    -- if f ~ Identity, it's an insertWith
    {-# RULES
    "alterF'/Identity" forall k (f :: Maybe a -> Identity a).
      alterF' f k =
        Identity . insertWith (\_ -> runIdentity . f . Just) k (runIdentity (f Nothing))
      #-}

    -- | /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)
    traverseMaybeWithKey :: forall (t :: * -> *) k a b.
    Applicative t =>
    (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b)
    traverseMaybeWithKey k -> a -> t (Maybe b)
    f (NEMap k
    k0 a
    v Map k a
    m0) =
      Maybe b -> Map k b -> Map k b
    forall {a}. Maybe a -> Map k a -> Map k a
    combine (Maybe b -> Map k b -> Map k b)
    -> t (Maybe b) -> t (Map k b -> Map k b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> k -> a -> t (Maybe b)
    f k
    k0 a
    v t (Map k b -> Map k b) -> t (Map k b) -> t (Map k b)
    forall a b. t (a -> b) -> t a -> t b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (k -> a -> t (Maybe b)) -> Map k a -> t (Map k b)
    forall (f :: * -> *) k a b.
    Applicative f =>
    (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
    M.traverseMaybeWithKey k -> a -> t (Maybe b)
    f Map k a
    m0
      where
        combine :: Maybe a -> Map k a -> Map k a
    combine Maybe a
    Nothing = Map k a -> Map k a
    forall a. a -> a
    id
        combine (Just a
    v') = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0 a
    v'
    {-# INLINE traverseMaybeWithKey #-}

    -- | /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'.

    -- TODO: benchmark against M.maxView version
    traverseMaybeWithKey1 ::
      Apply t =>
      (k -> a -> t (Maybe b)) ->
      NEMap k a ->
      t (Map k b)
    traverseMaybeWithKey1 :: forall (t :: * -> *) k a b.
    Apply t =>
    (k -> a -> t (Maybe b)) -> NEMap k a -> t (Map k b)
    traverseMaybeWithKey1 k -> a -> t (Maybe b)
    f (NEMap k
    k0 a
    v Map k a
    m0) = case MaybeApply t (Map k b) -> Either (t (Map k b)) (Map k b)
    forall (f :: * -> *) a. MaybeApply f a -> Either (f a) a
    runMaybeApply MaybeApply t (Map k b)
    m1 of
      Left t (Map k b)
    m2 -> Maybe b -> Map k b -> Map k b
    forall {a}. Maybe a -> Map k a -> Map k a
    combine (Maybe b -> Map k b -> Map k b)
    -> t (Maybe b) -> t (Map k b -> Map k b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> k -> a -> t (Maybe b)
    f k
    k0 a
    v t (Map k b -> Map k b) -> t (Map k b) -> t (Map k b)
    forall a b. t (a -> b) -> t a -> t b
    forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
    <.> t (Map k b)
    m2
      Right Map k b
    m2 -> (Maybe b -> Map k b -> Map k b
    forall {a}. Maybe a -> Map k a -> Map k a
    `combine` Map k b
    m2) (Maybe b -> Map k b) -> t (Maybe b) -> t (Map k b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> k -> a -> t (Maybe b)
    f k
    k0 a
    v
      where
        m1 :: MaybeApply t (Map k b)
    m1 = (k -> a -> MaybeApply t (Maybe b))
    -> Map k a -> MaybeApply t (Map k b)
    forall (f :: * -> *) k a b.
    Applicative f =>
    (k -> a -> f (Maybe b)) -> Map k a -> f (Map k b)
    M.traverseMaybeWithKey (\k
    k -> Either (t (Maybe b)) (Maybe b) -> MaybeApply t (Maybe b)
    forall (f :: * -> *) a. Either (f a) a -> MaybeApply f a
    MaybeApply (Either (t (Maybe b)) (Maybe b) -> MaybeApply t (Maybe b))
    -> (a -> Either (t (Maybe b)) (Maybe b))
    -> a
    -> MaybeApply t (Maybe b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . t (Maybe b) -> Either (t (Maybe b)) (Maybe b)
    forall a b. a -> Either a b
    Left (t (Maybe b) -> Either (t (Maybe b)) (Maybe b))
    -> (a -> t (Maybe b)) -> a -> Either (t (Maybe b)) (Maybe b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> a -> t (Maybe b)
    f k
    k) Map k a
    m0
        combine :: Maybe a -> Map k a -> Map k a
    combine Maybe a
    Nothing = Map k a -> Map k a
    forall a. a -> a
    id
        combine (Just a
    v') = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k0 a
    v'
    {-# INLINE traverseMaybeWithKey1 #-}

    -- | /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)
    mapAccum :: forall a b c k.
    (a -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
    mapAccum a -> b -> (a, c)
    f = (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
    forall a k b c.
    (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
    mapAccumWithKey (\a
    x k
    _ -> a -> b -> (a, c)
    f a
    x)
    {-# INLINE mapAccum #-}

    -- | /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)
    mapAccumWithKey :: forall a k b c.
    (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
    mapAccumWithKey a -> k -> b -> (a, c)
    f a
    z0 (NEMap k
    k b
    v Map k b
    m) = (a
    z2, k -> c -> Map k c -> NEMap k c
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k c
    v' Map k c
    m')
      where
        ~(a
    z1, c
    v') = a -> k -> b -> (a, c)
    f a
    z0 k
    k b
    v
        ~(a
    z2, Map k c
    m') = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
    forall a k b c.
    (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
    M.mapAccumWithKey a -> k -> b -> (a, c)
    f a
    z1 Map k b
    m
    {-# INLINE mapAccumWithKey #-}

    -- | /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)
    mapAccumRWithKey :: forall a k b c.
    (a -> k -> b -> (a, c)) -> a -> NEMap k b -> (a, NEMap k c)
    mapAccumRWithKey a -> k -> b -> (a, c)
    f a
    z0 (NEMap k
    k b
    v Map k b
    m) = (a
    z2, k -> c -> Map k c -> NEMap k c
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k c
    v' Map k c
    m')
      where
        ~(a
    z1, Map k c
    m') = (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
    forall a k b c.
    (a -> k -> b -> (a, c)) -> a -> Map k b -> (a, Map k c)
    M.mapAccumRWithKey a -> k -> b -> (a, c)
    f a
    z0 Map k b
    m
        ~(a
    z2, c
    v') = a -> k -> b -> (a, c)
    f a
    z1 k
    k b
    v
    {-# INLINE mapAccumRWithKey #-}

    -- TODO: what other situations can we take advantage of lazy tuple pattern
    -- matching?

    -- | /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
    mapKeys :: forall k2 k1 a. Ord k2 => (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
    mapKeys k1 -> k2
    f (NEMap k1
    k0 a
    v0 Map k1 a
    m) =
      (a -> a -> a) -> NonEmpty (k2, a) -> NEMap k2 a
    forall k a. Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromListWith a -> a -> a
    forall a b. a -> b -> a
    const
        (NonEmpty (k2, a) -> NEMap k2 a)
    -> (Map k1 a -> NonEmpty (k2, a)) -> Map k1 a -> NEMap k2 a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((k1 -> k2
    f k1
    k0, a
    v0) (k2, a) -> [(k2, a)] -> NonEmpty (k2, a)
    forall a. a -> [a] -> NonEmpty a
    :|)
        ([(k2, a)] -> NonEmpty (k2, a))
    -> (Map k1 a -> [(k2, a)]) -> Map k1 a -> NonEmpty (k2, a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k1 -> a -> [(k2, a)] -> [(k2, a)])
    -> [(k2, a)] -> Map k1 a -> [(k2, a)]
    forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
    M.foldrWithKey (\k1
    k a
    v [(k2, a)]
    kvs -> (k1 -> k2
    f k1
    k, a
    v) (k2, a) -> [(k2, a)] -> [(k2, a)]
    forall a. a -> [a] -> [a]
    : [(k2, a)]
    kvs) []
        (Map k1 a -> NEMap k2 a) -> Map k1 a -> NEMap k2 a
    forall a b. (a -> b) -> a -> b
    $ Map k1 a
    m
    {-# INLINEABLE mapKeys #-}

    -- | /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
    mapKeysWith :: forall k2 a k1.
    Ord k2 =>
    (a -> a -> a) -> (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
    mapKeysWith a -> a -> a
    c k1 -> k2
    f (NEMap k1
    k0 a
    v0 Map k1 a
    m) =
      (a -> a -> a) -> NonEmpty (k2, a) -> NEMap k2 a
    forall k a. Ord k => (a -> a -> a) -> NonEmpty (k, a) -> NEMap k a
    fromListWith a -> a -> a
    c
        (NonEmpty (k2, a) -> NEMap k2 a)
    -> (Map k1 a -> NonEmpty (k2, a)) -> Map k1 a -> NEMap k2 a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . ((k1 -> k2
    f k1
    k0, a
    v0) (k2, a) -> [(k2, a)] -> NonEmpty (k2, a)
    forall a. a -> [a] -> NonEmpty a
    :|)
        ([(k2, a)] -> NonEmpty (k2, a))
    -> (Map k1 a -> [(k2, a)]) -> Map k1 a -> NonEmpty (k2, a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k1 -> a -> [(k2, a)] -> [(k2, a)])
    -> [(k2, a)] -> Map k1 a -> [(k2, a)]
    forall k a b. (k -> a -> b -> b) -> b -> Map k a -> b
    M.foldrWithKey (\k1
    k a
    v [(k2, a)]
    kvs -> (k1 -> k2
    f k1
    k, a
    v) (k2, a) -> [(k2, a)] -> [(k2, a)]
    forall a. a -> [a] -> [a]
    : [(k2, a)]
    kvs) []
        (Map k1 a -> NEMap k2 a) -> Map k1 a -> NEMap k2 a
    forall a b. (a -> b) -> a -> b
    $ Map k1 a
    m
    {-# INLINEABLE mapKeysWith #-}

    -- | /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
    mapKeysMonotonic :: forall k1 k2 a. (k1 -> k2) -> NEMap k1 a -> NEMap k2 a
    mapKeysMonotonic k1 -> k2
    f (NEMap k1
    k a
    v Map k1 a
    m) =
      k2 -> a -> Map k2 a -> NEMap k2 a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap (k1 -> k2
    f k1
    k) a
    v
        (Map k2 a -> NEMap k2 a)
    -> (Map k1 a -> Map k2 a) -> Map k1 a -> NEMap k2 a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k1 -> k2) -> Map k1 a -> Map k2 a
    forall k1 k2 a. (k1 -> k2) -> Map k1 a -> Map k2 a
    M.mapKeysMonotonic k1 -> k2
    f
        (Map k1 a -> NEMap k2 a) -> Map k1 a -> NEMap k2 a
    forall a b. (a -> b) -> a -> b
    $ Map k1 a
    m
    {-# INLINE mapKeysMonotonic #-}

    -- | /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
    filter :: forall a k. (a -> Bool) -> NEMap k a -> Map k a
    filter a -> Bool
    f (NEMap k
    k a
    v Map k a
    m)
      | a -> Bool
    f a
    v = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> Bool) -> Map k a -> Map k a
    forall a k. (a -> Bool) -> Map k a -> Map k a
    M.filter a -> Bool
    f (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
      | Bool
    otherwise = (a -> Bool) -> Map k a -> Map k a
    forall a k. (a -> Bool) -> Map k a -> Map k a
    M.filter a -> Bool
    f Map k a
    m
    {-# INLINE filter #-}

    -- | /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
    filterWithKey :: forall k a. (k -> a -> Bool) -> NEMap k a -> Map k a
    filterWithKey k -> a -> Bool
    f (NEMap k
    k a
    v Map k a
    m)
      | k -> a -> Bool
    f k
    k a
    v = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> Bool) -> Map k a -> Map k a
    forall k a. (k -> a -> Bool) -> Map k a -> Map k a
    M.filterWithKey k -> a -> Bool
    f (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
      | Bool
    otherwise = (k -> a -> Bool) -> Map k a -> Map k a
    forall k a. (k -> a -> Bool) -> Map k a -> Map k a
    M.filterWithKey k -> a -> Bool
    f Map k a
    m
    {-# INLINE filterWithKey #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Restrict an 'NEMap' to only those keys
    -- found in a 'Data.Set.Set'.
    --
    -- @
    -- m \`restrictKeys\` s = 'filterWithKey' (\k _ -> k ``Set.member`` s) m
    -- m \`restrictKeys\` s = m ``intersection`` 'fromSet' (const ()) s
    -- @
    restrictKeys ::
      Ord k =>
      NEMap k a ->
      Set k ->
      Map k a
    restrictKeys :: forall k a. Ord k => NEMap k a -> Set k -> Map k a
    restrictKeys n :: NEMap k a
    n@(NEMap k
    k a
    v Map k a
    m) Set k
    xs = case Set k -> Maybe (k, Set k)
    forall a. Set a -> Maybe (a, Set a)
    S.minView Set k
    xs of
      Maybe (k, Set k)
    Nothing -> Map k a
    forall k a. Map k a
    M.empty
      Just (k
    y, Set k
    ys) -> case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    y of
        -- k is not in xs
        Ordering
    LT -> Map k a
    m Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    `M.restrictKeys` Set k
    xs
        -- k and y are a part of the result
        Ordering
    EQ -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    `M.restrictKeys` Set k
    ys
        -- y is not in m
        Ordering
    GT -> NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    `M.restrictKeys` Set k
    ys
    {-# INLINE restrictKeys #-}

    -- | /O(m*log(n\/m + 1)), m <= n/. Remove all keys in a 'Data.Set.Set' from
    -- an 'NEMap'.
    --
    -- @
    -- m \`withoutKeys\` s = 'filterWithKey' (\k _ -> k ``Set.notMember`` s) m
    -- m \`withoutKeys\` s = m ``difference`` 'fromSet' (const ()) s
    -- @
    withoutKeys ::
      Ord k =>
      NEMap k a ->
      Set k ->
      Map k a
    withoutKeys :: forall k a. Ord k => NEMap k a -> Set k -> Map k a
    withoutKeys n :: NEMap k a
    n@(NEMap k
    k a
    v Map k a
    m) Set k
    xs = case Set k -> Maybe (k, Set k)
    forall a. Set a -> Maybe (a, Set a)
    S.minView Set k
    xs of
      Maybe (k, Set k)
    Nothing -> NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n
      Just (k
    y, Set k
    ys) -> case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    y of
        -- k is not in xs, so cannot be deleted
        Ordering
    LT -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    `M.withoutKeys` Set k
    xs
        -- y deletes k, and only k
        Ordering
    EQ -> Map k a
    m Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    `M.withoutKeys` Set k
    ys
        -- y is not in n, so cannot delete anything, so we can just difference n and ys
        Ordering
    GT -> NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n Map k a -> Set k -> Map k a
    forall k a. Ord k => Map k a -> Set k -> Map k a
    `M.withoutKeys` Set k
    ys
    {-# INLINE withoutKeys #-}

    -- | /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)
    partition :: forall a k.
    (a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    partition a -> Bool
    f = (k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall k a.
    (k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    partitionWithKey ((a -> Bool) -> k -> a -> Bool
    forall a b. a -> b -> a
    const a -> Bool
    f)
    {-# INLINE partition #-}

    -- | /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)
    partitionWithKey :: forall k a.
    (k -> a -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    partitionWithKey k -> a -> Bool
    f n :: NEMap k a
    n@(NEMap k
    k a
    v Map k a
    m0) = case (Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m1, Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m2) of
      (Maybe (NEMap k a)
    Nothing, Maybe (NEMap k a)
    Nothing)
        | k -> a -> Bool
    f k
    k a
    v -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This NEMap k a
    n
        | Bool
    otherwise -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That NEMap k a
    n
      (Just NEMap k a
    n1, Maybe (NEMap k a)
    Nothing)
        | k -> a -> Bool
    f k
    k a
    v -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This NEMap k a
    n
        | Bool
    otherwise -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These NEMap k a
    n1 (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v)
      (Maybe (NEMap k a)
    Nothing, Just NEMap k a
    n2)
        | k -> a -> Bool
    f k
    k a
    v -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v) NEMap k a
    n2
        | Bool
    otherwise -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That NEMap k a
    n
      (Just NEMap k a
    n1, Just NEMap k a
    n2)
        | k -> a -> Bool
    f k
    k a
    v -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k a
    v Map k a
    m1) NEMap k a
    n2
        | Bool
    otherwise -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These NEMap k a
    n1 (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k a
    v Map k a
    m2)
      where
        (Map k a
    m1, Map k a
    m2) = (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
    forall k a. (k -> a -> Bool) -> Map k a -> (Map k a, Map k a)
    M.partitionWithKey k -> a -> Bool
    f Map k a
    m0
    {-# INLINEABLE partitionWithKey #-}

    -- | /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
    takeWhileAntitone :: forall k a. (k -> Bool) -> NEMap k a -> Map k a
    takeWhileAntitone k -> Bool
    f (NEMap k
    k a
    v Map k a
    m)
      | k -> Bool
    f k
    k = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> Bool) -> Map k a -> Map k a
    forall k a. (k -> Bool) -> Map k a -> Map k a
    M.takeWhileAntitone k -> Bool
    f (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
      | Bool
    otherwise = Map k a
    forall k a. Map k a
    M.empty
    {-# INLINE takeWhileAntitone #-}

    -- | /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
    dropWhileAntitone :: forall k a. (k -> Bool) -> NEMap k a -> Map k a
    dropWhileAntitone k -> Bool
    f n :: NEMap k a
    n@(NEMap k
    k a
    _ Map k a
    m)
      | k -> Bool
    f k
    k = (k -> Bool) -> Map k a -> Map k a
    forall k a. (k -> Bool) -> Map k a -> Map k a
    M.dropWhileAntitone k -> Bool
    f Map k a
    m
      | Bool
    otherwise = NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n
    {-# INLINE dropWhileAntitone #-}

    -- | /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)
    spanAntitone :: forall k a.
    (k -> Bool) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    spanAntitone k -> Bool
    f n :: NEMap k a
    n@(NEMap k
    k a
    v Map k a
    m0)
      | k -> Bool
    f k
    k = case (Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m1, Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m2) of
          (Maybe (NEMap k a)
    Nothing, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This NEMap k a
    n
          (Just NEMap k a
    _, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This NEMap k a
    n
          (Maybe (NEMap k a)
    Nothing, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v) NEMap k a
    n2
          (Just NEMap k a
    _, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k a
    v Map k a
    m1) NEMap k a
    n2
      | Bool
    otherwise = NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That NEMap k a
    n
      where
        (Map k a
    m1, Map k a
    m2) = (k -> Bool) -> Map k a -> (Map k a, Map k a)
    forall k a. (k -> Bool) -> Map k a -> (Map k a, Map k a)
    M.spanAntitone k -> Bool
    f Map k a
    m0
    {-# INLINEABLE spanAntitone #-}

    -- | /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
    mapMaybe :: forall a b k. (a -> Maybe b) -> NEMap k a -> Map k b
    mapMaybe a -> Maybe b
    f = (k -> a -> Maybe b) -> NEMap k a -> Map k b
    forall k a b. (k -> a -> Maybe b) -> NEMap k a -> Map k b
    mapMaybeWithKey ((a -> Maybe b) -> k -> a -> Maybe b
    forall a b. a -> b -> a
    const a -> Maybe b
    f)
    {-# INLINE mapMaybe #-}

    -- | /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
    mapMaybeWithKey :: forall k a b. (k -> a -> Maybe b) -> NEMap k a -> Map k b
    mapMaybeWithKey k -> a -> Maybe b
    f (NEMap k
    k a
    v Map k a
    m) = (Map k b -> Map k b)
    -> (b -> Map k b -> Map k b) -> Maybe b -> Map k b -> Map k b
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k b -> Map k b
    forall a. a -> a
    id (k -> b -> Map k b -> Map k b
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k) (k -> a -> Maybe b
    f k
    k a
    v) ((k -> a -> Maybe b) -> Map k a -> Map k b
    forall k a b. (k -> a -> Maybe b) -> Map k a -> Map k b
    M.mapMaybeWithKey k -> a -> Maybe b
    f Map k a
    m)
    {-# INLINE mapMaybeWithKey #-}

    -- | /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)
    mapEither :: forall a b c k.
    (a -> Either b c) -> NEMap k a -> These (NEMap k b) (NEMap k c)
    mapEither a -> Either b c
    f = (k -> a -> Either b c)
    -> NEMap k a -> These (NEMap k b) (NEMap k c)
    forall k a b c.
    (k -> a -> Either b c)
    -> NEMap k a -> These (NEMap k b) (NEMap k c)
    mapEitherWithKey ((a -> Either b c) -> k -> a -> Either b c
    forall a b. a -> b -> a
    const a -> Either b c
    f)
    {-# INLINE mapEither #-}

    -- | /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)
    mapEitherWithKey :: forall k a b c.
    (k -> a -> Either b c)
    -> NEMap k a -> These (NEMap k b) (NEMap k c)
    mapEitherWithKey k -> a -> Either b c
    f (NEMap k
    k a
    v Map k a
    m0) = case (Map k b -> Maybe (NEMap k b)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k b
    m1, Map k c -> Maybe (NEMap k c)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k c
    m2) of
      (Maybe (NEMap k b)
    Nothing, Maybe (NEMap k c)
    Nothing) -> case k -> a -> Either b c
    f k
    k a
    v of
        Left b
    v' -> NEMap k b -> These (NEMap k b) (NEMap k c)
    forall a b. a -> These a b
    This (k -> b -> NEMap k b
    forall k a. k -> a -> NEMap k a
    singleton k
    k b
    v')
        Right c
    v' -> NEMap k c -> These (NEMap k b) (NEMap k c)
    forall a b. b -> These a b
    That (k -> c -> NEMap k c
    forall k a. k -> a -> NEMap k a
    singleton k
    k c
    v')
      (Just NEMap k b
    n1, Maybe (NEMap k c)
    Nothing) -> case k -> a -> Either b c
    f k
    k a
    v of
        Left b
    v' -> NEMap k b -> These (NEMap k b) (NEMap k c)
    forall a b. a -> These a b
    This (k -> b -> Map k b -> NEMap k b
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k b
    v' Map k b
    m1)
        Right c
    v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
    forall a b. a -> b -> These a b
    These NEMap k b
    n1 (k -> c -> NEMap k c
    forall k a. k -> a -> NEMap k a
    singleton k
    k c
    v')
      (Maybe (NEMap k b)
    Nothing, Just NEMap k c
    n2) -> case k -> a -> Either b c
    f k
    k a
    v of
        Left b
    v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
    forall a b. a -> b -> These a b
    These (k -> b -> NEMap k b
    forall k a. k -> a -> NEMap k a
    singleton k
    k b
    v') NEMap k c
    n2
        Right c
    v' -> NEMap k c -> These (NEMap k b) (NEMap k c)
    forall a b. b -> These a b
    That (k -> c -> Map k c -> NEMap k c
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k c
    v' Map k c
    m2)
      (Just NEMap k b
    n1, Just NEMap k c
    n2) -> case k -> a -> Either b c
    f k
    k a
    v of
        Left b
    v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
    forall a b. a -> b -> These a b
    These (k -> b -> Map k b -> NEMap k b
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k b
    v' Map k b
    m1) NEMap k c
    n2
        Right c
    v' -> NEMap k b -> NEMap k c -> These (NEMap k b) (NEMap k c)
    forall a b. a -> b -> These a b
    These NEMap k b
    n1 (k -> c -> Map k c -> NEMap k c
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k c
    v' Map k c
    m2)
      where
        (Map k b
    m1, Map k c
    m2) = (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
    forall k a b c.
    (k -> a -> Either b c) -> Map k a -> (Map k b, Map k c)
    M.mapEitherWithKey k -> a -> Either b c
    f Map k a
    m0
    {-# INLINEABLE mapEitherWithKey #-}

    -- | /O(log n)/. The expression (@'split' k map@) is potentially a 'These'
    -- containing up to two 'NEMap's based on splitting the map into maps
    -- containing items before and after the given key @k@.  It will never
    -- return a map that contains @k@ itself.
    --
    -- *   '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))
    split :: forall k a.
    Ord k =>
    k -> NEMap k a -> Maybe (These (NEMap k a) (NEMap k a))
    split k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v Map k a
    m0) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> These (NEMap k a) (NEMap k a)
    -> Maybe (These (NEMap k a) (NEMap k a))
    forall a. a -> Maybe a
    Just (These (NEMap k a) (NEMap k a)
     -> Maybe (These (NEMap k a) (NEMap k a)))
    -> These (NEMap k a) (NEMap k a)
    -> Maybe (These (NEMap k a) (NEMap k a))
    forall a b. (a -> b) -> a -> b
    $ NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That NEMap k a
    n
      Ordering
    EQ -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That (NEMap k a -> These (NEMap k a) (NEMap k a))
    -> Maybe (NEMap k a) -> Maybe (These (NEMap k a) (NEMap k a))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m0
      Ordering
    GT -> These (NEMap k a) (NEMap k a)
    -> Maybe (These (NEMap k a) (NEMap k a))
    forall a. a -> Maybe a
    Just (These (NEMap k a) (NEMap k a)
     -> Maybe (These (NEMap k a) (NEMap k a)))
    -> These (NEMap k a) (NEMap k a)
    -> Maybe (These (NEMap k a) (NEMap k a))
    forall a b. (a -> b) -> a -> b
    $ case (Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m1, Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m2) of
        (Maybe (NEMap k a)
    Nothing, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k0 a
    v)
        (Just NEMap k a
    _, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k0 a
    v Map k a
    m1)
        (Maybe (NEMap k a)
    Nothing, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k0 a
    v) NEMap k a
    n2
        (Just NEMap k a
    _, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k0 a
    v Map k a
    m1) NEMap k a
    n2
      where
        (Map k a
    m1, Map k a
    m2) = k -> Map k a -> (Map k a, Map k a)
    forall k a. Ord k => k -> Map k a -> (Map k a, Map k a)
    M.split k
    k Map k a
    m0
    {-# INLINEABLE split #-}

    -- | /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))
    splitLookup :: forall k a.
    Ord k =>
    k -> NEMap k a -> These a (These (NEMap k a) (NEMap k a))
    splitLookup k
    k n :: NEMap k a
    n@(NEMap k
    k0 a
    v0 Map k a
    m0) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> These (NEMap k a) (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a))
    forall a b. b -> These a b
    That (These (NEMap k a) (NEMap k a)
     -> These a (These (NEMap k a) (NEMap k a)))
    -> (NEMap k a -> These (NEMap k a) (NEMap k a))
    -> NEMap k a
    -> These a (These (NEMap k a) (NEMap k a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That (NEMap k a -> These a (These (NEMap k a) (NEMap k a)))
    -> NEMap k a -> These a (These (NEMap k a) (NEMap k a))
    forall a b. (a -> b) -> a -> b
    $ NEMap k a
    n
      Ordering
    EQ -> These a (These (NEMap k a) (NEMap k a))
    -> (NEMap k a -> These a (These (NEMap k a) (NEMap k a)))
    -> Maybe (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a))
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe (a -> These a (These (NEMap k a) (NEMap k a))
    forall a b. a -> These a b
    This a
    v0) (a
    -> These (NEMap k a) (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a))
    forall a b. a -> b -> These a b
    These a
    v0 (These (NEMap k a) (NEMap k a)
     -> These a (These (NEMap k a) (NEMap k a)))
    -> (NEMap k a -> These (NEMap k a) (NEMap k a))
    -> NEMap k a
    -> These a (These (NEMap k a) (NEMap k a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That) (Maybe (NEMap k a) -> These a (These (NEMap k a) (NEMap k a)))
    -> (Map k a -> Maybe (NEMap k a))
    -> Map k a
    -> These a (These (NEMap k a) (NEMap k a))
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap (Map k a -> These a (These (NEMap k a) (NEMap k a)))
    -> Map k a -> These a (These (NEMap k a) (NEMap k a))
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m0
      Ordering
    GT -> (These (NEMap k a) (NEMap k a)
     -> These a (These (NEMap k a) (NEMap k a)))
    -> (a
        -> These (NEMap k a) (NEMap k a)
        -> These a (These (NEMap k a) (NEMap k a)))
    -> Maybe a
    -> These (NEMap k a) (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a))
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe These (NEMap k a) (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a))
    forall a b. b -> These a b
    That a
    -> These (NEMap k a) (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a))
    forall a b. a -> b -> These a b
    These Maybe a
    v (These (NEMap k a) (NEMap k a)
     -> These a (These (NEMap k a) (NEMap k a)))
    -> These (NEMap k a) (NEMap k a)
    -> These a (These (NEMap k a) (NEMap k a))
    forall a b. (a -> b) -> a -> b
    $ case (Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m1, Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m2) of
        (Maybe (NEMap k a)
    Nothing, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k0 a
    v0)
        (Just NEMap k a
    _, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k0 a
    v0 Map k a
    m1)
        (Maybe (NEMap k a)
    Nothing, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k0 a
    v0) NEMap k a
    n2
        (Just NEMap k a
    _, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k0 a
    v0 Map k a
    m1) NEMap k a
    n2
      where
        (Map k a
    m1, Maybe a
    v, Map k a
    m2) = k -> Map k a -> (Map k a, Maybe a, Map k a)
    forall k a. Ord k => k -> Map k a -> (Map k a, Maybe a, Map k a)
    M.splitLookup k
    k Map k a
    m0
    {-# INLINEABLE splitLookup #-}

    -- | /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)
    splitRoot :: forall k a. NEMap k a -> NonEmpty (NEMap k a)
    splitRoot (NEMap k
    k a
    v Map k a
    m) =
      k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v
        NEMap k a -> [NEMap k a] -> NonEmpty (NEMap k a)
    forall a. a -> [a] -> NonEmpty a
    :| (Map k a -> Maybe (NEMap k a)) -> [Map k a] -> [NEMap k a]
    forall a b. (a -> Maybe b) -> [a] -> [b]
    Maybe.mapMaybe Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap (Map k a -> [Map k a]
    forall k b. Map k b -> [Map k b]
    M.splitRoot Map k a
    m)
    {-# INLINE splitRoot #-}

    -- | /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
    isSubmapOf :: forall k a. (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool
    isSubmapOf = (a -> a -> Bool) -> NEMap k a -> NEMap k a -> Bool
    forall k a b.
    Ord k =>
    (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
    isSubmapOfBy a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)
    {-# INLINE isSubmapOf #-}

    -- | /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
    isSubmapOfBy :: forall k a b.
    Ord k =>
    (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
    isSubmapOfBy a -> b -> Bool
    f (NEMap k
    k a
    v Map k a
    m0) (NEMap k b -> Map k b
    forall k a. NEMap k a -> Map k a
    toMap -> Map k b
    m1) =
      Bool
    kvSub
        Bool -> Bool -> Bool
    && (a -> b -> Bool) -> Map k a -> Map k b -> Bool
    forall k a b.
    Ord k =>
    (a -> b -> Bool) -> Map k a -> Map k b -> Bool
    M.isSubmapOfBy a -> b -> Bool
    f Map k a
    m0 Map k b
    m1
      where
        kvSub :: Bool
    kvSub = case k -> Map k b -> Maybe b
    forall k a. Ord k => k -> Map k a -> Maybe a
    M.lookup k
    k Map k b
    m1 of
          Just b
    v0 -> a -> b -> Bool
    f a
    v b
    v0
          Maybe b
    Nothing -> Bool
    False
    {-# INLINE isSubmapOfBy #-}

    -- | /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
    isProperSubmapOf :: forall k a. (Ord k, Eq a) => NEMap k a -> NEMap k a -> Bool
    isProperSubmapOf = (a -> a -> Bool) -> NEMap k a -> NEMap k a -> Bool
    forall k a b.
    Ord k =>
    (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
    isProperSubmapOfBy a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    (==)
    {-# INLINE isProperSubmapOf #-}

    -- | /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
    isProperSubmapOfBy :: forall k a b.
    Ord k =>
    (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
    isProperSubmapOfBy a -> b -> Bool
    f NEMap k a
    m1 NEMap k b
    m2 =
      Map k a -> Int
    forall k a. Map k a -> Int
    M.size (NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    nemMap NEMap k a
    m1) Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Map k b -> Int
    forall k a. Map k a -> Int
    M.size (NEMap k b -> Map k b
    forall k a. NEMap k a -> Map k a
    nemMap NEMap k b
    m2)
        Bool -> Bool -> Bool
    && (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
    forall k a b.
    Ord k =>
    (a -> b -> Bool) -> NEMap k a -> NEMap k b -> Bool
    isSubmapOfBy a -> b -> Bool
    f NEMap k a
    m1 NEMap k b
    m2
    {-# INLINE isProperSubmapOfBy #-}

    -- | /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
    lookupIndex :: forall k a. Ord k => k -> NEMap k a -> Maybe Int
    lookupIndex k
    k (NEMap k
    k0 a
    _ Map k a
    m) = case k -> k -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare k
    k k
    k0 of
      Ordering
    LT -> Maybe Int
    forall a. Maybe a
    Nothing
      Ordering
    EQ -> Int -> Maybe Int
    forall a. a -> Maybe a
    Just Int
    0
      Ordering
    GT -> (Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) (Int -> Int) -> Maybe Int -> Maybe Int
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> k -> Map k a -> Maybe Int
    forall k a. Ord k => k -> Map k a -> Maybe Int
    M.lookupIndex k
    k Map k a
    m
    {-# INLINE lookupIndex #-}

    -- | /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
    findIndex :: forall k a. Ord k => k -> NEMap k a -> Int
    findIndex k
    k = Int -> Maybe Int -> Int
    forall a. a -> Maybe a -> a
    fromMaybe Int
    forall {a}. a
    e (Maybe Int -> Int) -> (NEMap k a -> Maybe Int) -> NEMap k a -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> NEMap k a -> Maybe Int
    forall k a. Ord k => k -> NEMap k a -> Maybe Int
    lookupIndex k
    k
      where
        e :: a
    e = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NEMap.findIndex: element is not in the map"
    {-# INLINE findIndex #-}

    -- | /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)
    elemAt :: forall k a. Int -> NEMap k a -> (k, a)
    elemAt Int
    0 (NEMap k
    k a
    v Map k a
    _) = (k
    k, a
    v)
    elemAt Int
    i (NEMap k
    _ a
    _ Map k a
    m) = Int -> Map k a -> (k, a)
    forall k a. Int -> Map k a -> (k, a)
    M.elemAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Map k a
    m
    {-# INLINEABLE elemAt #-}

    -- | /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
    updateAt :: forall k a. (k -> a -> Maybe a) -> Int -> NEMap k a -> Map k a
    updateAt k -> a -> Maybe a
    f Int
    0 (NEMap k
    k a
    v Map k a
    m) = Map k a -> (a -> Map k a) -> Maybe a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a
    m ((a -> Map k a -> Map k a) -> Map k a -> a -> Map k a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k) Map k a
    m) (Maybe a -> Map k a) -> Maybe a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ k -> a -> Maybe a
    f k
    k a
    v
    updateAt k -> a -> Maybe a
    f Int
    i (NEMap k
    k a
    v Map k a
    m) = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
    forall k a. (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
    M.updateAt k -> a -> Maybe a
    f (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINEABLE updateAt #-}

    -- | /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
    adjustAt :: forall k a. (k -> a -> a) -> Int -> NEMap k a -> NEMap k a
    adjustAt k -> a -> a
    f Int
    0 (NEMap k
    k0 a
    v Map k a
    m) = k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 (k -> a -> a
    f k
    k0 a
    v) Map k a
    m
    adjustAt k -> a -> a
    f Int
    i (NEMap k
    k0 a
    v Map k a
    m) =
      k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 a
    v
        (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
    forall k a. (k -> a -> Maybe a) -> Int -> Map k a -> Map k a
    M.updateAt (\k
    k -> a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> (a -> a) -> a -> Maybe a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> a -> a
    f k
    k) (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1)
        (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINEABLE adjustAt #-}

    -- | /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
    deleteAt :: forall k a. Int -> NEMap k a -> Map k a
    deleteAt Int
    0 (NEMap k
    _ a
    _ Map k a
    m) = Map k a
    m
    deleteAt Int
    i (NEMap k
    k a
    v Map k a
    m) = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Map k a -> Map k a
    forall k a. Int -> Map k a -> Map k a
    M.deleteAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINEABLE deleteAt #-}

    -- | 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
    take :: forall k a. Int -> NEMap k a -> Map k a
    take Int
    0 NEMap{} = Map k a
    forall k a. Map k a
    M.empty
    take Int
    i (NEMap k
    k a
    v Map k a
    m) = k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Int -> Map k a -> Map k a
    forall k a. Int -> Map k a -> Map k a
    M.take (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINEABLE take #-}

    -- | 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
    drop :: forall k a. Int -> NEMap k a -> Map k a
    drop Int
    0 NEMap k a
    n = NEMap k a -> Map k a
    forall k a. NEMap k a -> Map k a
    toMap NEMap k a
    n
    drop Int
    i (NEMap k
    _ a
    _ Map k a
    m) = Int -> Map k a -> Map k a
    forall k a. Int -> Map k a -> Map k a
    M.drop (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Map k a
    m
    {-# INLINEABLE drop #-}

    -- | /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)
    splitAt :: forall k a. Int -> NEMap k a -> These (NEMap k a) (NEMap k a)
    splitAt Int
    0 NEMap k a
    n = NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. b -> These a b
    That NEMap k a
    n
    splitAt Int
    i n :: NEMap k a
    n@(NEMap k
    k a
    v Map k a
    m0) = case (Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m1, Map k a -> Maybe (NEMap k a)
    forall k a. Map k a -> Maybe (NEMap k a)
    nonEmptyMap Map k a
    m2) of
      (Maybe (NEMap k a)
    Nothing, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v)
      (Just NEMap k a
    _, Maybe (NEMap k a)
    Nothing) -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> These a b
    This NEMap k a
    n
      (Maybe (NEMap k a)
    Nothing, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> NEMap k a
    forall k a. k -> a -> NEMap k a
    singleton k
    k a
    v) NEMap k a
    n2
      (Just NEMap k a
    _, Just NEMap k a
    n2) -> NEMap k a -> NEMap k a -> These (NEMap k a) (NEMap k a)
    forall a b. a -> b -> These a b
    These (k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k a
    v Map k a
    m1) NEMap k a
    n2
      where
        (Map k a
    m1, Map k a
    m2) = Int -> Map k a -> (Map k a, Map k a)
    forall k a. Int -> Map k a -> (Map k a, Map k a)
    M.splitAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Map k a
    m0
    {-# INLINEABLE splitAt #-}

    -- | /O(1)/. The minimal key of the map.  Note that this is total, making
    -- 'Data.Map.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)
    findMin :: forall k a. NEMap k a -> (k, a)
    findMin (NEMap k
    k a
    v Map k a
    _) = (k
    k, a
    v)
    {-# INLINE findMin #-}

    -- | /O(log n)/. The maximal key of the map.  Note that this is total, making
    -- 'Data.Map.lookupMin' obsolete.
    --
    -- > findMax (fromList ((5,"a") :| [(3,"b")])) == (5,"a")
    findMax :: NEMap k a -> (k, a)
    findMax :: forall k a. NEMap k a -> (k, a)
    findMax (NEMap k
    k a
    v Map k a
    m) = (k, a) -> Maybe (k, a) -> (k, a)
    forall a. a -> Maybe a -> a
    fromMaybe (k
    k, a
    v) (Maybe (k, a) -> (k, a))
    -> (Map k a -> Maybe (k, a)) -> Map k a -> (k, a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map k a -> Maybe (k, a)
    forall k a. Map k a -> Maybe (k, a)
    M.lookupMax (Map k a -> (k, a)) -> Map k a -> (k, a)
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE findMax #-}

    -- | /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
    -- 'Data.Map.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
    deleteMin :: forall k a. NEMap k a -> Map k a
    deleteMin (NEMap k
    _ a
    _ Map k a
    m) = Map k a
    m
    {-# INLINE deleteMin #-}

    -- | /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
    deleteMax :: forall k a. NEMap k a -> Map k a
    deleteMax (NEMap k
    k a
    v Map k a
    m) = case Map k a -> Maybe (a, Map k a)
    forall k a. Map k a -> Maybe (a, Map k a)
    M.maxView Map k a
    m of
      Maybe (a, Map k a)
    Nothing -> Map k a
    forall k a. Map k a
    M.empty
      Just (a
    _, Map k a
    m') -> k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v Map k a
    m'
    {-# INLINE deleteMax #-}

    -- | /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
    updateMin :: forall a k. (a -> Maybe a) -> NEMap k a -> Map k a
    updateMin a -> Maybe a
    f = (k -> a -> Maybe a) -> NEMap k a -> Map k a
    forall k a. (k -> a -> Maybe a) -> NEMap k a -> Map k a
    updateMinWithKey ((a -> Maybe a) -> k -> a -> Maybe a
    forall a b. a -> b -> a
    const a -> Maybe a
    f)
    {-# INLINE updateMin #-}

    -- | /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
    adjustMin :: forall a k. (a -> a) -> NEMap k a -> NEMap k a
    adjustMin a -> a
    f = (k -> a -> a) -> NEMap k a -> NEMap k a
    forall k a. (k -> a -> a) -> NEMap k a -> NEMap k a
    adjustMinWithKey ((a -> a) -> k -> a -> a
    forall a b. a -> b -> a
    const a -> a
    f)
    {-# INLINE adjustMin #-}

    -- | /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
    updateMinWithKey :: forall k a. (k -> a -> Maybe a) -> NEMap k a -> Map k a
    updateMinWithKey k -> a -> Maybe a
    f (NEMap k
    k a
    v Map k a
    m) = (Map k a -> Map k a)
    -> (a -> Map k a -> Map k a) -> Maybe a -> Map k a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a -> Map k a
    forall a. a -> a
    id (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k) (k -> a -> Maybe a
    f k
    k a
    v) Map k a
    m
    {-# INLINE updateMinWithKey #-}

    -- | /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
    adjustMinWithKey :: forall k a. (k -> a -> a) -> NEMap k a -> NEMap k a
    adjustMinWithKey k -> a -> a
    f (NEMap k
    k a
    v Map k a
    m) = k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k (k -> a -> a
    f k
    k a
    v) Map k a
    m
    {-# INLINE adjustMinWithKey #-}

    -- | /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
    updateMax :: forall a k. (a -> Maybe a) -> NEMap k a -> Map k a
    updateMax a -> Maybe a
    f = (k -> a -> Maybe a) -> NEMap k a -> Map k a
    forall k a. (k -> a -> Maybe a) -> NEMap k a -> Map k a
    updateMaxWithKey ((a -> Maybe a) -> k -> a -> Maybe a
    forall a b. a -> b -> a
    const a -> Maybe a
    f)
    {-# INLINE updateMax #-}

    -- | /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
    adjustMax :: forall a k. (a -> a) -> NEMap k a -> NEMap k a
    adjustMax a -> a
    f = (k -> a -> a) -> NEMap k a -> NEMap k a
    forall k a. (k -> a -> a) -> NEMap k a -> NEMap k a
    adjustMaxWithKey ((a -> a) -> k -> a -> a
    forall a b. a -> b -> a
    const a -> a
    f)
    {-# INLINE adjustMax #-}

    -- | /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
    updateMaxWithKey :: forall k a. (k -> a -> Maybe a) -> NEMap k a -> Map k a
    updateMaxWithKey k -> a -> Maybe a
    f (NEMap k
    k a
    v Map k a
    m)
      | Map k a -> Bool
    forall k a. Map k a -> Bool
    M.null Map k a
    m = Map k a -> (a -> Map k a) -> Maybe a -> Map k a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Map k a
    m (k -> a -> Map k a
    forall k a. k -> a -> Map k a
    M.singleton k
    k) (Maybe a -> Map k a) -> Maybe a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ k -> a -> Maybe a
    f k
    k a
    v
      | Bool
    otherwise =
          k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v
            (Map k a -> Map k a) -> (Map k a -> Map k a) -> Map k a -> Map k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> Maybe a) -> Map k a -> Map k a
    forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
    M.updateMaxWithKey k -> a -> Maybe a
    f
            (Map k a -> Map k a) -> Map k a -> Map k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE updateMaxWithKey #-}

    -- | /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
    adjustMaxWithKey :: forall k a. (k -> a -> a) -> NEMap k a -> NEMap k a
    adjustMaxWithKey k -> a -> a
    f (NEMap k
    k0 a
    v Map k a
    m)
      | Map k a -> Bool
    forall k a. Map k a -> Bool
    M.null Map k a
    m = k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    NEMap k
    k0 (k -> a -> a
    f k
    k0 a
    v) Map k a
    m
      | Bool
    otherwise =
          k -> a -> Map k a -> NEMap k a
    forall k a. k -> a -> Map k a -> NEMap k a
    insertMapMin k
    k0 a
    v
            (Map k a -> NEMap k a)
    -> (Map k a -> Map k a) -> Map k a -> NEMap k a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (k -> a -> Maybe a) -> Map k a -> Map k a
    forall k a. (k -> a -> Maybe a) -> Map k a -> Map k a
    M.updateMaxWithKey (\k
    k -> a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> (a -> a) -> a -> Maybe a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . k -> a -> a
    f k
    k)
            (Map k a -> NEMap k a) -> Map k a -> NEMap k a
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE adjustMaxWithKey #-}

    -- | /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)
    minView :: forall k a. NEMap k a -> (a, Map k a)
    minView = ((k, a) -> a) -> ((k, a), Map k a) -> (a, Map k a)
    forall a b c. (a -> b) -> (a, c) -> (b, c)
    forall (p :: * -> * -> *) a b c.
    Bifunctor p =>
    (a -> b) -> p a c -> p b c
    first (k, a) -> a
    forall a b. (a, b) -> b
    snd (((k, a), Map k a) -> (a, Map k a))
    -> (NEMap k a -> ((k, a), Map k a)) -> NEMap k a -> (a, Map k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> ((k, a), Map k a)
    forall k a. NEMap k a -> ((k, a), Map k a)
    deleteFindMin
    {-# INLINE minView #-}

    -- | /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)
    deleteFindMin :: forall k a. NEMap k a -> ((k, a), Map k a)
    deleteFindMin (NEMap k
    k a
    v Map k a
    m) = ((k
    k, a
    v), Map k a
    m)
    {-# INLINE deleteFindMin #-}

    -- | /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)
    maxView :: forall k a. NEMap k a -> (a, Map k a)
    maxView = ((k, a) -> a) -> ((k, a), Map k a) -> (a, Map k a)
    forall a b c. (a -> b) -> (a, c) -> (b, c)
    forall (p :: * -> * -> *) a b c.
    Bifunctor p =>
    (a -> b) -> p a c -> p b c
    first (k, a) -> a
    forall a b. (a, b) -> b
    snd (((k, a), Map k a) -> (a, Map k a))
    -> (NEMap k a -> ((k, a), Map k a)) -> NEMap k a -> (a, Map k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NEMap k a -> ((k, a), Map k a)
    forall k a. NEMap k a -> ((k, a), Map k a)
    deleteFindMax
    {-# INLINE maxView #-}

    -- | /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)
    deleteFindMax :: forall k a. NEMap k a -> ((k, a), Map k a)
    deleteFindMax (NEMap k
    k a
    v Map k a
    m) =
      ((k, a), Map k a)
    -> (((k, a), Map k a) -> ((k, a), Map k a))
    -> Maybe ((k, a), Map k a)
    -> ((k, a), Map k a)
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe ((k
    k, a
    v), Map k a
    forall k a. Map k a
    M.empty) ((Map k a -> Map k a) -> ((k, a), Map k a) -> ((k, a), Map k a)
    forall b c a. (b -> c) -> (a, b) -> (a, c)
    forall (p :: * -> * -> *) b c a.
    Bifunctor p =>
    (b -> c) -> p a b -> p a c
    second (k -> a -> Map k a -> Map k a
    forall k a. k -> a -> Map k a -> Map k a
    insertMinMap k
    k a
    v))
        (Maybe ((k, a), Map k a) -> ((k, a), Map k a))
    -> (Map k a -> Maybe ((k, a), Map k a))
    -> Map k a
    -> ((k, a), Map k a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Map k a -> Maybe ((k, a), Map k a)
    forall k a. Map k a -> Maybe ((k, a), Map k a)
    M.maxViewWithKey
        (Map k a -> ((k, a), Map k a)) -> Map k a -> ((k, a), Map k a)
    forall a b. (a -> b) -> a -> b
    $ Map k a
    m
    {-# INLINE deleteFindMax #-}

    -- | 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'@.
    --
    -- @since 0.3.1.0
    absurdNEMap :: NEMap Void a -> b
    absurdNEMap :: forall a b. NEMap Void a -> b
    absurdNEMap = \case {}

    -- ---------------------------
    -- Combining functions
    -- ---------------------------
    --
    -- Code comes from "Data.Map.Internal" from containers, modified slightly
    -- to work with NonEmpty
    --
    -- Copyright   :  (c) Daan Leijen 2002
    --                (c) Andriy Palamarchuk 2008

    combineEq :: Eq a => NonEmpty (a, b) -> NonEmpty (a, b)
    combineEq :: forall a b. Eq a => NonEmpty (a, b) -> NonEmpty (a, b)
    combineEq = \case
      (a, b)
    x :| [] -> (a, b)
    x (a, b) -> [(a, b)] -> NonEmpty (a, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
      (a, b)
    x :| xx :: [(a, b)]
    xx@((a, b)
    _ : [(a, b)]
    _) -> (a, b) -> [(a, b)] -> NonEmpty (a, b)
    forall {a} {b}. Eq a => (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    x [(a, b)]
    xx
      where
        go :: (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    z [] = (a, b)
    z (a, b) -> [(a, b)] -> NonEmpty (a, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
        go z :: (a, b)
    z@(a
    kz, b
    _) (x :: (a, b)
    x@(a
    kx, b
    xx) : [(a, b)]
    xs')
          | a
    kx a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    kz = (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a
    kx, b
    xx) [(a, b)]
    xs'
          | Bool
    otherwise = (a, b)
    z (a, b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    forall a. a -> NonEmpty a -> NonEmpty a
    NE.<| (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    x [(a, b)]
    xs'

    combineEqWith ::
      Eq a =>
      (a -> b -> b -> b) ->
      NonEmpty (a, b) ->
      NonEmpty (a, b)
    combineEqWith :: forall a b.
    Eq a =>
    (a -> b -> b -> b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    combineEqWith a -> b -> b -> b
    f = \case
      (a, b)
    x :| [] -> (a, b)
    x (a, b) -> [(a, b)] -> NonEmpty (a, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
      (a, b)
    x :| xx :: [(a, b)]
    xx@((a, b)
    _ : [(a, b)]
    _) -> (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    x [(a, b)]
    xx
      where
        go :: (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    z [] = (a, b)
    z (a, b) -> [(a, b)] -> NonEmpty (a, b)
    forall a. a -> [a] -> NonEmpty a
    :| []
        go z :: (a, b)
    z@(a
    kz, b
    zz) (x :: (a, b)
    x@(a
    kx, b
    xx) : [(a, b)]
    xs')
          | a
    kx a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    kz = let yy :: b
    yy = a -> b -> b -> b
    f a
    kx b
    xx b
    zz in (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a
    kx, b
    yy) [(a, b)]
    xs'
          | Bool
    otherwise = (a, b)
    z (a, b) -> NonEmpty (a, b) -> NonEmpty (a, b)
    forall a. a -> NonEmpty a -> NonEmpty a
    NE.<| (a, b) -> [(a, b)] -> NonEmpty (a, b)
    go (a, b)
    x [(a, b)]
    xs'