{-# LANGUAGE BangPatterns               #-}
{-# LANGUAGE DerivingStrategies         #-}
{-# LANGUAGE GeneralizedNewtypeDeriving #-}
{-# LANGUAGE PatternSynonyms            #-}
{-# LANGUAGE ViewPatterns               #-}

-- | Strict variants of 'Seq' operations.
--
module Data.Sequence.Strict
  ( StrictSeq (Empty, (:<|), (:|>))
  , getSeq

    -- * Construction
  , empty
  , singleton
  , (<|)
  , (|>)
  , (><)
  , fromList
  , toStrict

    -- * Deconstruction
    -- | Additional functions for deconstructing sequences are available
    -- via the 'Foldable' instance of 'Seq'.

    -- ** Queries
  , null
  , length

    -- * Scans
  , scanl

    -- * Sublists

    -- ** Sequential searches
  , dropWhileL
  , dropWhileR
  , spanl
  , spanr

    -- * Indexing
  , lookup
  , (!?)
  , take
  , takeLast
  , drop
  , dropLast
  , splitAt
  , splitAtEnd

    -- * Indexing with predicates
  , findIndexL
  , findIndicesL
  , findIndexR
  , findIndicesR
  ) where

import           Cardano.Prelude (forceElemsToWHNF)
import           Prelude hiding (drop, length, lookup, null, scanl, splitAt,
                     take)

import           Codec.Serialise (Serialise)
import           Data.Foldable (foldl', toList)
import           Data.Sequence (Seq)
import qualified Data.Sequence as Seq
import           NoThunks.Class (NoThunks (..), noThunksInValues)

infixr 5 ><
infixr 5 <|
infixl 5 |>

infixr 5 :<|
infixl 5 :|>

{-# COMPLETE Empty, (:<|) #-}
{-# COMPLETE Empty, (:|>) #-}

-- | A @newtype@ wrapper around a 'Seq', representing a general-purpose finite
-- sequence that is strict in its values.
--
-- This strictness is not enforced at the type level, but rather by the
-- construction functions in this module. These functions essentially just
-- wrap the original "Data.Sequence" functions while forcing the provided
-- value to WHNF.
newtype StrictSeq a = StrictSeq { StrictSeq a -> Seq a
getSeq :: Seq a }
  deriving stock (StrictSeq a -> StrictSeq a -> Bool
(StrictSeq a -> StrictSeq a -> Bool)
-> (StrictSeq a -> StrictSeq a -> Bool) -> Eq (StrictSeq a)
forall a. Eq a => StrictSeq a -> StrictSeq a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: StrictSeq a -> StrictSeq a -> Bool
$c/= :: forall a. Eq a => StrictSeq a -> StrictSeq a -> Bool
== :: StrictSeq a -> StrictSeq a -> Bool
$c== :: forall a. Eq a => StrictSeq a -> StrictSeq a -> Bool
Eq, Eq (StrictSeq a)
Eq (StrictSeq a)
-> (StrictSeq a -> StrictSeq a -> Ordering)
-> (StrictSeq a -> StrictSeq a -> Bool)
-> (StrictSeq a -> StrictSeq a -> Bool)
-> (StrictSeq a -> StrictSeq a -> Bool)
-> (StrictSeq a -> StrictSeq a -> Bool)
-> (StrictSeq a -> StrictSeq a -> StrictSeq a)
-> (StrictSeq a -> StrictSeq a -> StrictSeq a)
-> Ord (StrictSeq a)
StrictSeq a -> StrictSeq a -> Bool
StrictSeq a -> StrictSeq a -> Ordering
StrictSeq a -> StrictSeq a -> StrictSeq a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall a. Ord a => Eq (StrictSeq a)
forall a. Ord a => StrictSeq a -> StrictSeq a -> Bool
forall a. Ord a => StrictSeq a -> StrictSeq a -> Ordering
forall a. Ord a => StrictSeq a -> StrictSeq a -> StrictSeq a
min :: StrictSeq a -> StrictSeq a -> StrictSeq a
$cmin :: forall a. Ord a => StrictSeq a -> StrictSeq a -> StrictSeq a
max :: StrictSeq a -> StrictSeq a -> StrictSeq a
$cmax :: forall a. Ord a => StrictSeq a -> StrictSeq a -> StrictSeq a
>= :: StrictSeq a -> StrictSeq a -> Bool
$c>= :: forall a. Ord a => StrictSeq a -> StrictSeq a -> Bool
> :: StrictSeq a -> StrictSeq a -> Bool
$c> :: forall a. Ord a => StrictSeq a -> StrictSeq a -> Bool
<= :: StrictSeq a -> StrictSeq a -> Bool
$c<= :: forall a. Ord a => StrictSeq a -> StrictSeq a -> Bool
< :: StrictSeq a -> StrictSeq a -> Bool
$c< :: forall a. Ord a => StrictSeq a -> StrictSeq a -> Bool
compare :: StrictSeq a -> StrictSeq a -> Ordering
$ccompare :: forall a. Ord a => StrictSeq a -> StrictSeq a -> Ordering
$cp1Ord :: forall a. Ord a => Eq (StrictSeq a)
Ord, Int -> StrictSeq a -> ShowS
[StrictSeq a] -> ShowS
StrictSeq a -> String
(Int -> StrictSeq a -> ShowS)
-> (StrictSeq a -> String)
-> ([StrictSeq a] -> ShowS)
-> Show (StrictSeq a)
forall a. Show a => Int -> StrictSeq a -> ShowS
forall a. Show a => [StrictSeq a] -> ShowS
forall a. Show a => StrictSeq a -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [StrictSeq a] -> ShowS
$cshowList :: forall a. Show a => [StrictSeq a] -> ShowS
show :: StrictSeq a -> String
$cshow :: forall a. Show a => StrictSeq a -> String
showsPrec :: Int -> StrictSeq a -> ShowS
$cshowsPrec :: forall a. Show a => Int -> StrictSeq a -> ShowS
Show)
  deriving newtype (a -> StrictSeq a -> Bool
StrictSeq m -> m
StrictSeq a -> [a]
StrictSeq a -> Bool
StrictSeq a -> Int
StrictSeq a -> a
StrictSeq a -> a
StrictSeq a -> a
StrictSeq a -> a
(a -> m) -> StrictSeq a -> m
(a -> m) -> StrictSeq a -> m
(a -> b -> b) -> b -> StrictSeq a -> b
(a -> b -> b) -> b -> StrictSeq a -> b
(b -> a -> b) -> b -> StrictSeq a -> b
(b -> a -> b) -> b -> StrictSeq a -> b
(a -> a -> a) -> StrictSeq a -> a
(a -> a -> a) -> StrictSeq a -> a
(forall m. Monoid m => StrictSeq m -> m)
-> (forall m a. Monoid m => (a -> m) -> StrictSeq a -> m)
-> (forall m a. Monoid m => (a -> m) -> StrictSeq a -> m)
-> (forall a b. (a -> b -> b) -> b -> StrictSeq a -> b)
-> (forall a b. (a -> b -> b) -> b -> StrictSeq a -> b)
-> (forall b a. (b -> a -> b) -> b -> StrictSeq a -> b)
-> (forall b a. (b -> a -> b) -> b -> StrictSeq a -> b)
-> (forall a. (a -> a -> a) -> StrictSeq a -> a)
-> (forall a. (a -> a -> a) -> StrictSeq a -> a)
-> (forall a. StrictSeq a -> [a])
-> (forall a. StrictSeq a -> Bool)
-> (forall a. StrictSeq a -> Int)
-> (forall a. Eq a => a -> StrictSeq a -> Bool)
-> (forall a. Ord a => StrictSeq a -> a)
-> (forall a. Ord a => StrictSeq a -> a)
-> (forall a. Num a => StrictSeq a -> a)
-> (forall a. Num a => StrictSeq a -> a)
-> Foldable StrictSeq
forall a. Eq a => a -> StrictSeq a -> Bool
forall a. Num a => StrictSeq a -> a
forall a. Ord a => StrictSeq a -> a
forall m. Monoid m => StrictSeq m -> m
forall a. StrictSeq a -> Bool
forall a. StrictSeq a -> Int
forall a. StrictSeq a -> [a]
forall a. (a -> a -> a) -> StrictSeq a -> a
forall m a. Monoid m => (a -> m) -> StrictSeq a -> m
forall b a. (b -> a -> b) -> b -> StrictSeq a -> b
forall a b. (a -> b -> b) -> b -> StrictSeq a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: StrictSeq a -> a
$cproduct :: forall a. Num a => StrictSeq a -> a
sum :: StrictSeq a -> a
$csum :: forall a. Num a => StrictSeq a -> a
minimum :: StrictSeq a -> a
$cminimum :: forall a. Ord a => StrictSeq a -> a
maximum :: StrictSeq a -> a
$cmaximum :: forall a. Ord a => StrictSeq a -> a
elem :: a -> StrictSeq a -> Bool
$celem :: forall a. Eq a => a -> StrictSeq a -> Bool
length :: StrictSeq a -> Int
$clength :: forall a. StrictSeq a -> Int
null :: StrictSeq a -> Bool
$cnull :: forall a. StrictSeq a -> Bool
toList :: StrictSeq a -> [a]
$ctoList :: forall a. StrictSeq a -> [a]
foldl1 :: (a -> a -> a) -> StrictSeq a -> a
$cfoldl1 :: forall a. (a -> a -> a) -> StrictSeq a -> a
foldr1 :: (a -> a -> a) -> StrictSeq a -> a
$cfoldr1 :: forall a. (a -> a -> a) -> StrictSeq a -> a
foldl' :: (b -> a -> b) -> b -> StrictSeq a -> b
$cfoldl' :: forall b a. (b -> a -> b) -> b -> StrictSeq a -> b
foldl :: (b -> a -> b) -> b -> StrictSeq a -> b
$cfoldl :: forall b a. (b -> a -> b) -> b -> StrictSeq a -> b
foldr' :: (a -> b -> b) -> b -> StrictSeq a -> b
$cfoldr' :: forall a b. (a -> b -> b) -> b -> StrictSeq a -> b
foldr :: (a -> b -> b) -> b -> StrictSeq a -> b
$cfoldr :: forall a b. (a -> b -> b) -> b -> StrictSeq a -> b
foldMap' :: (a -> m) -> StrictSeq a -> m
$cfoldMap' :: forall m a. Monoid m => (a -> m) -> StrictSeq a -> m
foldMap :: (a -> m) -> StrictSeq a -> m
$cfoldMap :: forall m a. Monoid m => (a -> m) -> StrictSeq a -> m
fold :: StrictSeq m -> m
$cfold :: forall m. Monoid m => StrictSeq m -> m
Foldable, b -> StrictSeq a -> StrictSeq a
NonEmpty (StrictSeq a) -> StrictSeq a
StrictSeq a -> StrictSeq a -> StrictSeq a
(StrictSeq a -> StrictSeq a -> StrictSeq a)
-> (NonEmpty (StrictSeq a) -> StrictSeq a)
-> (forall b. Integral b => b -> StrictSeq a -> StrictSeq a)
-> Semigroup (StrictSeq a)
forall b. Integral b => b -> StrictSeq a -> StrictSeq a
forall a. NonEmpty (StrictSeq a) -> StrictSeq a
forall a. StrictSeq a -> StrictSeq a -> StrictSeq a
forall a.
(a -> a -> a)
-> (NonEmpty a -> a)
-> (forall b. Integral b => b -> a -> a)
-> Semigroup a
forall a b. Integral b => b -> StrictSeq a -> StrictSeq a
stimes :: b -> StrictSeq a -> StrictSeq a
$cstimes :: forall a b. Integral b => b -> StrictSeq a -> StrictSeq a
sconcat :: NonEmpty (StrictSeq a) -> StrictSeq a
$csconcat :: forall a. NonEmpty (StrictSeq a) -> StrictSeq a
<> :: StrictSeq a -> StrictSeq a -> StrictSeq a
$c<> :: forall a. StrictSeq a -> StrictSeq a -> StrictSeq a
Semigroup, Decoder s (StrictSeq a)
Decoder s [StrictSeq a]
[StrictSeq a] -> Encoding
StrictSeq a -> Encoding
(StrictSeq a -> Encoding)
-> (forall s. Decoder s (StrictSeq a))
-> ([StrictSeq a] -> Encoding)
-> (forall s. Decoder s [StrictSeq a])
-> Serialise (StrictSeq a)
forall s. Decoder s [StrictSeq a]
forall s. Decoder s (StrictSeq a)
forall a. Serialise a => [StrictSeq a] -> Encoding
forall a. Serialise a => StrictSeq a -> Encoding
forall a s. Serialise a => Decoder s [StrictSeq a]
forall a s. Serialise a => Decoder s (StrictSeq a)
forall a.
(a -> Encoding)
-> (forall s. Decoder s a)
-> ([a] -> Encoding)
-> (forall s. Decoder s [a])
-> Serialise a
decodeList :: Decoder s [StrictSeq a]
$cdecodeList :: forall a s. Serialise a => Decoder s [StrictSeq a]
encodeList :: [StrictSeq a] -> Encoding
$cencodeList :: forall a. Serialise a => [StrictSeq a] -> Encoding
decode :: Decoder s (StrictSeq a)
$cdecode :: forall a s. Serialise a => Decoder s (StrictSeq a)
encode :: StrictSeq a -> Encoding
$cencode :: forall a. Serialise a => StrictSeq a -> Encoding
Serialise)

instance Functor StrictSeq where
  fmap :: (a -> b) -> StrictSeq a -> StrictSeq b
fmap a -> b
f (StrictSeq Seq a
s) = Seq b -> StrictSeq b
forall a. Seq a -> StrictSeq a
StrictSeq (Seq b -> StrictSeq b) -> (Seq b -> Seq b) -> Seq b -> StrictSeq b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Seq b -> Seq b
forall (t :: * -> *) a. Foldable t => t a -> t a
forceElemsToWHNF (Seq b -> StrictSeq b) -> Seq b -> StrictSeq b
forall a b. (a -> b) -> 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
s

instance Traversable StrictSeq where
  sequenceA :: StrictSeq (f a) -> f (StrictSeq a)
sequenceA (StrictSeq Seq (f a)
xs) = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
toStrict (Seq a -> StrictSeq a) -> f (Seq a) -> f (StrictSeq a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Seq (f a) -> f (Seq a)
forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
sequenceA Seq (f a)
xs

-- | Instance for 'StrictSeq' checks elements only
--
-- The internal fingertree in 'Seq' might have thunks, which is essential for
-- its asymptotic complexity.
instance NoThunks a => NoThunks (StrictSeq a) where
  showTypeOf :: Proxy (StrictSeq a) -> String
showTypeOf Proxy (StrictSeq a)
_ = String
"StrictSeq"
  wNoThunks :: Context -> StrictSeq a -> IO (Maybe ThunkInfo)
wNoThunks Context
ctxt = Context -> [a] -> IO (Maybe ThunkInfo)
forall a. NoThunks a => Context -> [a] -> IO (Maybe ThunkInfo)
noThunksInValues Context
ctxt ([a] -> IO (Maybe ThunkInfo))
-> (StrictSeq a -> [a]) -> StrictSeq a -> IO (Maybe ThunkInfo)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. StrictSeq a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList

-- | A helper function for the ':<|' pattern.
--
viewFront :: StrictSeq a -> Maybe (a, StrictSeq a)
viewFront :: StrictSeq a -> Maybe (a, StrictSeq a)
viewFront (StrictSeq Seq a
xs) = case Seq a -> ViewL a
forall a. Seq a -> ViewL a
Seq.viewl Seq a
xs of
  ViewL a
Seq.EmptyL   -> Maybe (a, StrictSeq a)
forall a. Maybe a
Nothing
  a
x Seq.:< Seq a
xs' -> (a, StrictSeq a) -> Maybe (a, StrictSeq a)
forall a. a -> Maybe a
Just (a
x, Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq Seq a
xs')

-- | A helper function for the ':|>' pattern.
--
viewBack :: StrictSeq a -> Maybe (StrictSeq a, a)
viewBack :: StrictSeq a -> Maybe (StrictSeq a, a)
viewBack (StrictSeq Seq a
xs) = case Seq a -> ViewR a
forall a. Seq a -> ViewR a
Seq.viewr Seq a
xs of
  ViewR a
Seq.EmptyR   -> Maybe (StrictSeq a, a)
forall a. Maybe a
Nothing
  Seq a
xs' Seq.:> a
x -> (StrictSeq a, a) -> Maybe (StrictSeq a, a)
forall a. a -> Maybe a
Just (Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq Seq a
xs', a
x)

-- | A bidirectional pattern synonym matching an empty sequence.
pattern Empty :: StrictSeq a
pattern $bEmpty :: StrictSeq a
$mEmpty :: forall r a. StrictSeq a -> (Void# -> r) -> (Void# -> r) -> r
Empty = StrictSeq Seq.Empty

-- | A bidirectional pattern synonym viewing the front of a non-empty
-- sequence.
pattern (:<|) :: a -> StrictSeq a -> StrictSeq a
pattern x $b:<| :: a -> StrictSeq a -> StrictSeq a
$m:<| :: forall r a.
StrictSeq a -> (a -> StrictSeq a -> r) -> (Void# -> r) -> r
:<| xs <- (viewFront -> Just (x, xs))
  where
    a
x :<| StrictSeq a
xs = a
x a -> StrictSeq a -> StrictSeq a
forall a. a -> StrictSeq a -> StrictSeq a
<| StrictSeq a
xs

-- | A bidirectional pattern synonym viewing the rear of a non-empty
-- sequence.
pattern (:|>) :: StrictSeq a -> a -> StrictSeq a
pattern xs $b:|> :: StrictSeq a -> a -> StrictSeq a
$m:|> :: forall r a.
StrictSeq a -> (StrictSeq a -> a -> r) -> (Void# -> r) -> r
:|> x <- (viewBack -> Just (xs, x))
  where
    StrictSeq a
xs :|> a
x = StrictSeq a
xs StrictSeq a -> a -> StrictSeq a
forall a. StrictSeq a -> a -> StrictSeq a
|> a
x

{-------------------------------------------------------------------------------
  Construction
-------------------------------------------------------------------------------}

-- | \( O(1) \). The empty sequence.
empty :: StrictSeq a
empty :: StrictSeq a
empty = StrictSeq a
forall a. StrictSeq a
Empty

-- | \( O(1) \). A singleton sequence.
singleton :: a -> StrictSeq a
singleton :: a -> StrictSeq a
singleton !a
x =  Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (a -> Seq a
forall a. a -> Seq a
Seq.singleton a
x)

-- | \( O(1) \). Add an element to the left end of a sequence.
-- Mnemonic: a triangle with the single element at the pointy end.
(<|) :: a -> StrictSeq a -> StrictSeq a
(!a
x) <| :: a -> StrictSeq a -> StrictSeq a
<| StrictSeq Seq a
s = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (a
x a -> Seq a -> Seq a
forall a. a -> Seq a -> Seq a
Seq.<| Seq a
s)

-- | \( O(1) \). Add an element to the right end of a sequence.
-- Mnemonic: a triangle with the single element at the pointy end.
(|>) :: StrictSeq a -> a -> StrictSeq a
StrictSeq Seq a
s |> :: StrictSeq a -> a -> StrictSeq a
|> (!a
x) = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (Seq a
s Seq a -> a -> Seq a
forall a. Seq a -> a -> Seq a
Seq.|> a
x)

-- | \( O(\log(\min(n_1,n_2))) \). Concatenate two sequences.
(><) :: StrictSeq a -> StrictSeq a -> StrictSeq a
StrictSeq Seq a
xs >< :: StrictSeq a -> StrictSeq a -> StrictSeq a
>< StrictSeq Seq a
ys = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (Seq a
xs Seq a -> Seq a -> Seq a
forall a. Seq a -> Seq a -> Seq a
Seq.>< Seq a
ys)

fromList :: [a] -> StrictSeq a
fromList :: [a] -> StrictSeq a
fromList ![a]
xs = (StrictSeq a -> a -> StrictSeq a)
-> StrictSeq a -> [a] -> StrictSeq a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' StrictSeq a -> a -> StrictSeq a
forall a. StrictSeq a -> a -> StrictSeq a
(|>) StrictSeq a
forall a. StrictSeq a
empty [a]
xs

-- | Convert a 'Seq' into a 'StrictSeq'.
toStrict :: Seq a -> StrictSeq a
toStrict :: Seq a -> StrictSeq a
toStrict Seq a
xs = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (Seq a -> Seq a
forall (t :: * -> *) a. Foldable t => t a -> t a
forceElemsToWHNF Seq a
xs)

{-------------------------------------------------------------------------------
  Deconstruction
-------------------------------------------------------------------------------}

-- | \( O(1) \). Is this the empty sequence?
null :: StrictSeq a -> Bool
null :: StrictSeq a -> Bool
null (StrictSeq Seq a
xs) = Seq a -> Bool
forall a. Seq a -> Bool
Seq.null Seq a
xs

-- | \( O(1) \). The number of elements in the sequence.
length :: StrictSeq a -> Int
length :: StrictSeq a -> Int
length (StrictSeq Seq a
xs) = Seq a -> Int
forall a. Seq a -> Int
Seq.length Seq a
xs

{-------------------------------------------------------------------------------
  Scans
-------------------------------------------------------------------------------}

-- | '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 -> StrictSeq b -> StrictSeq a
scanl :: (a -> b -> a) -> a -> StrictSeq b -> StrictSeq a
scanl a -> b -> a
f !a
z0 (StrictSeq Seq b
xs) = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (Seq a -> StrictSeq a) -> Seq a -> StrictSeq a
forall a b. (a -> b) -> a -> b
$ Seq a -> Seq a
forall (t :: * -> *) a. Foldable t => t a -> t a
forceElemsToWHNF ((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
z0 Seq b
xs)

{-------------------------------------------------------------------------------
  Sublists
-------------------------------------------------------------------------------}

-- | \( O(i) \) where \( i \) is the prefix length.  @'dropWhileL' p xs@ returns
-- the suffix remaining after @'takeWhileL' p xs@.
dropWhileL :: (a -> Bool) -> StrictSeq a -> StrictSeq a
dropWhileL :: (a -> Bool) -> StrictSeq a -> StrictSeq a
dropWhileL a -> Bool
p (StrictSeq Seq a
xs) = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq ((a -> Bool) -> Seq a -> Seq a
forall a. (a -> Bool) -> Seq a -> Seq a
Seq.dropWhileL a -> Bool
p Seq a
xs)

-- | \( O(i) \) where \( i \) is the suffix length.  @'dropWhileR' p xs@ returns
-- the prefix remaining after @'takeWhileR' p xs@.
--
-- @'dropWhileR' p xs@ is equivalent to @'reverse' ('dropWhileL' p ('reverse' xs))@.
dropWhileR :: (a -> Bool) -> StrictSeq a -> StrictSeq a
dropWhileR :: (a -> Bool) -> StrictSeq a -> StrictSeq a
dropWhileR a -> Bool
p (StrictSeq Seq a
xs) = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq ((a -> Bool) -> Seq a -> Seq a
forall a. (a -> Bool) -> Seq a -> Seq a
Seq.dropWhileR a -> Bool
p Seq a
xs)

-- | \( O(i) \) where \( i \) is the prefix length.  'spanl', applied to
-- a predicate @p@ and a sequence @xs@, returns a pair whose first
-- element is the longest prefix (possibly empty) of @xs@ of elements that
-- satisfy @p@ and the second element is the remainder of the sequence.
spanl :: (a -> Bool) -> StrictSeq a -> (StrictSeq a, StrictSeq a)
spanl :: (a -> Bool) -> StrictSeq a -> (StrictSeq a, StrictSeq a)
spanl a -> Bool
p (StrictSeq Seq a
xs) = (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
forall a. (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
toStrictSeqTuple ((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)

-- | \( O(i) \) where \( i \) is the suffix length.  'spanr', applied to a
-- predicate @p@ and a sequence @xs@, returns a pair whose /first/ element
-- is the longest /suffix/ (possibly empty) of @xs@ of elements that
-- satisfy @p@ and the second element is the remainder of the sequence.
spanr :: (a -> Bool) -> StrictSeq a -> (StrictSeq a, StrictSeq a)
spanr :: (a -> Bool) -> StrictSeq a -> (StrictSeq a, StrictSeq a)
spanr a -> Bool
p (StrictSeq Seq a
xs) = (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
forall a. (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
toStrictSeqTuple ((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)

{-------------------------------------------------------------------------------
  Indexing
-------------------------------------------------------------------------------}

-- | \( 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'.
--
-- prop> 0 <= i < length xs ==> lookup i xs == Just (toList xs !! i)
-- prop> i < 0 || i >= length xs ==> lookup i xs = Nothing
--
-- Unlike 'index', this can be used to retrieve an element without
-- forcing it. For example, to insert the fifth element of a sequence
-- @xs@ into a 'Data.Map.Lazy.Map' @m@ at key @k@, you could use
--
-- @
-- case lookup 5 xs of
--   Nothing -> m
--   Just x -> 'Data.Map.Lazy.insert' k x m
-- @
lookup :: Int -> StrictSeq a -> Maybe a
lookup :: Int -> StrictSeq a -> Maybe a
lookup Int
i (StrictSeq Seq a
xs) = Int -> Seq a -> Maybe a
forall a. Int -> Seq a -> Maybe a
Seq.lookup Int
i Seq a
xs

-- | \( O(\log(\min(i,n-i))) \). A flipped, infix version of 'lookup'.
(!?) :: StrictSeq a -> Int -> Maybe a
!? :: StrictSeq a -> Int -> Maybe a
(!?) = (Int -> StrictSeq a -> Maybe a) -> StrictSeq a -> Int -> Maybe a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Int -> StrictSeq a -> Maybe a
forall a. Int -> StrictSeq a -> Maybe a
lookup

-- | \( 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 -> StrictSeq a -> StrictSeq a
take :: Int -> StrictSeq a -> StrictSeq a
take Int
i (StrictSeq Seq a
xs) = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
Seq.take Int
i Seq a
xs)

-- | Take the last @n@ elements
--
-- Returns the entire sequence if it has fewer than @n@ elements.
--
-- Inherits asymptotic complexity from @drop@.
takeLast :: Int -> StrictSeq a -> StrictSeq a
takeLast :: Int -> StrictSeq a -> StrictSeq a
takeLast Int
i StrictSeq a
xs
  | StrictSeq a -> Int
forall a. StrictSeq a -> Int
length StrictSeq a
xs Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
i = Int -> StrictSeq a -> StrictSeq a
forall a. Int -> StrictSeq a -> StrictSeq a
drop (StrictSeq a -> Int
forall a. StrictSeq a -> Int
length StrictSeq a
xs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) StrictSeq a
xs
  | Bool
otherwise      = StrictSeq a
xs

-- | \( 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 -> StrictSeq a -> StrictSeq a
drop :: Int -> StrictSeq a -> StrictSeq a
drop Int
i (StrictSeq Seq a
xs) = Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq (Int -> Seq a -> Seq a
forall a. Int -> Seq a -> Seq a
Seq.drop Int
i Seq a
xs)

-- | Drop the last @n@ elements
--
-- Returns the @Empty@ sequence if it has fewer than @n@ elements.
--
-- Inherits asymptotic complexity from @take@.
dropLast :: Int -> StrictSeq a -> StrictSeq a
dropLast :: Int -> StrictSeq a -> StrictSeq a
dropLast Int
i StrictSeq a
xs
  | StrictSeq a -> Int
forall a. StrictSeq a -> Int
length StrictSeq a
xs Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
i = Int -> StrictSeq a -> StrictSeq a
forall a. Int -> StrictSeq a -> StrictSeq a
take (StrictSeq a -> Int
forall a. StrictSeq a -> Int
length StrictSeq a
xs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) StrictSeq a
xs
  | Bool
otherwise      = StrictSeq a
forall a. StrictSeq a
Empty

-- | \( O(\log(\min(i,n-i))) \). Split a sequence at a given position.
-- @'splitAt' i s = ('take' i s, 'drop' i s)@.
splitAt :: Int -> StrictSeq a -> (StrictSeq a, StrictSeq a)
splitAt :: Int -> StrictSeq a -> (StrictSeq a, StrictSeq a)
splitAt Int
i (StrictSeq Seq a
xs) = (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
forall a. (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
toStrictSeqTuple (Int -> Seq a -> (Seq a, Seq a)
forall a. Int -> Seq a -> (Seq a, Seq a)
Seq.splitAt Int
i Seq a
xs)

-- | Split at the given position counting from the end of the sequence.
--
-- Inherits asymptotic complexity from 'splitAt'.
splitAtEnd :: Int -> StrictSeq a -> (StrictSeq a, StrictSeq a)
splitAtEnd :: Int -> StrictSeq a -> (StrictSeq a, StrictSeq a)
splitAtEnd Int
i StrictSeq a
xs
  | StrictSeq a -> Int
forall a. StrictSeq a -> Int
length StrictSeq a
xs Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
i = Int -> StrictSeq a -> (StrictSeq a, StrictSeq a)
forall a. Int -> StrictSeq a -> (StrictSeq a, StrictSeq a)
splitAt (StrictSeq a -> Int
forall a. StrictSeq a -> Int
length StrictSeq a
xs Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
i) StrictSeq a
xs
  | Bool
otherwise      = (StrictSeq a
forall a. StrictSeq a
Empty, StrictSeq a
xs)

-- | @'findIndexL' p xs@ finds the index of the leftmost element that
-- satisfies @p@, if any exist.
findIndexL :: (a -> Bool) -> StrictSeq a -> Maybe Int
findIndexL :: (a -> Bool) -> StrictSeq a -> Maybe Int
findIndexL a -> Bool
p (StrictSeq Seq a
xs) = (a -> Bool) -> Seq a -> Maybe Int
forall a. (a -> Bool) -> Seq a -> Maybe Int
Seq.findIndexL a -> Bool
p Seq a
xs

-- | @'findIndexR' p xs@ finds the index of the rightmost element that
-- satisfies @p@, if any exist.
findIndexR :: (a -> Bool) -> StrictSeq a -> Maybe Int
findIndexR :: (a -> Bool) -> StrictSeq a -> Maybe Int
findIndexR a -> Bool
p (StrictSeq Seq a
xs) = (a -> Bool) -> Seq a -> Maybe Int
forall a. (a -> Bool) -> Seq a -> Maybe Int
Seq.findIndexR a -> Bool
p Seq a
xs

-- | @'findIndicesL' p@ finds all indices of elements that satisfy @p@, in
-- ascending order.
findIndicesL :: (a -> Bool) -> StrictSeq a -> [Int]
findIndicesL :: (a -> Bool) -> StrictSeq a -> [Int]
findIndicesL a -> Bool
p (StrictSeq Seq a
xs) = (a -> Bool) -> Seq a -> [Int]
forall a. (a -> Bool) -> Seq a -> [Int]
Seq.findIndicesL a -> Bool
p Seq a
xs

-- | @'findIndicesR' p@ finds all indices of elements that satisfy @p@, in
-- descending order.
findIndicesR :: (a -> Bool) -> StrictSeq a -> [Int]
findIndicesR :: (a -> Bool) -> StrictSeq a -> [Int]
findIndicesR a -> Bool
p (StrictSeq Seq a
xs) = (a -> Bool) -> Seq a -> [Int]
forall a. (a -> Bool) -> Seq a -> [Int]
Seq.findIndicesR a -> Bool
p Seq a
xs

{-------------------------------------------------------------------------------
  Helpers
-------------------------------------------------------------------------------}

toStrictSeqTuple :: (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
toStrictSeqTuple :: (Seq a, Seq a) -> (StrictSeq a, StrictSeq a)
toStrictSeqTuple (Seq a
a, Seq a
b) = (Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq Seq a
a, Seq a -> StrictSeq a
forall a. Seq a -> StrictSeq a
StrictSeq Seq a
b)