{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE ConstraintKinds #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FunctionalDependencies #-}
-- | Abstractions over sequential data structures, like lists and vectors.
module Data.Sequences where

import Data.Maybe (fromJust, fromMaybe, isJust)
import Data.Monoid (Monoid, mconcat, mempty, (<>))
import Data.MonoTraversable
import Data.Int (Int64, Int)
import qualified Data.List as List
import qualified Data.List.Split as List
import qualified Control.Monad (filterM, replicateM)
import Prelude (Bool (..), Monad (..), Maybe (..), Ordering (..), Ord (..), Eq (..), Functor (..), fromIntegral, otherwise, (-), fst, snd, Integral, ($), flip, maybe, error, (||))
import Data.Char (Char, isSpace)
import qualified Data.ByteString as S
import qualified Data.ByteString.Lazy as L
import qualified Data.Text as T
import qualified Data.Text.Lazy as TL
import Control.Category
import Control.Arrow ((***), first, second)
import Control.Monad (liftM)
import qualified Data.Sequence as Seq
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Storable as VS
import Data.String (IsString)
import qualified Data.List.NonEmpty as NE
import qualified Data.ByteString.Unsafe as SU
import qualified Data.Vector.Generic as VG
import qualified Data.Vector.Algorithms.Merge as VAM
import Data.Ord (comparing)
import qualified Data.Text.Encoding as T
import qualified Data.Text.Lazy.Encoding as TL
import Data.Text.Encoding.Error (lenientDecode)
import Data.Word (Word8)

-- | 'SemiSequence' was created to share code between 'IsSequence' and 'NonNull'.
--
-- @Semi@ means 'SemiGroup'
-- A 'SemiSequence' can accomodate a 'SemiGroup' such as 'NonEmpty' or 'NonNull'
-- A Monoid should be able to fill out 'IsSequence'.
--
-- 'SemiSequence' operations maintain the same type because they all maintain the same number of elements or increase them.
-- However, a decreasing function such as filter may change they type.
-- For example, from 'NonEmpty' to '[]'
-- This type-changing function exists on 'NonNull' as 'nfilter'
--
-- 'filter' and other such functions are placed in 'IsSequence'
--
-- /NOTE/: Like 'GrowingAppend', ideally we'd have a @Semigroup@ superclass
-- constraint here, but that would pull in more dependencies to this package
-- than desired.
class (Integral (Index seq), GrowingAppend seq) => SemiSequence seq where
    -- | The type of the index of a sequence.
    type Index seq

    -- | 'intersperse' takes an element and intersperses that element between
    -- the elements of the sequence.
    --
    -- @
    -- > 'intersperse' ',' "abcde"
    -- "a,b,c,d,e"
    -- @
    intersperse :: Element seq -> seq -> seq

    -- | Reverse a sequence
    --
    -- @
    -- > 'reverse' "hello world"
    -- "dlrow olleh"
    -- @
    reverse :: seq -> seq

    -- | 'find' takes a predicate and a sequence and returns the first element in
    -- the sequence matching the predicate, or 'Nothing' if there isn't an element
    -- that matches the predicate.
    --
    -- @
    -- > 'find' (== 5) [1 .. 10]
    -- 'Just' 5
    --
    -- > 'find' (== 15) [1 .. 10]
    -- 'Nothing'
    -- @
    find :: (Element seq -> Bool) -> seq -> Maybe (Element seq)

    -- | Sort a sequence using an supplied element ordering function.
    --
    -- @
    -- > let compare' x y = case 'compare' x y of LT -> GT; EQ -> EQ; GT -> LT
    -- > 'sortBy' compare' [5,3,6,1,2,4]
    -- [6,5,4,3,2,1]
    -- @
    sortBy :: (Element seq -> Element seq -> Ordering) -> seq -> seq

    -- | Prepend an element onto a sequence.
    --
    -- @
    -- > 4 \``cons`` [1,2,3]
    -- [4,1,2,3]
    -- @
    cons :: Element seq -> seq -> seq

    -- | Append an element onto a sequence.
    --
    -- @
    -- > [1,2,3] \``snoc`` 4
    -- [1,2,3,4]
    -- @
    snoc :: seq -> Element seq -> seq

-- | Create a sequence from a single element.
--
-- @
-- > 'singleton' 'a' :: 'String'
-- "a"
-- > 'singleton' 'a' :: 'Vector' 'Char'
-- 'Data.Vector.fromList' "a"
-- @
singleton :: MonoPointed seq => Element seq -> seq
singleton :: forall seq. MonoPointed seq => Element seq -> seq
singleton = Element seq -> seq
forall seq. MonoPointed seq => Element seq -> seq
opoint
{-# INLINE singleton #-}

-- | Sequence Laws:
--
-- @
-- 'fromList' . 'otoList' = 'id'
-- 'fromList' (x <> y) = 'fromList' x <> 'fromList' y
-- 'otoList' ('fromList' x <> 'fromList' y) = x <> y
-- @
class (Monoid seq, MonoTraversable seq, SemiSequence seq, MonoPointed seq) => IsSequence seq where
    -- | Convert a list to a sequence.
    --
    -- @
    -- > 'fromList' ['a', 'b', 'c'] :: Text
    -- "abc"
    -- @
    fromList :: [Element seq] -> seq
    -- this definition creates the Monoid constraint
    -- However, all the instances define their own fromList
    fromList = [seq] -> seq
forall a. Monoid a => [a] -> a
mconcat ([seq] -> seq) -> ([Element seq] -> [seq]) -> [Element seq] -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> seq) -> [Element seq] -> [seq]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Element seq -> seq
forall seq. MonoPointed seq => Element seq -> seq
singleton

    -- | 'lengthIndex' returns the length of a sequence as @'Index' seq@.
    --
    -- @since 1.0.2
    lengthIndex :: seq -> Index seq;
    lengthIndex = Int64 -> Index seq
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int64 -> Index seq) -> (seq -> Int64) -> seq -> Index seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> Int64
forall mono. MonoFoldable mono => mono -> Int64
olength64;

    -- below functions change type fron the perspective of NonEmpty

    -- | 'break' applies a predicate to a sequence, and returns a tuple where
    -- the first element is the longest prefix (possibly empty) of elements that
    -- /do not satisfy/ the predicate. The second element of the tuple is the
    -- remainder of the sequence.
    --
    -- @'break' p@ is equivalent to @'span' ('not' . p)@
    --
    -- @
    -- > 'break' (> 3) ('fromList' [1,2,3,4,1,2,3,4] :: 'Vector' 'Int')
    -- (fromList [1,2,3],fromList [4,1,2,3,4])
    --
    -- > 'break' (< 'z') ('fromList' "abc" :: 'Text')
    -- ("","abc")
    --
    -- > 'break' (> 'z') ('fromList' "abc" :: 'Text')
    -- ("abc","")
    -- @
    break :: (Element seq -> Bool) -> seq -> (seq, seq)
    break Element seq -> Bool
f = ([Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq)
-> ([Element seq] -> seq)
-> ([Element seq], [Element seq])
-> (seq, seq)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList) (([Element seq], [Element seq]) -> (seq, seq))
-> (seq -> ([Element seq], [Element seq])) -> seq -> (seq, seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> Bool)
-> [Element seq] -> ([Element seq], [Element seq])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.break Element seq -> Bool
f ([Element seq] -> ([Element seq], [Element seq]))
-> (seq -> [Element seq]) -> seq -> ([Element seq], [Element seq])
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'span' applies a predicate to a sequence, and returns a tuple where
    -- the first element is the longest prefix (possibly empty) that
    -- /does satisfy/ the predicate. The second element of the tuple is the
    -- remainder of the sequence.
    --
    -- @'span' p xs@ is equivalent to @('takeWhile' p xs, 'dropWhile' p xs)@
    --
    -- @
    -- > 'span' (< 3) ('fromList' [1,2,3,4,1,2,3,4] :: 'Vector' 'Int')
    -- (fromList [1,2],fromList [3,4,1,2,3,4])
    --
    -- > 'span' (< 'z') ('fromList' "abc" :: 'Text')
    -- ("abc","")
    --
    -- > 'span' (< 0) [1,2,3]
    -- ([],[1,2,3])
    -- @
    span :: (Element seq -> Bool) -> seq -> (seq, seq)
    span Element seq -> Bool
f = ([Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq)
-> ([Element seq] -> seq)
-> ([Element seq], [Element seq])
-> (seq, seq)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList) (([Element seq], [Element seq]) -> (seq, seq))
-> (seq -> ([Element seq], [Element seq])) -> seq -> (seq, seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> Bool)
-> [Element seq] -> ([Element seq], [Element seq])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.span Element seq -> Bool
f ([Element seq] -> ([Element seq], [Element seq]))
-> (seq -> [Element seq]) -> seq -> ([Element seq], [Element seq])
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'dropWhile' returns the suffix remaining after 'takeWhile'.
    --
    -- @
    -- > 'dropWhile' (< 3) [1,2,3,4,5,1,2,3]
    -- [3,4,5,1,2,3]
    --
    -- > 'dropWhile' (< 'z') ('fromList' "abc" :: 'Text')
    -- ""
    -- @
    dropWhile :: (Element seq -> Bool) -> seq -> seq
    dropWhile Element seq -> Bool
f = [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq) -> (seq -> [Element seq]) -> seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> Bool) -> [Element seq] -> [Element seq]
forall a. (a -> Bool) -> [a] -> [a]
List.dropWhile Element seq -> Bool
f ([Element seq] -> [Element seq])
-> (seq -> [Element seq]) -> seq -> [Element seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'takeWhile' applies a predicate to a sequence, and returns the
    -- longest prefix (possibly empty) of the sequence of elements that
    -- /satisfy/ the predicate.
    --
    -- @
    -- > 'takeWhile' (< 3) [1,2,3,4,5,1,2,3]
    -- [1,2]
    --
    -- > 'takeWhile' (< 'z') ('fromList' "abc" :: 'Text')
    -- "abc"
    -- @
    takeWhile :: (Element seq -> Bool) -> seq -> seq
    takeWhile Element seq -> Bool
f = [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq) -> (seq -> [Element seq]) -> seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> Bool) -> [Element seq] -> [Element seq]
forall a. (a -> Bool) -> [a] -> [a]
List.takeWhile Element seq -> Bool
f ([Element seq] -> [Element seq])
-> (seq -> [Element seq]) -> seq -> [Element seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | @'splitAt' n se@ returns a tuple where the first element is the prefix of
    -- the sequence @se@ with length @n@, and the second element is the remainder of
    -- the sequence.
    --
    -- @
    -- > 'splitAt' 6 "Hello world!"
    -- ("Hello ","world!")
    --
    -- > 'splitAt' 3 ('fromList' [1,2,3,4,5] :: 'Vector' 'Int')
    -- (fromList [1,2,3],fromList [4,5])
    -- @
    splitAt :: Index seq -> seq -> (seq, seq)
    splitAt Index seq
i = ([Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq)
-> ([Element seq] -> seq)
-> ([Element seq], [Element seq])
-> (seq, seq)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList) (([Element seq], [Element seq]) -> (seq, seq))
-> (seq -> ([Element seq], [Element seq])) -> seq -> (seq, seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Index seq -> [Element seq] -> ([Element seq], [Element seq])
forall i a. Integral i => i -> [a] -> ([a], [a])
List.genericSplitAt Index seq
i ([Element seq] -> ([Element seq], [Element seq]))
-> (seq -> [Element seq]) -> seq -> ([Element seq], [Element seq])
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | Equivalent to 'splitAt'.
    unsafeSplitAt :: Index seq -> seq -> (seq, seq)
    unsafeSplitAt Index seq
i seq
seq = (Index seq -> seq -> seq
forall seq. IsSequence seq => Index seq -> seq -> seq
unsafeTake Index seq
i seq
seq, Index seq -> seq -> seq
forall seq. IsSequence seq => Index seq -> seq -> seq
unsafeDrop Index seq
i seq
seq)

    -- | @'take' n@ returns the prefix of a sequence of length @n@, or the
    -- sequence itself if @n > 'olength' seq@.
    --
    -- @
    -- > 'take' 3 "abcdefg"
    -- "abc"
    -- > 'take' 4 ('fromList' [1,2,3,4,5,6] :: 'Vector' 'Int')
    -- fromList [1,2,3,4]
    -- @
    take :: Index seq -> seq -> seq
    take Index seq
i = (seq, seq) -> seq
forall a b. (a, b) -> a
fst ((seq, seq) -> seq) -> (seq -> (seq, seq)) -> seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Index seq -> seq -> (seq, seq)
forall seq. IsSequence seq => Index seq -> seq -> (seq, seq)
splitAt Index seq
i

    -- | Equivalent to 'take'.
    unsafeTake :: Index seq -> seq -> seq
    unsafeTake = Index seq -> seq -> seq
forall seq. IsSequence seq => Index seq -> seq -> seq
take

    -- | @'drop' n@ returns the suffix of a sequence after the first @n@
    -- elements, or an empty sequence if @n > 'olength' seq@.
    --
    -- @
    -- > 'drop' 3 "abcdefg"
    -- "defg"
    -- > 'drop' 4 ('fromList' [1,2,3,4,5,6] :: 'Vector' 'Int')
    -- fromList [5,6]
    -- @
    drop :: Index seq -> seq -> seq
    drop Index seq
i = (seq, seq) -> seq
forall a b. (a, b) -> b
snd ((seq, seq) -> seq) -> (seq -> (seq, seq)) -> seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Index seq -> seq -> (seq, seq)
forall seq. IsSequence seq => Index seq -> seq -> (seq, seq)
splitAt Index seq
i

    -- | Equivalent to 'drop'
    unsafeDrop :: Index seq -> seq -> seq
    unsafeDrop = Index seq -> seq -> seq
forall seq. IsSequence seq => Index seq -> seq -> seq
drop

    -- | Same as 'drop' but drops from the end of the sequence instead.
    --
    -- @
    -- > 'dropEnd' 3 "abcdefg"
    -- "abcd"
    -- > 'dropEnd' 4 ('fromList' [1,2,3,4,5,6] :: 'Vector' 'Int')
    -- fromList [1,2]
    -- @
    --
    -- @since 1.0.4.0
    dropEnd :: Index seq -> seq -> seq
    dropEnd Index seq
i seq
s = (seq, seq) -> seq
forall a b. (a, b) -> a
fst ((seq, seq) -> seq) -> (seq, seq) -> seq
forall a b. (a -> b) -> a -> b
$ Index seq -> seq -> (seq, seq)
forall seq. IsSequence seq => Index seq -> seq -> (seq, seq)
splitAt (seq -> Index seq
forall seq. IsSequence seq => seq -> Index seq
lengthIndex seq
s Index seq -> Index seq -> Index seq
forall a. Num a => a -> a -> a
- Index seq
i) seq
s

    -- | 'partition' takes a predicate and a sequence and returns the pair of
    -- sequences of elements which do and do not satisfy the predicate.
    --
    -- @
    -- 'partition' p se = ('filter' p se, 'filter' ('not' . p) se)
    -- @
    partition :: (Element seq -> Bool) -> seq -> (seq, seq)
    partition Element seq -> Bool
f = ([Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq)
-> ([Element seq] -> seq)
-> ([Element seq], [Element seq])
-> (seq, seq)
forall (a :: * -> * -> *) b c b' c'.
Arrow a =>
a b c -> a b' c' -> a (b, b') (c, c')
*** [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList) (([Element seq], [Element seq]) -> (seq, seq))
-> (seq -> ([Element seq], [Element seq])) -> seq -> (seq, seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> Bool)
-> [Element seq] -> ([Element seq], [Element seq])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.partition Element seq -> Bool
f ([Element seq] -> ([Element seq], [Element seq]))
-> (seq -> [Element seq]) -> seq -> ([Element seq], [Element seq])
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'uncons' returns the tuple of the first element of a sequence and the rest
    -- of the sequence, or 'Nothing' if the sequence is empty.
    --
    -- @
    -- > 'uncons' ('fromList' [1,2,3,4] :: 'Vector' 'Int')
    -- 'Just' (1,fromList [2,3,4])
    --
    -- > 'uncons' ([] :: ['Int'])
    -- 'Nothing'
    -- @
    uncons :: seq -> Maybe (Element seq, seq)
    uncons = ((Element seq, [Element seq]) -> (Element seq, seq))
-> Maybe (Element seq, [Element seq]) -> Maybe (Element seq, seq)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([Element seq] -> seq)
-> (Element seq, [Element seq]) -> (Element seq, seq)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (d, b) (d, c)
second [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList) (Maybe (Element seq, [Element seq]) -> Maybe (Element seq, seq))
-> (seq -> Maybe (Element seq, [Element seq]))
-> seq
-> Maybe (Element seq, seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [Element seq] -> Maybe (Element seq, [Element seq])
forall seq. IsSequence seq => seq -> Maybe (Element seq, seq)
uncons ([Element seq] -> Maybe (Element seq, [Element seq]))
-> (seq -> [Element seq])
-> seq
-> Maybe (Element seq, [Element seq])
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'unsnoc' returns the tuple of the init of a sequence and the last element,
    -- or 'Nothing' if the sequence is empty.
    --
    -- @
    -- > 'unsnoc' ('fromList' [1,2,3,4] :: 'Vector' 'Int')
    -- 'Just' (fromList [1,2,3],4)
    --
    -- > 'unsnoc' ([] :: ['Int'])
    -- 'Nothing'
    -- @
    unsnoc :: seq -> Maybe (seq, Element seq)
    unsnoc = (([Element seq], Element seq) -> (seq, Element seq))
-> Maybe ([Element seq], Element seq) -> Maybe (seq, Element seq)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (([Element seq] -> seq)
-> ([Element seq], Element seq) -> (seq, Element seq)
forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList) (Maybe ([Element seq], Element seq) -> Maybe (seq, Element seq))
-> (seq -> Maybe ([Element seq], Element seq))
-> seq
-> Maybe (seq, Element seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [Element seq] -> Maybe ([Element seq], Element seq)
forall seq. IsSequence seq => seq -> Maybe (seq, Element seq)
unsnoc ([Element seq] -> Maybe ([Element seq], Element seq))
-> (seq -> [Element seq])
-> seq
-> Maybe ([Element seq], Element seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'filter' given a predicate returns a sequence of all elements that satisfy
    -- the predicate.
    --
    -- @
    -- > 'filter' (< 5) [1 .. 10]
    -- [1,2,3,4]
    -- @
    filter :: (Element seq -> Bool) -> seq -> seq
    filter Element seq -> Bool
f = [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq) -> (seq -> [Element seq]) -> seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> Bool) -> [Element seq] -> [Element seq]
forall a. (a -> Bool) -> [a] -> [a]
List.filter Element seq -> Bool
f ([Element seq] -> [Element seq])
-> (seq -> [Element seq]) -> seq -> [Element seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | The monadic version of 'filter'.
    filterM :: Monad m => (Element seq -> m Bool) -> seq -> m seq
    filterM Element seq -> m Bool
f = ([Element seq] -> seq) -> m [Element seq] -> m seq
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList (m [Element seq] -> m seq)
-> (seq -> m [Element seq]) -> seq -> m seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [Element seq] -> m Bool)
-> [Element seq] -> m [Element seq]
forall seq (m :: * -> *).
(IsSequence seq, Monad m) =>
(Element seq -> m Bool) -> seq -> m seq
filterM Element seq -> m Bool
Element [Element seq] -> m Bool
f ([Element seq] -> m [Element seq])
-> (seq -> [Element seq]) -> seq -> m [Element seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- replicates are not in SemiSequence to allow for zero

    -- | @'replicate' n x@ is a sequence of length @n@ with @x@ as the
    -- value of every element.
    --
    -- @
    -- > 'replicate' 10 'a' :: Text
    -- "aaaaaaaaaa"
    -- @
    replicate :: Index seq -> Element seq -> seq
    replicate Index seq
i = [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([Element seq] -> seq)
-> (Element seq -> [Element seq]) -> Element seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Index seq -> Element seq -> [Element seq]
forall i a. Integral i => i -> a -> [a]
List.genericReplicate Index seq
i

    -- | The monadic version of 'replicateM'.
    replicateM :: Monad m => Index seq -> m (Element seq) -> m seq
    replicateM Index seq
i = ([Element seq] -> seq) -> m [Element seq] -> m seq
forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
liftM [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList (m [Element seq] -> m seq)
-> (m (Element seq) -> m [Element seq]) -> m (Element seq) -> m seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. Int -> m (Element seq) -> m [Element seq]
forall (m :: * -> *) a. Applicative m => Int -> m a -> m [a]
Control.Monad.replicateM (Index seq -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Index seq
i)

    -- below functions are not in SemiSequence because they return a List (instead of NonEmpty)

    -- | 'group' takes a sequence and returns a list of sequences such that the
    -- concatenation of the result is equal to the argument. Each subsequence in
    -- the result contains only equal elements, using the supplied equality test.
    --
    -- @
    -- > 'groupBy' (==) "Mississippi"
    -- ["M","i","ss","i","ss","i","pp","i"]
    -- @
    groupBy :: (Element seq -> Element seq -> Bool) -> seq -> [seq]
    groupBy Element seq -> Element seq -> Bool
f = ([Element seq] -> seq) -> [[Element seq]] -> [seq]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([[Element seq]] -> [seq])
-> (seq -> [[Element seq]]) -> seq -> [seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq -> Element seq -> Bool)
-> [Element seq] -> [[Element seq]]
forall a. (a -> a -> Bool) -> [a] -> [[a]]
List.groupBy Element seq -> Element seq -> Bool
f ([Element seq] -> [[Element seq]])
-> (seq -> [Element seq]) -> seq -> [[Element seq]]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | Similar to standard 'groupBy', but operates on the whole collection,
    -- not just the consecutive items.
    groupAllOn :: Eq b => (Element seq -> b) -> seq -> [seq]
    groupAllOn Element seq -> b
f = ([Element seq] -> seq) -> [[Element seq]] -> [seq]
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([[Element seq]] -> [seq])
-> (seq -> [[Element seq]]) -> seq -> [seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element [Element seq] -> b) -> [Element seq] -> [[Element seq]]
forall seq b.
(IsSequence seq, Eq b) =>
(Element seq -> b) -> seq -> [seq]
groupAllOn Element seq -> b
Element [Element seq] -> b
f ([Element seq] -> [[Element seq]])
-> (seq -> [Element seq]) -> seq -> [[Element seq]]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'subsequences' returns a list of all subsequences of the argument.
    --
    -- @
    -- > 'subsequences' "abc"
    -- ["","a","b","ab","c","ac","bc","abc"]
    -- @
    subsequences :: seq -> [seq]
    subsequences = ([Element seq] -> seq) -> [[Element seq]] -> [seq]
forall a b. (a -> b) -> [a] -> [b]
List.map [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([[Element seq]] -> [seq])
-> (seq -> [[Element seq]]) -> seq -> [seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [Element seq] -> [[Element seq]]
forall a. [a] -> [[a]]
List.subsequences ([Element seq] -> [[Element seq]])
-> (seq -> [Element seq]) -> seq -> [[Element seq]]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | 'permutations' returns a list of all permutations of the argument.
    --
    -- @
    -- > 'permutations' "abc"
    -- ["abc","bac","cba","bca","cab","acb"]
    -- @
    permutations :: seq -> [seq]
    permutations = ([Element seq] -> seq) -> [[Element seq]] -> [seq]
forall a b. (a -> b) -> [a] -> [b]
List.map [Element seq] -> seq
forall seq. IsSequence seq => [Element seq] -> seq
fromList ([[Element seq]] -> [seq])
-> (seq -> [[Element seq]]) -> seq -> [seq]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. [Element seq] -> [[Element seq]]
forall a. [a] -> [[a]]
List.permutations ([Element seq] -> [[Element seq]])
-> (seq -> [Element seq]) -> seq -> [[Element seq]]
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> [Element seq]
forall mono. MonoFoldable mono => mono -> [Element mono]
otoList

    -- | __Unsafe__
    --
    -- Get the tail of a sequence, throw an exception if the sequence is empty.
    --
    -- @
    -- > 'tailEx' [1,2,3]
    -- [2,3]
    -- @
    tailEx :: seq -> seq
    tailEx = (Element seq, seq) -> seq
forall a b. (a, b) -> b
snd ((Element seq, seq) -> seq)
-> (seq -> (Element seq, seq)) -> seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (Element seq, seq)
-> ((Element seq, seq) -> (Element seq, seq))
-> Maybe (Element seq, seq)
-> (Element seq, seq)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ([Char] -> (Element seq, seq)
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.Sequences.tailEx") (Element seq, seq) -> (Element seq, seq)
forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id (Maybe (Element seq, seq) -> (Element seq, seq))
-> (seq -> Maybe (Element seq, seq)) -> seq -> (Element seq, seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> Maybe (Element seq, seq)
forall seq. IsSequence seq => seq -> Maybe (Element seq, seq)
uncons

    -- | Safe version of 'tailEx'.
    --
    -- Returns 'Nothing' instead of throwing an exception when encountering
    -- an empty monomorphic container.
    --
    -- @since 1.0.0
    tailMay :: seq -> Maybe seq
    tailMay seq
seq
        | seq -> Bool
forall mono. MonoFoldable mono => mono -> Bool
onull seq
seq = Maybe seq
forall a. Maybe a
Nothing
        | Bool
otherwise = seq -> Maybe seq
forall a. a -> Maybe a
Just (seq -> seq
forall seq. IsSequence seq => seq -> seq
tailEx seq
seq)
    {-# INLINE tailMay #-}

    -- | __Unsafe__
    --
    -- Get the init of a sequence, throw an exception if the sequence is empty.
    --
    -- @
    -- > 'initEx' [1,2,3]
    -- [1,2]
    -- @
    initEx :: seq -> seq
    initEx = (seq, Element seq) -> seq
forall a b. (a, b) -> a
fst ((seq, Element seq) -> seq)
-> (seq -> (seq, Element seq)) -> seq -> seq
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. (seq, Element seq)
-> ((seq, Element seq) -> (seq, Element seq))
-> Maybe (seq, Element seq)
-> (seq, Element seq)
forall b a. b -> (a -> b) -> Maybe a -> b
maybe ([Char] -> (seq, Element seq)
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.Sequences.initEx") (seq, Element seq) -> (seq, Element seq)
forall {k} (cat :: k -> k -> *) (a :: k). Category cat => cat a a
id (Maybe (seq, Element seq) -> (seq, Element seq))
-> (seq -> Maybe (seq, Element seq)) -> seq -> (seq, Element seq)
forall {k} (cat :: k -> k -> *) (b :: k) (c :: k) (a :: k).
Category cat =>
cat b c -> cat a b -> cat a c
. seq -> Maybe (seq, Element seq)
forall seq. IsSequence seq => seq -> Maybe (seq, Element seq)
unsnoc

    -- | Safe version of 'initEx'.
    --
    -- Returns 'Nothing' instead of throwing an exception when encountering
    -- an empty monomorphic container.
    --
    -- @since 1.0.0
    initMay :: IsSequence seq => seq -> Maybe seq
    initMay seq
seq
        | seq -> Bool
forall mono. MonoFoldable mono => mono -> Bool
onull seq
seq = Maybe seq
forall a. Maybe a
Nothing
        | Bool
otherwise = seq -> Maybe seq
forall a. a -> Maybe a
Just (seq -> seq
forall seq. IsSequence seq => seq -> seq
initEx seq
seq)
    {-# INLINE initMay #-}

    -- | Equivalent to 'tailEx'.
    unsafeTail :: seq -> seq
    unsafeTail = seq -> seq
forall seq. IsSequence seq => seq -> seq
tailEx

    -- | Equivalent to 'initEx'.