{-# 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           Data.Sequence.NonEmpty.Internal
import           Data.These
import           Prelude hiding                  (length, scanl, scanl1, scanr, scanr1, splitAt, zip, zipWith, zip3, zipWith3, unzip, replicate, filter, reverse, lookup, take, drop, head, tail, init, last, map)
import qualified Data.Sequence                   as Seq

-- | /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 $bIsNonEmpty :: NESeq a -> Seq a
$mIsNonEmpty :: forall r a. Seq a -> (NESeq a -> r) -> (Void# -> r) -> r
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 $bIsEmpty :: Seq a
$mIsEmpty :: forall r a. Seq a -> (Void# -> r) -> (Void# -> r) -> r
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 :: 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 :: 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 :: 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) |> :: 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 ><| :: 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 :: 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 (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 :: 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 (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 :: Int -> m a -> m (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 :: 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 :: 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 :: (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 :: (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 :: 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 :: 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 :: 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 :: 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 :: (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 :: (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 :: (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 :: (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 :: 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
{-# INLINABLE 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 :: 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."
{-# INLINABLE 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 :: (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 :: (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 :: (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 :: (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 :: (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
{-# INLINABLE 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 :: (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
{-# INLINABLE 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 :: (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 :: (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 :: (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
{-# INLINABLE 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 :: (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 :: 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 :: (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 :: (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
sortOnSeq 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 :: 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 :: (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 :: (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
unstableSortOnSeq 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 :: (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
{-# INLINABLE insertBy #-}

insertOn :: Ord b => (a -> b) -> a -> NESeq a -> NESeq a
insertOn :: (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
{-# INLINABLE 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 :: 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
!? :: 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 :: (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' :: (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 :: 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 :: 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 :: 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 :: 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 :: 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 :: 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
{-# INLINABLE 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 :: 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 :: 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 :: 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 :: 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 :: (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 (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 (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 :: (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 (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 (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 :: (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 :: (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 :: (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 :: (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 :: (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 :: (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 (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 :: 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 :: (a -> b) -> NESeq a -> NESeq b
mapReverse a -> b
f (a
x :<|| Seq a
xs) = (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 :: 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 :: 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 :: (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 :: 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 :: (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 :: (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 (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)
unzipWithSeq 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
 #-}