{-# 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
  #-}