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

    -- |
    -- Module      : Data.Sequence.NonEmpty
    -- Copyright   : (c) Justin Le 2018
    -- License     : BSD3
    --
    -- Maintainer  : justin@jle.im
    -- Stability   : experimental
    -- Portability : non-portable
    --
    -- = Non-Empty Finite Sequences
    --
    -- | An @'NESeq' a@ is a non-empty (but finite) sequence of values of type
    -- @a@.  Generally has the same interface as 'Data.List.NonEmpty.NonEmpty'.
    -- This is a non-empty version of 'Data.Sequence.Seq' from "Data.Sequence".
    --
    -- The main differences between this type and 'Data.List.NonEmpty.NonEmpty'
    -- are:
    --
    -- *   You cannot have infinite 'NESeq's
    -- *   You have constant-time consing from either end, and constant-time
    --     unconsing as well (through '<|', '|>', ':<||', and ':||>')
    -- *   Concatenation ('><', '|><', '><|') is logarithmic-time.
    -- *   You have logarithmic-time indexing and updating at a given index.
    --
    -- While asymptotics are often better than for 'Data.List.NonEmpty.NonEmpty', there is
    -- a decent constant factor involved in most operations.
    --
    -- See documentation for 'NESeq' for information on how to convert and
    -- manipulate such non-empty sequences
    --
    -- This module essentially re-imports the API of "Data.Sequence.Lazy" and its
    -- 'Seq' type, along with semantics and asymptotics.
    --
    -- Because 'NESeq' is implemented using 'Seq', all of the caveats of using
    -- 'Seq' apply.
    --
    -- All functions take non-empty sequences as inputs.  In situations where
    -- their results can be guarunteed to also be non-empty, they also return
    -- non-empty maps.  In situations where their results could potentially be
    -- empty, 'Seq' is returned instead.
    --
    -- Some functions (like 'spanl', 'spanr', 'breakl', 'breakr', 'partition',
    -- 'splitAt') have modified return types to account for possible
    -- configurations of non-emptiness.
    --
    -- Some functions ('head', 'last', 'tail', 'init') are provided because
    -- they are total for non-empty sequences.
    --
    -- This module is intended to be imported qualified, to avoid name clashes with
    -- "Prelude" and "Data.Sequence" functions:
    --
    -- > import qualified Data.Sequence.NonEmpty as NESeq
    module Data.Sequence.NonEmpty (
      -- * Finite sequences
      NESeq ((:<||), (:||>)),

      -- ** Conversions between empty and non-empty sequences
      pattern IsNonEmpty,
      pattern IsEmpty,
      nonEmptySeq,
      toSeq,
      withNonEmpty,
      unsafeFromSeq,
      insertSeqAt,

      -- * Construction
      singleton,
      (<|),
      (|>),
      (><),
      (|><),
      (><|),
      fromList,
      fromFunction,

      -- ** Repetition
      replicate,
      replicateA,
      replicateA1,
      replicateM,
      cycleTaking,

      -- ** Iterative construction
      iterateN,
      unfoldr,
      unfoldl,

      -- * Deconstruction

      -- | Additional functions for deconstructing sequences are available
      -- via the 'Foldable' instance of 'NESeq'.
      head,
      tail,
      last,
      init,

      -- ** Queries
      length,

      -- * Scans
      scanl,
      scanl1,
      scanr,
      scanr1,

      -- * Sublists
      tails,
      inits,
      chunksOf,

      -- ** Sequential searches
      takeWhileL,
      takeWhileR,
      dropWhileL,
      dropWhileR,
      spanl,
      spanr,
      breakl,
      breakr,
      partition,
      filter,

      -- * Sorting
      sort,
      sortBy,
      sortOn,
      unstableSort,
      unstableSortBy,
      unstableSortOn,

      -- * Indexing
      lookup,
      (!?),
      index,
      adjust,
      adjust',
      update,
      take,
      drop,
      insertAt,
      deleteAt,
      splitAt,

      -- ** Indexing with predicates

      -- | These functions perform sequential searches from the left
      -- or right ends of the sequence  returning indices of matching
      -- elements.
      elemIndexL,
      elemIndicesL,
      elemIndexR,
      elemIndicesR,
      findIndexL,
      findIndicesL,
      findIndexR,
      findIndicesR,

      -- * Folds

      -- | General folds are available via the 'Foldable' instance of 'Seq'.
      foldMapWithIndex,
      foldlWithIndex,
      foldrWithIndex,

      -- * Transformations
      mapWithIndex,
      traverseWithIndex,
      traverseWithIndex1,
      reverse,
      intersperse,

      -- ** Zips and unzip
      zip,
      zipWith,
      zip3,
      zipWith3,
      zip4,
      zipWith4,
      unzip,
      unzipWith,
    ) where

    import Control.Applicative
    import Control.Monad hiding (replicateM)
    import Data.Bifunctor
    import Data.Functor.Apply
    import Data.Sequence (Seq (..))
    import qualified Data.Sequence as Seq
    import Data.Sequence.NonEmpty.Internal
    import Data.These
    import Prelude hiding (
      drop,
      filter,
      head,
      init,
      last,
      length,
      lookup,
      map,
      replicate,
      reverse,
      scanl,
      scanl1,
      scanr,
      scanr1,
      splitAt,
      tail,
      take,
      unzip,
      zip,
      zip3,
      zipWith,
      zipWith3,
     )

    -- | /O(1)/. The 'IsNonEmpty' and 'IsEmpty' patterns allow you to treat
    -- a 'Seq' as if it were either a @'IsNonEmpty' n@ (where @n@ is a 'NESeq')
    -- or an 'IsEmpty'.
    --
    -- For example, you can pattern match on a 'Seq':
    --
    -- @
    -- safeHead :: 'Seq' Int -> Int
    -- safeHead ('IsNonEmpty' (x :<|| _))  = x  -- here, user provided a non-empty sequence, and @n@ is the 'NESeq'
    -- safeHead 'IsEmpty'                  = 0  -- here the user provided an empty sequence
    -- @
    --
    -- Matching on @'IsNonEmpty' n@ means that the original 'Seq' was /not/
    -- empty, and you have a verified-non-empty 'NESeq' @n@ to use.
    --
    -- A case statement handling both 'IsNonEmpty' and 'IsEmpty' provides
    -- complete coverage.
    --
    -- This is a bidirectional pattern, so you can use 'IsNonEmpty' to convert
    -- a 'NESeq' back into a 'Seq', obscuring its non-emptiness (see 'toSeq').
    pattern IsNonEmpty :: NESeq a -> Seq a
    pattern $mIsNonEmpty :: forall {r} {a}. Seq a -> (NESeq a -> r) -> ((# #) -> r) -> r
    $bIsNonEmpty :: forall a. NESeq a -> Seq a
    IsNonEmpty n <- (nonEmptySeq -> Just n)
      where
        IsNonEmpty NESeq a
    n = NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq NESeq a
    n

    -- | /O(1)/. The 'IsNonEmpty' and 'IsEmpty' patterns allow you to treat
    -- a 'Seq' as if it were either a @'IsNonEmpty' n@ (where @n@ is
    -- a 'NESeq') or an 'IsEmpty'.
    --
    -- Matching on 'IsEmpty' means that the original 'Seq' was empty.
    --
    -- A case statement handling both 'IsNonEmpty' and 'IsEmpty' provides
    -- complete coverage.
    --
    -- This is a bidirectional pattern, so you can use 'IsEmpty' as an
    -- expression, and it will be interpreted as 'Data.Seq.empty'.
    --
    -- See 'IsNonEmpty' for more information.
    pattern IsEmpty :: Seq a
    pattern $mIsEmpty :: forall {r} {a}. Seq a -> ((# #) -> r) -> ((# #) -> r) -> r
    $bIsEmpty :: forall a. Seq a
    IsEmpty <- (Seq.null -> True)
      where
        IsEmpty = Seq a
    forall a. Seq a
    Seq.empty

    {-# COMPLETE IsNonEmpty, IsEmpty #-}

    -- | /O(1)/. Smart constructor for an 'NESeq' from a 'Seq'.  Returns
    -- 'Nothing' if the 'Seq' was originally actually empty, and @'Just' n@
    -- with an 'NESeq', if the 'Seq' was not empty.
    --
    -- 'nonEmptySeq' and @'maybe' 'Data.Sequence.empty' 'toSeq'@ form an
    -- isomorphism: they are perfect structure-preserving inverses of
    -- eachother.
    --
    -- See 'Data.Sequence.NonEmpty.IsNonEmpty' for a pattern synonym that lets
    -- you "match on" the possiblity of a 'Seq' being an 'NESeq'.
    --
    -- > nonEmptySeq (Data.Sequence.fromList [1,2,3]) == Just (fromList (1) :| [2,3])
    nonEmptySeq :: Seq a -> Maybe (NESeq a)
    nonEmptySeq :: forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq (a
    x :<| Seq a
    xs) = NESeq a -> Maybe (NESeq a)
    forall a. a -> Maybe a
    Just (NESeq a -> Maybe (NESeq a)) -> NESeq a -> Maybe (NESeq a)
    forall a b. (a -> b) -> a -> b
    $ a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a
    xs
    nonEmptySeq Seq a
    Empty = Maybe (NESeq a)
    forall a. Maybe a
    Nothing
    {-# INLINE nonEmptySeq #-}

    -- | /O(1)/. Unsafe version of 'nonEmptySeq'.  Coerces a 'Seq' into an
    -- 'NESeq', but is undefined (throws a runtime exception when evaluation is
    -- attempted) for an empty 'Seq'.
    unsafeFromSeq :: Seq a -> NESeq a
    unsafeFromSeq :: forall a. Seq a -> NESeq a
    unsafeFromSeq (a
    x :<| Seq a
    xs) = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a
    xs
    unsafeFromSeq Seq a
    Empty = [Char] -> NESeq a
    forall a. [Char] -> a
    errorWithoutStackTrace [Char]
    "NESeq.unsafeFromSeq: empty seq"
    {-# INLINE unsafeFromSeq #-}

    -- | Turn a 'Seq' into a guarantted non-empty 'NESeq' by adding an element
    -- at a given index.
    --
    -- > insertSeqAt 1 0 (Data.Sequence.fromList [1,2,3]) == fromList (1 :| [0,2,3])
    insertSeqAt :: Int -> a -> Seq a -> NESeq a
    insertSeqAt :: forall a. Int -> a -> Seq a -> NESeq a
    insertSeqAt Int
    i a
    y
      | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = (a
    y a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<||)
      | Bool
    otherwise = \case
          a
    x :<| Seq a
    xs -> a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Int -> a -> Seq a -> Seq a
    forall a. Int -> a -> Seq a -> Seq a
    Seq.insertAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) a
    y Seq a
    xs
          Seq a
    Empty -> a
    y a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a
    forall a. Seq a
    Seq.empty
    {-# INLINE insertSeqAt #-}

    -- | \( O(1) \). Add an element to the right end of a non-empty sequence.
    -- Mnemonic: a triangle with the single element at the pointy end.
    (|>) :: NESeq a -> a -> NESeq a
    (a
    x :<|| Seq a
    xs) |> :: forall a. NESeq a -> a -> NESeq a
    |> a
    y = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| (Seq a
    xs Seq a -> a -> Seq a
    forall a. Seq a -> a -> Seq a
    Seq.|> a
    y)
    {-# INLINE (|>) #-}

    -- | \( O(\log(\min(n_1,n_2))) \). Concatenate a non-empty sequence with
    -- a potentially empty sequence ('Seq'), to produce a guaranteed non-empty
    -- sequence.  Mnemonic: like '><', but a pipe for the guarunteed non-empty
    -- side.
    (><|) :: Seq a -> NESeq a -> NESeq a
    Seq a
    xs ><| :: forall a. Seq a -> NESeq a -> NESeq a
    ><| NESeq a
    ys = NESeq a -> (NESeq a -> NESeq a) -> Seq a -> NESeq a
    forall r a. r -> (NESeq a -> r) -> Seq a -> r
    withNonEmpty NESeq a
    ys (NESeq a -> NESeq a -> NESeq a
    forall a. NESeq a -> NESeq a -> NESeq a
    >< NESeq a
    ys) Seq a
    xs
    {-# INLINE (><|) #-}

    infixl 5 |>
    infixr 5 ><|

    -- | 'replicateA' is an 'Applicative' version of 'replicate', and makes \(
    -- O(\log n) \) calls to 'liftA2' and 'pure'.  Is only defined when @n@ is
    -- positive.
    --
    -- > replicateA n x = sequenceA (replicate n x)
    --
    -- Is a more restrictive version of 'replicateA1'.  'replicateA1' should be
    -- preferred whenever possible.
    replicateA :: Applicative f => Int -> f a -> f (NESeq a)
    replicateA :: forall (f :: * -> *) a. Applicative f => Int -> f a -> f (NESeq a)
    replicateA Int
    n f a
    x
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    1 = [Char] -> f (NESeq a)
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NESeq.replicateA: must take a positive integer argument"
      | Bool
    otherwise = (a -> Seq a -> NESeq a) -> f a -> f (Seq a) -> f (NESeq a)
    forall a b c. (a -> b -> c) -> f a -> f b -> f c
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> f a -> f b -> f c
    liftA2 a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    (:<||) f a
    x (Int -> f a -> f (Seq a)
    forall (f :: * -> *) a. Applicative f => Int -> f a -> f (Seq a)
    Seq.replicateA (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) f a
    x)
    {-# INLINE replicateA #-}

    -- | 'replicateA' is an 'Apply' version of 'replicate', and makes \( O(\log
    -- n) \) calls to '<.>'.  Is only defined when @n@ is positive.
    --
    -- > replicateA1 n x = sequence1 (replicate n x)
    replicateA1 :: Apply f => Int -> f a -> f (NESeq a)
    replicateA1 :: forall (f :: * -> *) a. Apply f => Int -> f a -> f (NESeq a)
    replicateA1 Int
    n f a
    x
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    1 = [Char] -> f (NESeq a)
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NESeq.replicateA1: must take a positive integer argument"
      | Bool
    otherwise = case MaybeApply f (Seq a) -> Either (f (Seq a)) (Seq a)
    forall (f :: * -> *) a. MaybeApply f a -> Either (f a) a
    runMaybeApply (Int -> MaybeApply f a -> MaybeApply f (Seq a)
    forall (f :: * -> *) a. Applicative f => Int -> f a -> f (Seq a)
    Seq.replicateA (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) (Either (f a) a -> MaybeApply f a
    forall (f :: * -> *) a. Either (f a) a -> MaybeApply f a
    MaybeApply (f a -> Either (f a) a
    forall a b. a -> Either a b
    Left f a
    x))) of
          Left f (Seq a)
    xs -> a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    (:<||) (a -> Seq a -> NESeq a) -> f a -> f (Seq a -> NESeq a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    x f (Seq a -> NESeq a) -> f (Seq a) -> f (NESeq a)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Apply f => f (a -> b) -> f a -> f b
    <.> f (Seq a)
    xs
          Right Seq a
    xs -> (a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a
    xs) (a -> NESeq a) -> f a -> f (NESeq a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    x
    {-# INLINE replicateA1 #-}

    -- | An alias of 'replicateA'.
    replicateM :: Applicative m => Int -> m a -> m (NESeq a)
    replicateM :: forall (f :: * -> *) a. Applicative f => Int -> f a -> f (NESeq a)
    replicateM = Int -> m a -> m (NESeq a)
    forall (f :: * -> *) a. Applicative f => Int -> f a -> f (NESeq a)
    replicateA
    {-# INLINE replicateM #-}

    -- | /O(/log/ k)/. @'cycleTaking' k xs@ forms a sequence of length @k@ by
    -- repeatedly concatenating @xs@ with itself. Is only defined when @k@ is
    -- positive.
    --
    -- prop> cycleTaking k = fromList . fromJust . nonEmpty . take k . cycle . toList

    -- If you wish to concatenate a non-empty sequence @xs@ with itself precisely
    -- @k@ times, you can use @cycleTaking (k * length xs)@ or just
    -- @replicate k () *> xs@.
    cycleTaking :: Int -> NESeq a -> NESeq a
    cycleTaking :: forall a. Int -> NESeq a -> NESeq a
    cycleTaking Int
    n xs0 :: NESeq a
    xs0@(a
    x :<|| Seq a
    xs)
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    1 = [Char] -> NESeq a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NESeq.cycleTaking: must take a positive integer argument"
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Seq a -> Int
    forall a. Seq a -> Int
    Seq.length Seq a
    xs = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Int -> Seq a -> Seq a
    forall a. Int -> Seq a -> Seq a
    Seq.take (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
      | Bool
    otherwise = NESeq a
    xs0 NESeq a -> Seq a -> NESeq a
    forall a. NESeq a -> Seq a -> NESeq a
    |>< Int -> Seq a -> Seq a
    forall a. Int -> Seq a -> Seq a
    Seq.cycleTaking (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - NESeq a -> Int
    forall a. NESeq a -> Int
    length NESeq a
    xs0) (NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq NESeq a
    xs0)
    {-# INLINE cycleTaking #-}

    -- | \( O(n) \).  Constructs a sequence by repeated application of
    -- a function to a seed value.  Is only defined if given a positive value.
    --
    -- > iterateN n f x = fromList (fromJust (nonEmpty ((Prelude.take n (Prelude.iterate f x)))))
    iterateN :: Int -> (a -> a) -> a -> NESeq a
    iterateN :: forall a. Int -> (a -> a) -> a -> NESeq a
    iterateN Int
    n a -> a
    f a
    x
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    < Int
    1 = [Char] -> NESeq a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "NESeq.iterateN: must take a positive integer argument"
      | Bool
    otherwise = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Int -> (a -> a) -> a -> Seq a
    forall a. Int -> (a -> a) -> a -> Seq a
    Seq.iterateN (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) a -> a
    f (a -> a
    f a
    x)
    {-# INLINE iterateN #-}

    -- | Builds a sequence from a seed value.  Takes time linear in the
    -- number of generated elements.  /WARNING:/ If the number of generated
    -- elements is infinite, this method will not terminate.
    unfoldr :: (b -> (a, Maybe b)) -> b -> NESeq a
    unfoldr :: forall b a. (b -> (a, Maybe b)) -> b -> NESeq a
    unfoldr b -> (a, Maybe b)
    f = b -> NESeq a
    go
      where
        go :: b -> NESeq a
    go b
    x0 = a
    y a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a -> (b -> Seq a) -> Maybe b -> Seq a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Seq a
    forall a. Seq a
    Seq.empty (NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq (NESeq a -> Seq a) -> (b -> NESeq a) -> b -> Seq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> NESeq a
    go) Maybe b
    x1
          where
            (a
    y, Maybe b
    x1) = b -> (a, Maybe b)
    f b
    x0
    {-# INLINE unfoldr #-}

    -- | @'unfoldl' f x@ is equivalent to @'reverse' ('unfoldr' ('fmap' swap . f) x)@.
    unfoldl :: (b -> (Maybe b, a)) -> b -> NESeq a
    unfoldl :: forall b a. (b -> (Maybe b, a)) -> b -> NESeq a
    unfoldl b -> (Maybe b, a)
    f = b -> NESeq a
    go
      where
        go :: b -> NESeq a
    go b
    x0 = Seq a -> (b -> Seq a) -> Maybe b -> Seq a
    forall b a. b -> (a -> b) -> Maybe a -> b
    maybe Seq a
    forall a. Seq a
    Seq.empty (NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq (NESeq a -> Seq a) -> (b -> NESeq a) -> b -> Seq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> NESeq a
    go) Maybe b
    x1 Seq a -> a -> NESeq a
    forall a. Seq a -> a -> NESeq a
    :||> a
    y
          where
            (Maybe b
    x1, a
    y) = b -> (Maybe b, a)
    f b
    x0
    {-# INLINE unfoldl #-}

    -- | /O(1)/. Retrieve the left-most item in a non-empty sequence.  Note
    -- that this function is total.
    head :: NESeq a -> a
    head :: forall a. NESeq a -> a
    head (a
    x :<|| Seq a
    _) = a
    x
    {-# INLINE head #-}

    -- | /O(1)/. Delete the left-most item in a non-empty sequence.  Returns
    -- a potentially empty sequence ('Seq') in the case that the original
    -- 'NESeq' contained only a single element.  Note that this function is
    -- total.
    tail :: NESeq a -> Seq a
    tail :: forall a. NESeq a -> Seq a
    tail (a
    _ :<|| Seq a
    xs) = Seq a
    xs
    {-# INLINE tail #-}

    -- | /O(1)/. Retrieve the right-most item in a non-empty sequence.  Note
    -- that this function is total.
    last :: NESeq a -> a
    last :: forall a. NESeq a -> a
    last (Seq a
    _ :||> a
    x) = a
    x
    {-# INLINE last #-}

    -- | /O(1)/. Delete the right-most item in a non-empty sequence.  Returns
    -- a potentially empty sequence ('Seq') in the case that the original
    -- 'NESeq' contained only a single element.  Note that this function is
    -- total.
    init :: NESeq a -> Seq a
    init :: forall a. NESeq a -> Seq a
    init (Seq a
    xs :||> a
    _) = Seq a
    xs
    {-# INLINE init #-}

    -- | 'scanl' is similar to 'foldl', but returns a sequence of reduced
    -- values from the left:
    --
    -- > scanl f z (fromList [x1, x2, ...]) = fromList [z, z `f` x1, (z `f` x1) `f` x2, ...]
    scanl :: (a -> b -> a) -> a -> NESeq b -> NESeq a
    scanl :: forall a b. (a -> b -> a) -> a -> NESeq b -> NESeq a
    scanl a -> b -> a
    f a
    y0 (b
    x :<|| Seq b
    xs) = a
    y0 a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| (a -> b -> a) -> a -> Seq b -> Seq a
    forall a b. (a -> b -> a) -> a -> Seq b -> Seq a
    Seq.scanl a -> b -> a
    f (a -> b -> a
    f a
    y0 b
    x) Seq b
    xs
    {-# INLINE scanl #-}

    -- | 'scanl1' is a variant of 'scanl' that has no starting value argument:
    --
    -- > scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]
    scanl1 :: (a -> a -> a) -> NESeq a -> NESeq a
    scanl1 :: forall a. (a -> a -> a) -> NESeq a -> NESeq a
    scanl1 a -> a -> a
    f (a
    x :<|| Seq a
    xs) = NESeq a -> (NESeq a -> NESeq a) -> Seq a -> NESeq a
    forall r a. r -> (NESeq a -> r) -> Seq a -> r
    withNonEmpty (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) ((a -> a -> a) -> a -> NESeq a -> NESeq a
    forall a b. (a -> b -> a) -> a -> NESeq b -> NESeq a
    scanl a -> a -> a
    f a
    x) Seq a
    xs
    {-# INLINE scanl1 #-}

    -- | 'scanr' is the right-to-left dual of 'scanl'.
    scanr :: (a -> b -> b) -> b -> NESeq a -> NESeq b
    scanr :: forall a b. (a -> b -> b) -> b -> NESeq a -> NESeq b
    scanr a -> b -> b
    f b
    y0 (Seq a
    xs :||> a
    x) = (a -> b -> b) -> b -> Seq a -> Seq b
    forall a b. (a -> b -> b) -> b -> Seq a -> Seq b
    Seq.scanr a -> b -> b
    f (a -> b -> b
    f a
    x b
    y0) Seq a
    xs Seq b -> b -> NESeq b
    forall a. Seq a -> a -> NESeq a
    :||> b
    y0
    {-# INLINE scanr #-}

    -- | 'scanr1' is a variant of 'scanr' that has no starting value argument.
    scanr1 :: (a -> a -> a) -> NESeq a -> NESeq a
    scanr1 :: forall a. (a -> a -> a) -> NESeq a -> NESeq a
    scanr1 a -> a -> a
    f (Seq a
    xs :||> a
    x) = NESeq a -> (NESeq a -> NESeq a) -> Seq a -> NESeq a
    forall r a. r -> (NESeq a -> r) -> Seq a -> r
    withNonEmpty (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) ((a -> a -> a) -> a -> NESeq a -> NESeq a
    forall a b. (a -> b -> b) -> b -> NESeq a -> NESeq b
    scanr a -> a -> a
    f a
    x) Seq a
    xs
    {-# INLINE scanr1 #-}

    -- | \( O(n) \).  Returns a sequence of all non-empty prefixes of this
    -- sequence, shortest first.  For example,
    --
    -- > tails (fromList (1:|[2,3])) = fromList (fromList (1:|[]) :| [fromList (1:|[2]), fromList (1:|[2,3]))
    --
    -- Evaluating the \( i \)th prefix takes \( O(\log(\min(i, n-i))) \), but evaluating
    -- every prefix in the sequence takes \( O(n) \) due to sharing.

    -- TODO: is this true?
    inits :: NESeq a -> NESeq (NESeq a)
    inits :: forall a. NESeq a -> NESeq (NESeq a)
    inits xs :: NESeq a
    xs@(Seq a
    ys :||> a
    _) = NESeq (NESeq a)
    -> (NESeq a -> NESeq (NESeq a)) -> Seq a -> NESeq (NESeq a)
    forall r a. r -> (NESeq a -> r) -> Seq a -> r
    withNonEmpty (NESeq a -> NESeq (NESeq a)
    forall a. a -> NESeq a
    singleton NESeq a
    xs) ((NESeq (NESeq a) -> NESeq a -> NESeq (NESeq a)
    forall a. NESeq a -> a -> NESeq a
    |> NESeq a
    xs) (NESeq (NESeq a) -> NESeq (NESeq a))
    -> (NESeq a -> NESeq (NESeq a)) -> NESeq a -> NESeq (NESeq a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NESeq a -> NESeq (NESeq a)
    forall a. NESeq a -> NESeq (NESeq a)
    inits) Seq a
    ys
    {-# INLINEABLE inits #-}

    -- | \(O \Bigl(\bigl(\frac{n}{c}\bigr) \log c\Bigr)\). @chunksOf c xs@ splits @xs@ into chunks of size @c>0@.
    -- If @c@ does not divide the length of @xs@ evenly, then the last element
    -- of the result will be short.  Is only defined if @c@ is a positive
    -- number.
    --
    -- Side note: the given performance bound is missing some messy terms that only
    -- really affect edge cases. Performance degrades smoothly from \( O(1) \) (for
    -- \( c = n \)) to \( O(n) \) (for \( c = 1 \)). The true bound is more like
    -- \( O \Bigl( \bigl(\frac{n}{c} - 1\bigr) (\log (c + 1)) + 1 \Bigr) \)

    -- TODO: is this true?
    chunksOf :: Int -> NESeq a -> NESeq (NESeq a)
    chunksOf :: forall a. Int -> NESeq a -> NESeq (NESeq a)
    chunksOf Int
    n = NESeq a -> NESeq (NESeq a)
    forall a. NESeq a -> NESeq (NESeq a)
    go
      where
        go :: NESeq a -> NESeq (NESeq a)
    go NESeq a
    xs = case Int -> NESeq a -> These (NESeq a) (NESeq a)
    forall a. Int -> NESeq a -> These (NESeq a) (NESeq a)
    splitAt Int
    n NESeq a
    xs of
          This NESeq a
    ys -> NESeq a -> NESeq (NESeq a)
    forall a. a -> NESeq a
    singleton NESeq a
    ys
          That NESeq a
    _ -> NESeq (NESeq a)
    forall {a}. a
    e
          These NESeq a
    ys NESeq a
    zs -> NESeq a
    ys NESeq a -> NESeq (NESeq a) -> NESeq (NESeq a)
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a -> NESeq (NESeq a)
    go NESeq a
    zs
        e :: a
    e = [Char] -> a
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "chunksOf: A non-empty sequence can only be broken up into positively-sized chunks."
    {-# INLINEABLE chunksOf #-}

    -- | \( O(i) \) where \( i \) is the prefix length. 'takeWhileL', applied
    -- to a predicate @p@ and a sequence @xs@, returns the longest prefix
    -- (possibly empty) of @xs@ of elements that satisfy @p@.
    --
    -- Returns a possibly empty sequence ('Seq') in the case that the predicate
    -- fails on the first item.
    takeWhileL :: (a -> Bool) -> NESeq a -> Seq a
    takeWhileL :: forall a. (a -> Bool) -> NESeq a -> Seq a
    takeWhileL a -> Bool
    p (a
    x :<|| Seq a
    xs)
      | a -> Bool
    p a
    x = a
    x a -> Seq a -> Seq a
    forall a. a -> Seq a -> Seq a
    Seq.<| (a -> Bool) -> Seq a -> Seq a
    forall a. (a -> Bool) -> Seq a -> Seq a
    Seq.takeWhileL a -> Bool
    p Seq a
    xs
      | Bool
    otherwise = Seq a
    forall a. Seq a
    Seq.empty
    {-# INLINE takeWhileL #-}

    -- | \( O(i) \) where \( i \) is the suffix length.  'takeWhileR', applied
    -- to a predicate @p@ and a sequence @xs@, returns the longest suffix
    -- (possibly empty) of @xs@ of elements that satisfy @p@.
    --
    -- Returns a possibly empty sequence ('Seq') in the case that the predicate
    -- fails on the first item.
    --
    -- @'takeWhileR' p xs@ is equivalent to @'reverse' ('takeWhileL' p ('reverse' xs))@.
    takeWhileR :: (a -> Bool) -> NESeq a -> Seq a
    takeWhileR :: forall a. (a -> Bool) -> NESeq a -> Seq a
    takeWhileR a -> Bool
    p (Seq a
    xs :||> a
    x)
      | a -> Bool
    p a
    x = (a -> Bool) -> Seq a -> Seq a
    forall a. (a -> Bool) -> Seq a -> Seq a
    Seq.takeWhileR a -> Bool
    p Seq a
    xs Seq a -> a -> Seq a
    forall a. Seq a -> a -> Seq a
    Seq.|> a
    x
      | Bool
    otherwise = Seq a
    forall a. Seq a
    Seq.empty
    {-# INLINE takeWhileR #-}

    -- | \( O(i) \) where \( i \) is the prefix length.  @'dropWhileL' p xs@ returns
    -- the suffix remaining after @'takeWhileL' p xs@.
    --
    -- Returns a possibly empty sequence ('Seq') in the case that the predicate
    -- passes for all items.
    dropWhileL :: (a -> Bool) -> NESeq a -> Seq a
    dropWhileL :: forall a. (a -> Bool) -> NESeq a -> Seq a
    dropWhileL a -> Bool
    p xs0 :: NESeq a
    xs0@(a
    x :<|| Seq a
    xs)
      | a -> Bool
    p a
    x = (a -> Bool) -> Seq a -> Seq a
    forall a. (a -> Bool) -> Seq a -> Seq a
    Seq.dropWhileL a -> Bool
    p Seq a
    xs
      | Bool
    otherwise = NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq NESeq a
    xs0
    {-# INLINE dropWhileL #-}

    -- | \( O(i) \) where \( i \) is the suffix length.  @'dropWhileR' p xs@ returns
    -- the prefix remaining after @'takeWhileR' p xs@.
    --
    -- Returns a possibly empty sequence ('Seq') in the case that the predicate
    -- passes for all items.
    --
    -- @'dropWhileR' p xs@ is equivalent to @'reverse' ('dropWhileL' p ('reverse' xs))@.
    dropWhileR :: (a -> Bool) -> NESeq a -> Seq a
    dropWhileR :: forall a. (a -> Bool) -> NESeq a -> Seq a
    dropWhileR a -> Bool
    p xs0 :: NESeq a
    xs0@(Seq a
    xs :||> a
    x)
      | a -> Bool
    p a
    x = (a -> Bool) -> Seq a -> Seq a
    forall a. (a -> Bool) -> Seq a -> Seq a
    Seq.dropWhileR a -> Bool
    p Seq a
    xs
      | Bool
    otherwise = NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq NESeq a
    xs0
    {-# INLINE dropWhileR #-}

    -- | \( O(i) \) where \( i \) is the prefix length.  'spanl', applied to
    -- a predicate @p@ and a sequence @xs@, returns a 'These' based on the
    -- point where the predicate fails:
    --
    -- *   @'This' ys@ means that the predicate was true for all items, and
    --     @ys@ is the entire original sequence.
    -- *   @'That' zs@ means that the predicate failed on the first item, and
    --     @zs@ is the entire original sequence.
    -- *   @'These' ys zs@ gives @ys@ (the prefix of elements that satisfy the
    --     predicae) and @zs@ (the remainder of the sequence)
    spanl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanl :: forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanl a -> Bool
    p xs0 :: NESeq a
    xs0@(a
    x :<|| Seq a
    xs)
      | a -> Bool
    p a
    x = case (Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    ys, Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    zs) of
          (Maybe (NESeq a)
    Nothing, Maybe (NESeq a)
    Nothing) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x)
          (Just NESeq a
    _, Maybe (NESeq a)
    Nothing) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This NESeq a
    xs0
          (Maybe (NESeq a)
    Nothing, Just NESeq a
    zs') -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) NESeq a
    zs'
          (Just NESeq a
    ys', Just NESeq a
    zs') -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    ys') NESeq a
    zs'
      | Bool
    otherwise = NESeq a -> These (NESeq a) (NESeq a)
    forall a b. b -> These a b
    That NESeq a
    xs0
      where
        (Seq a
    ys, Seq a
    zs) = (a -> Bool) -> Seq a -> (Seq a, Seq a)
    forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
    Seq.spanl a -> Bool
    p Seq a
    xs
    {-# INLINEABLE spanl #-}

    -- | \( O(i) \) where \( i \) is the suffix length.  'spanr', applied to
    -- a predicate @p@ and a sequence @xs@, returns a 'These' based on the
    -- point where the predicate fails:
    --
    -- *   @'This' ys@ means that the predicate was true for all items, and
    --     @ys@ is the entire original sequence.
    -- *   @'That' zs@ means that the predicate failed on the first item, and
    --     @zs@ is the entire original sequence.
    -- *   @'These' ys zs@ gives @ys@ (the suffix of elements that satisfy the
    --     predicae) and @zs@ (the remainder of the sequence, before the suffix)
    spanr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanr :: forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanr a -> Bool
    p xs0 :: NESeq a
    xs0@(Seq a
    xs :||> a
    x)
      | a -> Bool
    p a
    x = case (Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    ys, Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    zs) of
          (Maybe (NESeq a)
    Nothing, Maybe (NESeq a)
    Nothing) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x)
          (Just NESeq a
    _, Maybe (NESeq a)
    Nothing) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This NESeq a
    xs0
          (Maybe (NESeq a)
    Nothing, Just NESeq a
    zs') -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) NESeq a
    zs'
          (Just NESeq a
    ys', Just NESeq a
    zs') -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (NESeq a
    ys' NESeq a -> a -> NESeq a
    forall a. NESeq a -> a -> NESeq a
    |> a
    x) NESeq a
    zs'
      | Bool
    otherwise = NESeq a -> These (NESeq a) (NESeq a)
    forall a b. b -> These a b
    That NESeq a
    xs0
      where
        (Seq a
    ys, Seq a
    zs) = (a -> Bool) -> Seq a -> (Seq a, Seq a)
    forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
    Seq.spanr a -> Bool
    p Seq a
    xs
    {-# INLINEABLE spanr #-}

    -- | \( O(i) \) where \( i \) is the breakpoint index.
    --
    -- @'breakl' p@ is @'spanl' (not . p)@.
    breakl :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    breakl :: forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    breakl a -> Bool
    p = (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanl (Bool -> Bool
    not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Bool
    p)
    {-# INLINE breakl #-}

    -- | \( O(i) \) where \( i \) is the breakpoint index.
    --
    -- @'breakr' p@ is @'spanr' (not . p)@.
    breakr :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    breakr :: forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    breakr a -> Bool
    p = (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanr (Bool -> Bool
    not (Bool -> Bool) -> (a -> Bool) -> a -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Bool
    p)
    {-# INLINE breakr #-}

    -- | \( O(n) \).  The 'partition' function takes a predicate @p@ and a
    -- sequence @xs@ and returns sequences of those elements which do and
    -- do not satisfy the predicate, as a 'These':
    --
    -- *   @'This' ys@ means that the predicate was true for all items, and
    --     @ys@ is the entire original sequence.
    -- *   @'That' zs@ means that the predicate failed on the first item, and
    --     @zs@ is the entire original sequence.
    -- *   @'These' ys zs@ gives @ys@ (the sequence of elements for which the
    --     predicate was true) and @zs@ (the sequence of elements for which the
    --     predicate was false).
    partition :: (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    partition :: forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    partition a -> Bool
    p xs0 :: NESeq a
    xs0@(a
    x :<|| Seq a
    xs) = case (Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    ys, Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    zs) of
      (Maybe (NESeq a)
    Nothing, Maybe (NESeq a)
    Nothing)
        | a -> Bool
    p a
    x -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x)
        | Bool
    otherwise -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. b -> These a b
    That (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x)
      (Just NESeq a
    ys', Maybe (NESeq a)
    Nothing)
        | a -> Bool
    p a
    x -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This NESeq a
    xs0
        | Bool
    otherwise -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These NESeq a
    ys' (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x)
      (Maybe (NESeq a)
    Nothing, Just NESeq a
    zs')
        | a -> Bool
    p a
    x -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) NESeq a
    zs'
        | Bool
    otherwise -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. b -> These a b
    That NESeq a
    xs0
      (Just NESeq a
    ys', Just NESeq a
    zs')
        | a -> Bool
    p a
    x -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    ys') NESeq a
    zs'
        | Bool
    otherwise -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These NESeq a
    ys' (a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    zs')
      where
        (Seq a
    ys, Seq a
    zs) = (a -> Bool) -> Seq a -> (Seq a, Seq a)
    forall a. (a -> Bool) -> Seq a -> (Seq a, Seq a)
    Seq.partition a -> Bool
    p Seq a
    xs
    {-# INLINEABLE partition #-}

    -- | \( O(n) \).  The 'filter' function takes a predicate @p@ and a sequence
    -- @xs@ and returns a sequence of those elements which satisfy the
    -- predicate.
    --
    -- Returns a potentially empty sequence ('Seq') in the case that the
    -- predicate fails for all items in the sequence.
    filter :: (a -> Bool) -> NESeq a -> Seq a
    filter :: forall a. (a -> Bool) -> NESeq a -> Seq a
    filter a -> Bool
    p (a
    x :<|| Seq a
    xs)
      | a -> Bool
    p a
    x = a
    x a -> Seq a -> Seq a
    forall a. a -> Seq a -> Seq a
    Seq.<| (a -> Bool) -> Seq a -> Seq a
    forall a. (a -> Bool) -> Seq a -> Seq a
    Seq.filter a -> Bool
    p Seq a
    xs
      | Bool
    otherwise = (a -> Bool) -> Seq a -> Seq a
    forall a. (a -> Bool) -> Seq a -> Seq a
    Seq.filter a -> Bool
    p Seq a
    xs
    {-# INLINE filter #-}

    -- | \( O(n \log n) \).  'sort' sorts the specified 'NESeq' by the natural
    -- ordering of its elements.  The sort is stable.  If stability is not
    -- required, 'unstableSort' can be slightly faster.
    sort :: Ord a => NESeq a -> NESeq a
    sort :: forall a. Ord a => NESeq a -> NESeq a
    sort = (a -> a -> Ordering) -> NESeq a -> NESeq a
    forall a. (a -> a -> Ordering) -> NESeq a -> NESeq a
    sortBy a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare
    {-# INLINE sort #-}

    -- | \( O(n \log n) \).  'sortBy' sorts the specified 'NESeq' according to
    -- the specified comparator.  The sort is stable.  If stability is not
    -- required, 'unstableSortBy' can be slightly faster.

    -- TODO: benchmark against just unsafe unwrapping and wrapping
    sortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a
    sortBy :: forall a. (a -> a -> Ordering) -> NESeq a -> NESeq a
    sortBy a -> a -> Ordering
    c (a
    x :<|| Seq a
    xs) =
      NESeq a -> (NESeq a -> NESeq a) -> Seq a -> NESeq a
    forall r a. r -> (NESeq a -> r) -> Seq a -> r
    withNonEmpty (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) ((a -> a -> Ordering) -> a -> NESeq a -> NESeq a
    forall a. (a -> a -> Ordering) -> a -> NESeq a -> NESeq a
    insertBy a -> a -> Ordering
    c a
    x)
        (Seq a -> NESeq a) -> (Seq a -> Seq a) -> Seq a -> NESeq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> Ordering) -> Seq a -> Seq a
    forall a. (a -> a -> Ordering) -> Seq a -> Seq a
    Seq.sortBy a -> a -> Ordering
    c
        (Seq a -> NESeq a) -> Seq a -> NESeq a
    forall a b. (a -> b) -> a -> b
    $ Seq a
    xs
    {-# INLINE sortBy #-}

    -- | \( O(n \log n) \). 'sortOn' sorts the specified 'NESeq' by comparing
    -- the results of a key function applied to each element. @'sortOn' f@ is
    -- equivalent to @'sortBy' ('compare' ``Data.Function.on`` f)@, but has the
    -- performance advantage of only evaluating @f@ once for each element in
    -- the input list. This is called the decorate-sort-undecorate paradigm, or
    -- Schwartzian transform.
    --
    -- An example of using 'sortOn' might be to sort a 'NESeq' of strings
    -- according to their length:
    --
    -- > sortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator"])
    --
    -- If, instead, 'sortBy' had been used, 'length' would be evaluated on
    -- every comparison, giving \( O(n \log n) \) evaluations, rather than
    -- \( O(n) \).
    --
    -- If @f@ is very cheap (for example a record selector, or 'fst'),
    -- @'sortBy' ('compare' ``Data.Function.on`` f)@ will be faster than
    -- @'sortOn' f@.

    -- TODO: benchmark against just unsafe unwrapping and wrapping
    sortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a
    sortOn :: forall b a. Ord b => (a -> b) -> NESeq a -> NESeq a
    sortOn a -> b
    f (a
    x :<|| Seq a
    xs) =
      NESeq a -> (NESeq a -> NESeq a) -> Seq a -> NESeq a
    forall r a. r -> (NESeq a -> r) -> Seq a -> r
    withNonEmpty (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) ((a -> b) -> a -> NESeq a -> NESeq a
    forall b a. Ord b => (a -> b) -> a -> NESeq a -> NESeq a
    insertOn a -> b
    f a
    x)
        (Seq a -> NESeq a) -> (Seq a -> Seq a) -> Seq a -> NESeq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> b) -> Seq a -> Seq a
    forall b a. Ord b => (a -> b) -> Seq a -> Seq a
    Seq.sortOn a -> b
    f
        (Seq a -> NESeq a) -> Seq a -> NESeq a
    forall a b. (a -> b) -> a -> b
    $ Seq a
    xs
    {-# INLINE sortOn #-}

    -- | \( O(n \log n) \).  'unstableSort' sorts the specified 'NESeq' by the
    -- natural ordering of its elements, but the sort is not stable.  This
    -- algorithm is frequently faster and uses less memory than 'sort'.
    unstableSort :: Ord a => NESeq a -> NESeq a
    unstableSort :: forall a. Ord a => NESeq a -> NESeq a
    unstableSort = (a -> a -> Ordering) -> NESeq a -> NESeq a
    forall a. (a -> a -> Ordering) -> NESeq a -> NESeq a
    unstableSortBy a -> a -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare
    {-# INLINE unstableSort #-}

    -- | \( O(n \log n) \).  A generalization of 'unstableSort',
    -- 'unstableSortBy' takes an arbitrary comparator and sorts the specified
    -- sequence.  The sort is not stable.  This algorithm is frequently faster
    -- and uses less memory than 'sortBy'.

    -- TODO: figure out how to make it match 'Data.Sequence.unstableSortBy'
    -- without unsafe wrapping/unwrapping
    unstableSortBy :: (a -> a -> Ordering) -> NESeq a -> NESeq a
    unstableSortBy :: forall a. (a -> a -> Ordering) -> NESeq a -> NESeq a
    unstableSortBy a -> a -> Ordering
    c = Seq a -> NESeq a
    forall a. Seq a -> NESeq a
    unsafeFromSeq (Seq a -> NESeq a) -> (NESeq a -> Seq a) -> NESeq a -> NESeq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> a -> Ordering) -> Seq a -> Seq a
    forall a. (a -> a -> Ordering) -> Seq a -> Seq a
    Seq.unstableSortBy a -> a -> Ordering
    c (Seq a -> Seq a) -> (NESeq a -> Seq a) -> NESeq a -> Seq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq
    -- unstableSortBy c (x :<|| xs) = withNonEmpty (singleton x) (insertBy c x)
    --                      . Seq.unstableSortBy c
    --                      $ xs
    {-# INLINE unstableSortBy #-}

    -- | \( O(n \log n) \). 'unstableSortOn' sorts the specified 'NESeq' by
    -- comparing the results of a key function applied to each element.
    -- @'unstableSortOn' f@ is equivalent to @'unstableSortBy' ('compare' ``Data.Function.on`` f)@,
    -- but has the performance advantage of only evaluating @f@ once for each
    -- element in the input list. This is called the
    -- decorate-sort-undecorate paradigm, or Schwartzian transform.
    --
    -- An example of using 'unstableSortOn' might be to sort a 'NESeq' of strings
    -- according to their length.
    --
    -- > unstableSortOn length (fromList ("alligator" :| ["monkey", "zebra"])) == fromList ("zebra" :| ["monkey", "alligator]")
    --
    -- If, instead, 'unstableSortBy' had been used, 'length' would be evaluated on
    -- every comparison, giving \( O(n \log n) \) evaluations, rather than
    -- \( O(n) \).
    --
    -- If @f@ is very cheap (for example a record selector, or 'fst'),
    -- @'unstableSortBy' ('compare' ``Data.Function.on`` f)@ will be faster than
    -- @'unstableSortOn' f@.

    -- TODO: figure out how to make it match 'Data.Sequence.unstableSortBy'
    -- without unsafe wrapping/unwrapping
    unstableSortOn :: Ord b => (a -> b) -> NESeq a -> NESeq a
    unstableSortOn :: forall b a. Ord b => (a -> b) -> NESeq a -> NESeq a
    unstableSortOn a -> b
    f = Seq a -> NESeq a
    forall a. Seq a -> NESeq a
    unsafeFromSeq (Seq a -> NESeq a) -> (NESeq a -> Seq a) -> NESeq a -> NESeq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> b) -> Seq a -> Seq a
    forall b a. Ord b => (a -> b) -> Seq a -> Seq a
    Seq.unstableSortOn a -> b
    f (Seq a -> Seq a) -> (NESeq a -> Seq a) -> NESeq a -> Seq a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq
    -- unstableSortOn f (x :<|| xs) = withNonEmpty (singleton x) (insertOn f x)
    --                              . Seq.unstableSortOn f
    --                              $ xs
    {-# INLINE unstableSortOn #-}

    insertBy :: (a -> a -> Ordering) -> a -> NESeq a -> NESeq a
    insertBy :: forall a. (a -> a -> Ordering) -> a -> NESeq a -> NESeq a
    insertBy a -> a -> Ordering
    c a
    x NESeq a
    xs = case (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanl a -> Bool
    ltx NESeq a
    xs of
      This NESeq a
    ys -> NESeq a
    ys NESeq a -> a -> NESeq a
    forall a. NESeq a -> a -> NESeq a
    |> a
    x
      That NESeq a
    zs -> a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    zs
      These NESeq a
    ys NESeq a
    zs -> NESeq a
    ys NESeq a -> NESeq a -> NESeq a
    forall a. NESeq a -> NESeq a -> NESeq a
    >< (a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    zs)
      where
        ltx :: a -> Bool
    ltx a
    y = a -> a -> Ordering
    c a
    x a
    y Ordering -> Ordering -> Bool
    forall a. Eq a => a -> a -> Bool
    == Ordering
    GT
    {-# INLINEABLE insertBy #-}

    insertOn :: Ord b => (a -> b) -> a -> NESeq a -> NESeq a
    insertOn :: forall b a. Ord b => (a -> b) -> a -> NESeq a -> NESeq a
    insertOn a -> b
    f a
    x NESeq a
    xs = case (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a. (a -> Bool) -> NESeq a -> These (NESeq a) (NESeq a)
    spanl a -> Bool
    ltx NESeq a
    xs of
      This NESeq a
    ys -> NESeq a
    ys NESeq a -> a -> NESeq a
    forall a. NESeq a -> a -> NESeq a
    |> a
    x
      That NESeq a
    zs -> a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    zs
      These NESeq a
    ys NESeq a
    zs -> NESeq a
    ys NESeq a -> NESeq a -> NESeq a
    forall a. NESeq a -> NESeq a -> NESeq a
    >< (a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    zs)
      where
        fx :: b
    fx = a -> b
    f a
    x
        ltx :: a -> Bool
    ltx a
    y = b
    fx b -> b -> Bool
    forall a. Ord a => a -> a -> Bool
    > a -> b
    f a
    y
    {-# INLINEABLE insertOn #-}

    -- | \( O(\log(\min(i,n-i))) \). The element at the specified position,
    -- counting from 0. If the specified position is negative or at
    -- least the length of the sequence, 'lookup' returns 'Nothing'.
    --
    -- Unlike 'index', this can be used to retrieve an element without
    -- forcing it.
    lookup :: Int -> NESeq a -> Maybe a
    lookup :: forall a. Int -> NESeq a -> Maybe a
    lookup Int
    0 (a
    x :<|| Seq a
    _) = a -> Maybe a
    forall a. a -> Maybe a
    Just a
    x
    lookup Int
    i (a
    _ :<|| Seq a
    xs) = Int -> Seq a -> Maybe a
    forall a. Int -> Seq a -> Maybe a
    Seq.lookup (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
    {-# INLINE lookup #-}

    -- | \( O(\log(\min(i,n-i))) \). A flipped, infix version of `lookup`.
    (!?) :: NESeq a -> Int -> Maybe a
    !? :: forall a. NESeq a -> Int -> Maybe a
    (!?) = (Int -> NESeq a -> Maybe a) -> NESeq a -> Int -> Maybe a
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip Int -> NESeq a -> Maybe a
    forall a. Int -> NESeq a -> Maybe a
    lookup
    {-# INLINE (!?) #-}

    -- | \( O(\log(\min(i,n-i))) \). Update the element at the specified position.  If
    -- the position is out of range, the original sequence is returned.  'adjust'
    -- can lead to poor performance and even memory leaks, because it does not
    -- force the new value before installing it in the sequence. 'adjust'' should
    -- usually be preferred.
    adjust :: (a -> a) -> Int -> NESeq a -> NESeq a
    adjust :: forall a. (a -> a) -> Int -> NESeq a -> NESeq a
    adjust a -> a
    f Int
    0 (a
    x :<|| Seq a
    xs) = a -> a
    f a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a
    xs
    adjust a -> a
    f Int
    i (a
    x :<|| Seq a
    xs) = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| (a -> a) -> Int -> Seq a -> Seq a
    forall a. (a -> a) -> Int -> Seq a -> Seq a
    Seq.adjust a -> a
    f (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
    {-# INLINE adjust #-}

    -- | \( O(\log(\min(i,n-i))) \). Update the element at the specified position.
    -- If the position is out of range, the original sequence is returned.
    -- The new value is forced before it is installed in the sequence.
    --
    -- @
    -- adjust' f i xs =
    --  case xs !? i of
    --    Nothing -> xs
    --    Just x -> let !x' = f x
    --              in update i x' xs
    -- @
    adjust' :: (a -> a) -> Int -> NESeq a -> NESeq a
    adjust' :: forall a. (a -> a) -> Int -> NESeq a -> NESeq a
    adjust' a -> a
    f Int
    0 (a
    x :<|| Seq a
    xs) = let !y :: a
    y = a -> a
    f a
    x in a
    y a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a
    xs
    adjust' a -> a
    f Int
    i (a
    x :<|| Seq a
    xs) = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| (a -> a) -> Int -> Seq a -> Seq a
    forall a. (a -> a) -> Int -> Seq a -> Seq a
    Seq.adjust a -> a
    f (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
    {-# INLINE adjust' #-}

    -- | \( O(\log(\min(i,n-i))) \). Replace the element at the specified position.
    -- If the position is out of range, the original sequence is returned.
    update :: Int -> a -> NESeq a -> NESeq a
    update :: forall a. Int -> a -> NESeq a -> NESeq a
    update Int
    0 a
    y (a
    _ :<|| Seq a
    xs) = a
    y a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a
    xs
    update Int
    i a
    y (a
    x :<|| Seq a
    xs) = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Int -> a -> Seq a -> Seq a
    forall a. Int -> a -> Seq a -> Seq a
    Seq.update (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) a
    y Seq a
    xs
    {-# INLINE update #-}

    -- | \( O(\log(\min(i,n-i))) \). The first @i@ elements of a sequence.
    -- If @i@ is negative, @'take' i s@ yields the empty sequence.
    -- If the sequence contains fewer than @i@ elements, the whole sequence
    -- is returned.
    take :: Int -> NESeq a -> Seq a
    take :: forall a. Int -> NESeq a -> Seq a
    take Int
    i (a
    x :<|| Seq a
    xs)
      | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = Seq a
    forall a. Seq a
    Seq.empty
      | Bool
    otherwise = a
    x a -> Seq a -> Seq a
    forall a. a -> Seq a -> Seq a
    Seq.<| Int -> Seq a -> Seq a
    forall a. Int -> Seq a -> Seq a
    Seq.take (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
    {-# INLINE take #-}

    -- | \( O(\log(\min(i,n-i))) \). Elements of a sequence after the first @i@.
    -- If @i@ is negative, @'drop' i s@ yields the whole sequence.
    -- If the sequence contains fewer than @i@ elements, the empty sequence
    -- is returned.
    drop :: Int -> NESeq a -> Seq a
    drop :: forall a. Int -> NESeq a -> Seq a
    drop Int
    i xs0 :: NESeq a
    xs0@(a
    _ :<|| Seq a
    xs)
      | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq NESeq a
    xs0
      | Bool
    otherwise = Int -> Seq a -> Seq a
    forall a. Int -> Seq a -> Seq a
    Seq.drop (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
    {-# INLINE drop #-}

    -- | \( O(\log(\min(i,n-i))) \). @'insertAt' i x xs@ inserts @x@ into @xs@
    -- at the index @i@, shifting the rest of the sequence over.
    --
    -- @
    -- insertAt 2 x (fromList (a:|[b,c,d])) = fromList (a:|[b,x,c,d])
    -- insertAt 4 x (fromList (a:|[b,c,d])) = insertAt 10 x (fromList (a:|[b,c,d]))
    --                                      = fromList (a:|[b,c,d,x])
    -- @
    --
    -- prop> insertAt i x xs = take i xs >< singleton x >< drop i xs
    insertAt :: Int -> a -> NESeq a -> NESeq a
    insertAt :: forall a. Int -> a -> NESeq a -> NESeq a
    insertAt Int
    i a
    y xs0 :: NESeq a
    xs0@(a
    x :<|| Seq a
    xs)
      | Int
    i Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = a
    y a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    xs0
      | Bool
    otherwise = a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| Int -> a -> Seq a -> Seq a
    forall a. Int -> a -> Seq a -> Seq a
    Seq.insertAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) a
    y Seq a
    xs
    {-# INLINE insertAt #-}

    -- | \( O(\log(\min(i,n-i))) \). Delete the element of a sequence at a given
    -- index. Return the original sequence if the index is out of range.
    --
    -- @
    -- deleteAt 2 (a:|[b,c,d]) = a:|[b,d]
    -- deleteAt 4 (a:|[b,c,d]) = deleteAt (-1) (a:|[b,c,d]) = a:|[b,c,d]
    -- @
    deleteAt :: Int -> NESeq a -> Seq a
    deleteAt :: forall a. Int -> NESeq a -> Seq a
    deleteAt Int
    i xs0 :: NESeq a
    xs0@(a
    x :<|| Seq a
    xs) = case Int -> Int -> Ordering
    forall a. Ord a => a -> a -> Ordering
    compare Int
    i Int
    0 of
      Ordering
    LT -> NESeq a -> Seq a
    forall a. NESeq a -> Seq a
    toSeq NESeq a
    xs0
      Ordering
    EQ -> Seq a
    xs
      Ordering
    GT -> a
    x a -> Seq a -> Seq a
    forall a. a -> Seq a -> Seq a
    Seq.<| Int -> Seq a -> Seq a
    forall a. Int -> Seq a -> Seq a
    Seq.deleteAt (Int
    i Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
    {-# INLINE deleteAt #-}

    -- | \( O(\log(\min(i,n-i))) \). Split a sequence at a given position.
    --
    -- *   @'This' ys@ means that the given position was longer than the length
    --     of the list, and @ys@ is the entire original system.
    -- *   @'That' zs@ means that the given position was zero or smaller, and
    --     so @zs@ is the entire original sequence.
    -- *   @'These' ys zs@ gives @ys@ (the sequence of elements before the
    --     given position, @take n xs@) and @zs@ (the sequence of elements
    --     after the given position, @drop n xs@).
    splitAt :: Int -> NESeq a -> These (NESeq a) (NESeq a)
    splitAt :: forall a. Int -> NESeq a -> These (NESeq a) (NESeq a)
    splitAt Int
    n xs0 :: NESeq a
    xs0@(a
    x :<|| Seq a
    xs)
      | Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    <= Int
    0 = NESeq a -> These (NESeq a) (NESeq a)
    forall a b. b -> These a b
    That NESeq a
    xs0
      | Bool
    otherwise = case (Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    ys, Seq a -> Maybe (NESeq a)
    forall a. Seq a -> Maybe (NESeq a)
    nonEmptySeq Seq a
    zs) of
          (Maybe (NESeq a)
    Nothing, Maybe (NESeq a)
    Nothing) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x)
          (Just NESeq a
    _, Maybe (NESeq a)
    Nothing) -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> These a b
    This NESeq a
    xs0
          (Maybe (NESeq a)
    Nothing, Just NESeq a
    zs') -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (a -> NESeq a
    forall a. a -> NESeq a
    singleton a
    x) NESeq a
    zs'
          (Just NESeq a
    ys', Just NESeq a
    zs') -> NESeq a -> NESeq a -> These (NESeq a) (NESeq a)
    forall a b. a -> b -> These a b
    These (a
    x a -> NESeq a -> NESeq a
    forall a. a -> NESeq a -> NESeq a
    <| NESeq a
    ys') NESeq a
    zs'
      where
        (Seq a
    ys, Seq a
    zs) = Int -> Seq a -> (Seq a, Seq a)
    forall a. Int -> Seq a -> (Seq a, Seq a)
    Seq.splitAt (Int
    n Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) Seq a
    xs
    {-# INLINEABLE splitAt #-}

    -- | 'elemIndexL' finds the leftmost index of the specified element,
    -- if it is present, and otherwise 'Nothing'.
    elemIndexL :: Eq a => a -> NESeq a -> Maybe Int
    elemIndexL :: forall a. Eq a => a -> NESeq a -> Maybe Int
    elemIndexL a
    x = (a -> Bool) -> NESeq a -> Maybe Int
    forall a. (a -> Bool) -> NESeq a -> Maybe Int
    findIndexL (a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    x)
    {-# INLINE elemIndexL #-}

    -- | 'elemIndexR' finds the rightmost index of the specified element,
    -- if it is present, and otherwise 'Nothing'.
    elemIndexR :: Eq a => a -> NESeq a -> Maybe Int
    elemIndexR :: forall a. Eq a => a -> NESeq a -> Maybe Int
    elemIndexR a
    x = (a -> Bool) -> NESeq a -> Maybe Int
    forall a. (a -> Bool) -> NESeq a -> Maybe Int
    findIndexR (a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    x)
    {-# INLINE elemIndexR #-}

    -- | 'elemIndicesL' finds the indices of the specified element, from
    -- left to right (i.e. in ascending order).
    elemIndicesL :: Eq a => a -> NESeq a -> [Int]
    elemIndicesL :: forall a. Eq a => a -> NESeq a -> [Int]
    elemIndicesL a
    x = (a -> Bool) -> NESeq a -> [Int]
    forall a. (a -> Bool) -> NESeq a -> [Int]
    findIndicesL (a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    x)
    {-# INLINE elemIndicesL #-}

    -- | 'elemIndicesR' finds the indices of the specified element, from
    -- right to left (i.e. in descending order).
    elemIndicesR :: Eq a => a -> NESeq a -> [Int]
    elemIndicesR :: forall a. Eq a => a -> NESeq a -> [Int]
    elemIndicesR a
    x = (a -> Bool) -> NESeq a -> [Int]
    forall a. (a -> Bool) -> NESeq a -> [Int]
    findIndicesR (a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    x)
    {-# INLINE elemIndicesR #-}

    -- | @'findIndexL' p xs@ finds the index of the leftmost element that
    -- satisfies @p@, if any exist.
    findIndexL :: (a -> Bool) -> NESeq a -> Maybe Int
    findIndexL :: forall a. (a -> Bool) -> NESeq a -> Maybe Int
    findIndexL a -> Bool
    p (a
    x :<|| Seq a
    xs) = Maybe Int
    here_ Maybe Int -> Maybe Int -> Maybe Int
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> Maybe Int
    there_
      where
        here_ :: Maybe Int
    here_ = Int
    0 Int -> Maybe () -> Maybe Int
    forall a b. a -> Maybe b -> Maybe a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$ Bool -> Maybe ()
    forall (f :: * -> *). Alternative f => Bool -> f ()
    guard (a -> Bool
    p a
    x)
        there_ :: Maybe Int
    there_ = (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
    <$> (a -> Bool) -> Seq a -> Maybe Int
    forall a. (a -> Bool) -> Seq a -> Maybe Int
    Seq.findIndexL a -> Bool
    p Seq a
    xs
    {-# INLINE findIndexL #-}

    -- | @'findIndexR' p xs@ finds the index of the rightmost element that
    -- satisfies @p@, if any exist.
    findIndexR :: (a -> Bool) -> NESeq a -> Maybe Int
    findIndexR :: forall a. (a -> Bool) -> NESeq a -> Maybe Int
    findIndexR a -> Bool
    p (Seq a
    xs :||> a
    x) = Maybe Int
    here_ Maybe Int -> Maybe Int -> Maybe Int
    forall a. Maybe a -> Maybe a -> Maybe a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> Maybe Int
    there_
      where
        here_ :: Maybe Int
    here_ = Seq a -> Int
    forall a. Seq a -> Int
    Seq.length Seq a
    xs Int -> Maybe () -> Maybe Int
    forall a b. a -> Maybe b -> Maybe a
    forall (f :: * -> *) a b. Functor f => a -> f b -> f a
    <$ Bool -> Maybe ()
    forall (f :: * -> *). Alternative f => Bool -> f ()
    guard (a -> Bool
    p a
    x)
        there_ :: Maybe Int
    there_ = (a -> Bool) -> Seq a -> Maybe Int
    forall a. (a -> Bool) -> Seq a -> Maybe Int
    Seq.findIndexR a -> Bool
    p Seq a
    xs
    {-# INLINE findIndexR #-}

    -- | @'findIndicesL' p@ finds all indices of elements that satisfy @p@,
    -- in ascending order.

    -- TODO: use build
    findIndicesL :: (a -> Bool) -> NESeq a -> [Int]
    findIndicesL :: forall a. (a -> Bool) -> NESeq a -> [Int]
    findIndicesL a -> Bool
    p (a
    x :<|| Seq a
    xs)
      | a -> Bool
    p a
    x = Int
    0 Int -> [Int] -> [Int]
    forall a. a -> [a] -> [a]
    : [Int]
    ixs
      | Bool
    otherwise = [Int]
    ixs
      where
        ixs :: [Int]
    ixs = (Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1) (Int -> Int) -> [Int] -> [Int]
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> (a -> Bool) -> Seq a -> [Int]
    forall a. (a -> Bool) -> Seq a -> [Int]
    Seq.findIndicesL a -> Bool
    p Seq a
    xs
    {-# INLINE findIndicesL #-}

    -- | @'findIndicesR' p@ finds all indices of elements that satisfy @p@,
    -- in descending order.

    -- TODO: use build
    findIndicesR :: (a -> Bool) -> NESeq a -> [Int]
    findIndicesR :: forall a. (a -> Bool) -> NESeq a -> [Int]
    findIndicesR a -> Bool
    p (Seq a
    xs :||> a
    x)
      | a -> Bool
    p a
    x = Seq a -> Int
    forall a. Seq a -> Int
    Seq.length Seq a
    xs Int -> [Int] -> [Int]
    forall a. a -> [a] -> [a]
    : [Int]
    ixs
      | Bool
    otherwise = [Int]
    ixs
      where
        ixs :: [Int]
    ixs = (a -> Bool) -> Seq a -> [Int]
    forall a. (a -> Bool) -> Seq a -> [Int]
    Seq.findIndicesR a -> Bool
    p Seq a
    xs
    {-# INLINE findIndicesR #-}

    -- | 'foldlWithIndex' is a version of 'foldl' that also provides access
    -- to the index of each element.
    foldlWithIndex :: (b -> Int -> a -> b) -> b -> NESeq a -> b
    foldlWithIndex :: forall b a. (b -> Int -> a -> b) -> b -> NESeq a -> b
    foldlWithIndex b -> Int -> a -> b
    f b
    z (Seq a
    xs :||> a
    x) = (\b
    z' -> b -> Int -> a -> b
    f b
    z' (Seq a -> Int
    forall a. Seq a -> Int
    Seq.length Seq a
    xs) a
    x) (b -> b) -> (Seq a -> b) -> Seq a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (b -> Int -> a -> b) -> b -> Seq a -> b
    forall b a. (b -> Int -> a -> b) -> b -> Seq a -> b
    Seq.foldlWithIndex b -> Int -> a -> b
    f b
    z (Seq a -> b) -> Seq a -> b
    forall a b. (a -> b) -> a -> b
    $ Seq a
    xs
    {-# INLINE foldlWithIndex #-}

    -- | 'foldrWithIndex' is a version of 'foldr' that also provides access
    -- to the index of each element.
    foldrWithIndex :: (Int -> a -> b -> b) -> b -> NESeq a -> b
    foldrWithIndex :: forall a b. (Int -> a -> b -> b) -> b -> NESeq a -> b
    foldrWithIndex Int -> a -> b -> b
    f b
    z (a
    x :<|| Seq a
    xs) = Int -> a -> b -> b
    f Int
    0 a
    x (b -> b) -> (Seq a -> b) -> Seq a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> a -> b -> b) -> b -> Seq a -> b
    forall a b. (Int -> a -> b -> b) -> b -> Seq a -> b
    Seq.foldrWithIndex (Int -> a -> b -> b
    f (Int -> a -> b -> b) -> (Int -> Int) -> Int -> a -> b -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1)) b
    z (Seq a -> b) -> Seq a -> b
    forall a b. (a -> b) -> a -> b
    $ Seq a
    xs
    {-# INLINE foldrWithIndex #-}

    -- | A generalization of 'fmap', 'mapWithIndex' takes a mapping
    -- function that also depends on the element's index, and applies it to every
    -- element in the sequence.
    mapWithIndex :: (Int -> a -> b) -> NESeq a -> NESeq b
    mapWithIndex :: forall a b. (Int -> a -> b) -> NESeq a -> NESeq b
    mapWithIndex Int -> a -> b
    f (a
    x :<|| Seq a
    xs) = Int -> a -> b
    f Int
    0 a
    x b -> Seq b -> NESeq b
    forall a. a -> Seq a -> NESeq a
    :<|| (Int -> a -> b) -> Seq a -> Seq b
    forall a b. (Int -> a -> b) -> Seq a -> Seq b
    Seq.mapWithIndex (Int -> a -> b
    f (Int -> a -> b) -> (Int -> Int) -> Int -> a -> b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1)) Seq a
    xs
    {-# NOINLINE [1] mapWithIndex #-}

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

    -- | 'traverseWithIndex' is a version of 'traverse' that also offers
    -- access to the index of each element.
    --
    -- Is a more restrictive version of 'traverseWithIndex1';
    -- 'traverseWithIndex1' should be used whenever possible.
    traverseWithIndex :: Applicative f => (Int -> a -> f b) -> NESeq a -> f (NESeq b)
    traverseWithIndex :: forall (f :: * -> *) a b.
    Applicative f =>
    (Int -> a -> f b) -> NESeq a -> f (NESeq b)
    traverseWithIndex Int -> a -> f b
    f (a
    x :<|| Seq a
    xs) = b -> Seq b -> NESeq b
    forall a. a -> Seq a -> NESeq a
    (:<||) (b -> Seq b -> NESeq b) -> f b -> f (Seq b -> NESeq b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Int -> a -> f b
    f Int
    0 a
    x f (Seq b -> NESeq b) -> f (Seq b) -> f (NESeq b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> (Int -> a -> f b) -> Seq a -> f (Seq b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (Int -> a -> f b) -> Seq a -> f (Seq b)
    Seq.traverseWithIndex (Int -> a -> f b
    f (Int -> a -> f b) -> (Int -> Int) -> Int -> a -> f b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int -> Int -> Int
    forall a. Num a => a -> a -> a
    + Int
    1)) Seq a
    xs
    {-# NOINLINE [1] traverseWithIndex #-}

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

    -- | \( O(n) \). The reverse of a sequence.
    reverse :: NESeq a -> NESeq a
    reverse :: forall a. NESeq a -> NESeq a
    reverse (a
    x :<|| Seq a
    xs) = Seq a -> Seq a
    forall a. Seq a -> Seq a
    Seq.reverse Seq a
    xs Seq a -> a -> NESeq a
    forall a. Seq a -> a -> NESeq a
    :||> a
    x
    {-# NOINLINE [1] reverse #-}

    -- | \( O(n) \). Reverse a sequence while mapping over it. This is not
    -- currently exported, but is used in rewrite rules.
    mapReverse :: (a -> b) -> NESeq a -> NESeq b
    mapReverse :: forall a b. (a -> b) -> NESeq a -> NESeq b
    mapReverse a -> b
    f (a
    x :<|| Seq a
    xs) = (a -> b) -> Seq a -> Seq b
    forall a b. (a -> b) -> Seq a -> Seq b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> b
    f (Seq a -> Seq a
    forall a. Seq a -> Seq a
    Seq.reverse Seq a
    xs) Seq b -> b -> NESeq b
    forall a. Seq a -> a -> NESeq a
    :||> a -> b
    f a
    x

    {-# RULES
    "map/reverse" forall f xs. map f (reverse xs) = mapReverse f xs
    "reverse/map" forall f xs. reverse (map f xs) = mapReverse f xs
      #-}

    -- | \( O(n) \). Intersperse an element between the elements of a sequence.
    --
    -- @
    -- intersperse a empty = empty
    -- intersperse a (singleton x) = singleton x
    -- intersperse a (fromList [x,y]) = fromList [x,a,y]
    -- intersperse a (fromList [x,y,z]) = fromList [x,a,y,a,z]
    -- @
    intersperse :: a -> NESeq a -> NESeq a
    intersperse :: forall a. a -> NESeq a -> NESeq a
    intersperse a
    z nes :: NESeq a
    nes@(a
    x :<|| Seq a
    xs) = case Seq a
    xs of
      a
    _ Seq.:<| Seq a
    _ -> a
    x a -> Seq a -> NESeq a
    forall a. a -> Seq a -> NESeq a
    :<|| (a
    z a -> Seq a -> Seq a
    forall a. a -> Seq a -> Seq a
    Seq.<| a -> Seq a -> Seq a
    forall a. a -> Seq a -> Seq a
    Seq.intersperse a
    z Seq a
    xs)
      Seq a
    Seq.Empty -> NESeq a
    nes
    {-# INLINE intersperse #-}

    -- | \( O(\min(n_1,n_2,n_3)) \).  'zip3' takes three sequences and returns a
    -- sequence of triples, analogous to 'zip'.
    zip3 :: NESeq a -> NESeq b -> NESeq c -> NESeq (a, b, c)
    zip3 :: forall a b c. NESeq a -> NESeq b -> NESeq c -> NESeq (a, b, c)
    zip3 (a
    x :<|| Seq a
    xs) (b
    y :<|| Seq b
    ys) (c
    z :<|| Seq c
    zs) = (a
    x, b
    y, c
    z) (a, b, c) -> Seq (a, b, c) -> NESeq (a, b, c)
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a -> Seq b -> Seq c -> Seq (a, b, c)
    forall a b c. Seq a -> Seq b -> Seq c -> Seq (a, b, c)
    Seq.zip3 Seq a
    xs Seq b
    ys Seq c
    zs
    {-# INLINE zip3 #-}

    -- | \( O(\min(n_1,n_2,n_3)) \).  'zipWith3' takes a function which combines
    -- three elements, as well as three sequences and returns a sequence of
    -- their point-wise combinations, analogous to 'zipWith'.
    zipWith3 :: (a -> b -> c -> d) -> NESeq a -> NESeq b -> NESeq c -> NESeq d
    zipWith3 :: forall a b c d.
    (a -> b -> c -> d) -> NESeq a -> NESeq b -> NESeq c -> NESeq d
    zipWith3 a -> b -> c -> d
    f (a
    x :<|| Seq a
    xs) (b
    y :<|| Seq b
    ys) (c
    z :<|| Seq c
    zs) = a -> b -> c -> d
    f a
    x b
    y c
    z d -> Seq d -> NESeq d
    forall a. a -> Seq a -> NESeq a
    :<|| (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
    forall a b c d.
    (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
    Seq.zipWith3 a -> b -> c -> d
    f Seq a
    xs Seq b
    ys Seq c
    zs
    {-# INLINE zipWith3 #-}

    -- | \( O(\min(n_1,n_2,n_3,n_4)) \).  'zip4' takes four sequences and returns a
    -- sequence of quadruples, analogous to 'zip'.
    zip4 :: NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq (a, b, c, d)
    zip4 :: forall a b c d.
    NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq (a, b, c, d)
    zip4 (a
    x :<|| Seq a
    xs) (b
    y :<|| Seq b
    ys) (c
    z :<|| Seq c
    zs) (d
    r :<|| Seq d
    rs) = (a
    x, b
    y, c
    z, d
    r) (a, b, c, d) -> Seq (a, b, c, d) -> NESeq (a, b, c, d)
    forall a. a -> Seq a -> NESeq a
    :<|| Seq a -> Seq b -> Seq c -> Seq d -> Seq (a, b, c, d)
    forall a b c d.
    Seq a -> Seq b -> Seq c -> Seq d -> Seq (a, b, c, d)
    Seq.zip4 Seq a
    xs Seq b
    ys Seq c
    zs Seq d
    rs
    {-# INLINE zip4 #-}

    -- | \( O(\min(n_1,n_2,n_3,n_4)) \).  'zipWith4' takes a function which combines
    -- four elements, as well as four sequences and returns a sequence of
    -- their point-wise combinations, analogous to 'zipWith'.
    zipWith4 :: (a -> b -> c -> d -> e) -> NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq e
    zipWith4 :: forall a b c d e.
    (a -> b -> c -> d -> e)
    -> NESeq a -> NESeq b -> NESeq c -> NESeq d -> NESeq e
    zipWith4 a -> b -> c -> d -> e
    f (a
    x :<|| Seq a
    xs) (b
    y :<|| Seq b
    ys) (c
    z :<|| Seq c
    zs) (d
    r :<|| Seq d
    rs) = a -> b -> c -> d -> e
    f a
    x b
    y c
    z d
    r e -> Seq e -> NESeq e
    forall a. a -> Seq a -> NESeq a
    :<|| (a -> b -> c -> d -> e)
    -> Seq a -> Seq b -> Seq c -> Seq d -> Seq e
    forall a b c d e.
    (a -> b -> c -> d -> e)
    -> Seq a -> Seq b -> Seq c -> Seq d -> Seq e
    Seq.zipWith4 a -> b -> c -> d -> e
    f Seq a
    xs Seq b
    ys Seq c
    zs Seq d
    rs
    {-# INLINE zipWith4 #-}

    -- | \( O(n) \). Unzip a sequence using a function to divide elements.
    --
    -- @ unzipWith f xs == 'unzip' ('fmap' f xs) @
    --
    -- Efficiency note:
    --
    -- @unzipWith@ produces its two results in lockstep. If you calculate
    -- @ unzipWith f xs @ and fully force /either/ of the results, then the
    -- entire structure of the /other/ one will be built as well. This
    -- behavior allows the garbage collector to collect each calculated
    -- pair component as soon as it dies, without having to wait for its mate
    -- to die. If you do not need this behavior, you may be better off simply
    -- calculating the sequence of pairs and using 'fmap' to extract each
    -- component sequence.
    unzipWith :: (a -> (b, c)) -> NESeq a -> (NESeq b, NESeq c)
    unzipWith :: forall a b c. (a -> (b, c)) -> NESeq a -> (NESeq b, NESeq c)
    unzipWith a -> (b, c)
    f (a
    x :<|| Seq a
    xs) = (Seq b -> NESeq b)
    -> (Seq c -> NESeq c) -> (Seq b, Seq c) -> (NESeq b, NESeq c)
    forall a b c d. (a -> b) -> (c -> d) -> (a, c) -> (b, d)
    forall (p :: * -> * -> *) a b c d.
    Bifunctor p =>
    (a -> b) -> (c -> d) -> p a c -> p b d
    bimap (b
    y b -> Seq b -> NESeq b
    forall a. a -> Seq a -> NESeq a
    :<||) (c
    z c -> Seq c -> NESeq c
    forall a. a -> Seq a -> NESeq a
    :<||) ((Seq b, Seq c) -> (NESeq b, NESeq c))
    -> (Seq a -> (Seq b, Seq c)) -> Seq a -> (NESeq b, NESeq c)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (a -> (b, c)) -> Seq a -> (Seq b, Seq c)
    forall a b c. (a -> (b, c)) -> Seq a -> (Seq b, Seq c)
    Seq.unzipWith a -> (b, c)
    f (Seq a -> (NESeq b, NESeq c)) -> Seq a -> (NESeq b, NESeq c)
    forall a b. (a -> b) -> a -> b
    $ Seq a
    xs
      where
        ~(b
    y, c
    z) = a -> (b, c)
    f a
    x
    {-# NOINLINE [1] unzipWith #-}

    {-# RULES
    "unzipWith/map" forall f g xs.
      unzipWith f (map g xs) =
        unzipWith (f . g) xs
      #-}