-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Sequences and measured sequences
--
-- Sequences and measured sequences with logarithmic time index, split,
-- append.
@package seqn
@version 0.1.0.0
-- | This is an internal module. You probably don't need to import this.
-- Use Data.Seqn.Seq, Data.Seqn.MSeq, or
-- Data.Seqn.PQueue instead.
--
-- The only reason to use this module is to use the constructs defined
-- here with other internal modules.
module Data.Seqn.Internal.Util
class Bifunctor p => Biapplicative p
bipure :: Biapplicative p => a -> b -> p a b
biliftA2 :: Biapplicative p => (a -> b -> c) -> (d -> e -> f) -> p a d -> p b e -> p c f
data S2 a b
S2 :: !a -> !b -> S2 a b
data S3 a b c
S3 :: !a -> !b -> !c -> S3 a b c
data SMaybe a
SNothing :: SMaybe a
SJust :: !a -> SMaybe a
newtype Tagged a b
Tagged :: b -> Tagged a b
[unTagged] :: Tagged a b -> b
newtype SStateT s m a
SStateT :: (s -> m (S2 s a)) -> SStateT s m a
[runSStateT] :: SStateT s m a -> s -> m (S2 s a)
evalSStateT :: Functor m => SStateT s m a -> s -> m a
type SState s = SStateT s Identity
sState :: (s -> S2 s a) -> SState s a
evalSState :: SState s a -> s -> a
(#.) :: Coercible b c => (b -> c) -> (a -> b) -> a -> c
infixr 9 #.
instance GHC.Base.Functor m => GHC.Base.Functor (Data.Seqn.Internal.Util.SStateT s m)
instance GHC.Base.Monad m => GHC.Base.Applicative (Data.Seqn.Internal.Util.SStateT s m)
instance GHC.Base.Functor (Data.Seqn.Internal.Util.Tagged a)
instance Data.Bifunctor.Bifunctor Data.Seqn.Internal.Util.Tagged
instance Data.Seqn.Internal.Util.Biapplicative Data.Seqn.Internal.Util.Tagged
instance GHC.Base.Functor (Data.Seqn.Internal.Util.S2 a)
instance Data.Bifunctor.Bifunctor Data.Seqn.Internal.Util.S2
instance Data.Seqn.Internal.Util.Biapplicative Data.Seqn.Internal.Util.S2
instance Data.Seqn.Internal.Util.Biapplicative Data.Functor.Const.Const
-- | This is an internal module. You probably don't need to import this.
-- Use Data.Seqn.Seq instead.
--
-- WARNING
--
-- Definitions in this module allow violating invariants that would
-- otherwise be guaranteed by Data.Seqn.Seq. Use at your own risk!
module Data.Seqn.Internal.Tree
data Tree a
Bin :: {-# UNPACK #-} !Int -> !a -> !Tree a -> !Tree a -> Tree a
Tip :: Tree a
size :: Tree a -> Int
bin :: a -> Tree a -> Tree a -> Tree a
foldl' :: (b -> a -> b) -> b -> Tree a -> b
ifoldl' :: (Int -> b -> a -> b) -> b -> Int -> Tree a -> b
foldr' :: (a -> b -> b) -> b -> Tree a -> b
ifoldr' :: (Int -> a -> b -> b) -> b -> Int -> Tree a -> b
traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b)
itraverse :: Applicative f => (Int -> a -> f b) -> Int -> Tree a -> f (Tree b)
generateA :: Applicative f => (Int -> f a) -> Int -> Int -> f (Tree a)
adjustF :: Functor f => (a -> f a) -> Int -> Tree a -> f (Tree a)
insertAt :: Int -> a -> Tree a -> Tree a
deleteAt :: Int -> Tree a -> Tree a
cons :: a -> Tree a -> Tree a
snoc :: Tree a -> a -> Tree a
uncons :: Tree a -> SMaybe (S2 a (Tree a))
unsnoc :: Tree a -> SMaybe (S2 (Tree a) a)
splitAtF :: Biapplicative f => Int -> Tree a -> f (Tree a) (S2 a (Tree a))
mapMaybeA :: Applicative f => (a -> f (Maybe b)) -> Tree a -> f (Tree b)
mapEitherA :: Applicative f => (a -> f (Either b c)) -> Tree a -> f (S2 (Tree b) (Tree c))
zipWithStreamM :: Monad m => (a -> b -> m c) -> Tree a -> Stream b -> m (Tree c)
unzipWithA :: Applicative f => (a -> f (b, c)) -> Tree a -> f (S2 (Tree b) (Tree c))
unzipWith3A :: Applicative f => (a -> f (b, c, d)) -> Tree a -> f (S3 (Tree b) (Tree c) (Tree d))
fold :: b -> (Int -> a -> b -> b -> b) -> (Int -> a -> b -> b) -> (Int -> a -> b -> b) -> (a -> b) -> Tree a -> b
foldSimple :: b -> (Int -> a -> b -> b -> b) -> Tree a -> b
link :: a -> Tree a -> Tree a -> Tree a
glue :: Tree a -> Tree a -> Tree a
merge :: Tree a -> Tree a -> Tree a
balanceL :: a -> Tree a -> Tree a -> Tree a
balanceR :: a -> Tree a -> Tree a -> Tree a
valid :: Tree a -> Bool
debugShowsPrec :: Show a => Int -> Tree a -> ShowS
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Seqn.Internal.Tree.Tree a)
instance Control.DeepSeq.NFData1 Data.Seqn.Internal.Tree.Tree
-- | This is an internal module. You probably don't need to import this.
-- Use Data.Seqn.Seq instead.
--
-- WARNING
--
-- Definitions in this module allow violating invariants that would
-- otherwise be guaranteed by Data.Seqn.Seq. Use at your own risk!
module Data.Seqn.Internal.Seq
-- | A sequence with elements of type a.
data Seq a
Tree :: !a -> !Tree a -> Seq a
Empty :: Seq a
-- | The empty sequence.
empty :: Seq a
-- | A singleton sequence.
singleton :: a -> Seq a
-- | <math>. Create a Seq from a list.
--
-- Examples
--
--
-- >>> fromList [8,1,19,11,5,12,12]
-- [8,1,19,11,5,12,12]
--
fromList :: [a] -> Seq a
-- | <math>. Create a Seq from a reversed list.
--
-- Examples
--
--
-- >>> fromRevList "!olleH"
-- "Hello!"
--
fromRevList :: [a] -> Seq a
-- | <math>. A sequence with a repeated element. If the length is
-- negative, empty is returned.
--
-- Examples
--
--
-- >>> replicate 3 "ha"
-- ["ha","ha","ha"]
--
replicate :: Int -> a -> Seq a
-- | <math>. Generate a sequence from a length and an applicative
-- action. If the length is negative, empty is returned.
--
-- Examples
--
--
-- >>> import System.Random (randomIO)
--
-- >>> import Data.Word (Word8)
--
-- >>> replicateA 5 (randomIO :: IO Word8)
-- [26,134,30,58,221]
--
replicateA :: Applicative f => Int -> f a -> f (Seq a)
-- | <math>. Generate a sequence from a length and a generator. If
-- the length is negative, empty is returned.
--
-- Examples
--
--
-- >>> generate 4 (10*)
-- [0,10,20,30]
--
generate :: Int -> (Int -> a) -> Seq a
-- | <math>. Generate a sequence from a length and an applicative
-- generator. If the length is negative, empty is returned.
generateA :: Applicative f => Int -> (Int -> f a) -> f (Seq a)
-- | <math>. Unfold a sequence from left to right.
--
-- Examples
--
--
-- >>> let f (i,a,b) = if i >= 10 then Nothing else Just (a, (i+1, b, a+b))
--
-- >>> unfoldr f (0,0,1)
-- [0,1,1,2,3,5,8,13,21,34]
--
unfoldr :: (b -> Maybe (a, b)) -> b -> Seq a
-- | <math>. Unfold a sequence from right to left.
--
-- Examples
--
--
-- >>> let f i = if i <= 0 then Nothing else Just (i `div` 2, i)
--
-- >>> unfoldl f 1024
-- [1,2,4,8,16,32,64,128,256,512,1024]
--
unfoldl :: (b -> Maybe (b, a)) -> b -> Seq a
-- | <math>. Unfold a sequence monadically from left to right.
unfoldrM :: Monad m => (b -> m (Maybe (a, b))) -> b -> m (Seq a)
-- | <math>. Unfold a sequence monadically from right to left.
unfoldlM :: Monad m => (b -> m (Maybe (b, a))) -> b -> m (Seq a)
-- | <math>. Map over a Foldable and concatenate the
-- results.
--
-- Examples
--
--
-- >>> concatMap (uncurry replicate) [(1,'H'),(1,'e'),(2,'l'),(1,'o')]
-- "Hello"
--
concatMap :: Foldable f => (a -> Seq b) -> f a -> Seq b
-- | <math>. Convert to a list in reverse.
--
-- To convert to a list without reversing, use
-- Data.Foldable.toList.
--
-- Examples
--
--
-- >>> toRevList (fromList "!olleH")
-- "Hello!"
--
toRevList :: Seq a -> [a]
-- | <math>. Look up the element at an index.
--
-- Examples
--
--
-- >>> lookup 3 (fromList "haskell")
-- Just 'k'
--
-- >>> lookup (-1) (singleton 7)
-- Nothing
--
lookup :: Int -> Seq a -> Maybe a
-- | <math>. Look up the element at an index. Calls error if
-- the index is out of bounds.
--
-- Examples
--
--
-- >>> index 3 (fromList "haskell")
-- 'k'
--
-- >>> index (-1) (singleton 7)
-- *** Exception: ...
--
index :: Int -> Seq a -> a
-- | <math>. Infix version of lookup.
(!?) :: Seq a -> Int -> Maybe a
-- | <math>. Infix version of index. Calls error if
-- the index is out of bounds.
(!) :: Seq a -> Int -> a
-- | <math>. Update an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
--
-- Examples
--
--
-- >>> update 3 'b' (fromList "bird")
-- "birb"
--
-- >>> update 3 True (singleton False)
-- [False]
--
update :: Int -> a -> Seq a -> Seq a
-- | <math>. Adjust the element at an index. If the index is out of
-- bounds the sequence is returned unchanged.
--
-- Examples
--
--
-- >>> adjust Data.List.reverse 1 (fromList ["Hello", "ereht"])
-- ["Hello","there"]
--
-- >>> adjust (*100) (-1) (singleton 7)
-- [7]
--
adjust :: (a -> a) -> Int -> Seq a -> Seq a
-- | <math>. Insert an element at an index. If the index is out of
-- bounds, the element is added to the closest end of the sequence.
--
-- Examples
--
--
-- >>> insertAt 1 'a' (fromList "ct")
-- "cat"
--
-- >>> insertAt (-10) 0 (fromList [5,6,7])
-- [0,5,6,7]
--
-- >>> insertAt 10 0 (fromList [5,6,7])
-- [5,6,7,0]
--
insertAt :: Int -> a -> Seq a -> Seq a
-- | <math>. Delete an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
--
-- Examples
--
--
-- >>> deleteAt 2 (fromList "cart")
-- "cat"
--
-- >>> deleteAt 10 (fromList [5,6,7])
-- [5,6,7]
--
deleteAt :: Int -> Seq a -> Seq a
-- | <math>. Append a value to the beginning of a sequence.
--
-- Examples
--
--
-- >>> cons 1 (fromList [2,3])
-- [1,2,3]
--
cons :: a -> Seq a -> Seq a
-- | <math>. Append a value to the end of a sequence.
--
-- Examples
--
--
-- >>> snoc (fromList [1,2]) 3
-- [1,2,3]
--
snoc :: Seq a -> a -> Seq a
-- | <math>. The head and tail of a sequence.
--
-- Examples
--
--
-- >>> uncons (fromList [1,2,3])
-- Just (1,[2,3])
--
-- >>> uncons empty
-- Nothing
--
uncons :: Seq a -> Maybe (a, Seq a)
-- | <math>. The init and last of a sequence.
--
-- Examples
--
--
-- >>> unsnoc (fromList [1,2,3])
-- Just ([1,2],3)
--
-- >>> unsnoc empty
-- Nothing
--
unsnoc :: Seq a -> Maybe (Seq a, a)
-- | <math>. Take a number of elements from the beginning of a
-- sequence.
--
-- Examples
--
--
-- >>> take 3 (fromList "haskell")
-- "has"
--
-- >>> take (-1) (fromList [1,2,3])
-- []
--
-- >>> take 10 (fromList [1,2,3])
-- [1,2,3]
--
take :: Int -> Seq a -> Seq a
-- | <math>. Drop a number of elements from the beginning of a
-- sequence.
--
-- Examples
--
--
-- >>> drop 3 (fromList "haskell")
-- "kell"
--
-- >>> drop (-1) (fromList [1,2,3])
-- [1,2,3]
--
-- >>> drop 10 (fromList [1,2,3])
-- []
--
drop :: Int -> Seq a -> Seq a
-- | <math>. The slice of a sequence between two indices (inclusive).
--
-- Examples
--
--
-- >>> slice (1,3) (fromList "haskell")
-- "ask"
--
-- >>> slice (-10,2) (fromList [1,2,3,4,5])
-- [1,2,3]
--
-- >>> slice (2,1) (fromList [1,2,3,4,5])
-- []
--
slice :: (Int, Int) -> Seq a -> Seq a
-- | <math>. Split a sequence at a given index.
--
--
-- splitAt n xs == (take n xs, drop n xs)
--
--
-- Examples
--
--
-- >>> splitAt 3 (fromList "haskell")
-- ("has","kell")
--
-- >>> splitAt (-1) (fromList [1,2,3])
-- ([],[1,2,3])
--
-- >>> splitAt 10 (fromList [1,2,3])
-- ([1,2,3],[])
--
splitAt :: Int -> Seq a -> (Seq a, Seq a)
-- | <math>. Take a number of elements from the end of a sequence.
takeEnd :: Int -> Seq a -> Seq a
-- | <math>. Drop a number of elements from the end of a sequence.
dropEnd :: Int -> Seq a -> Seq a
-- | <math>. Split a sequence at a given index from the end.
--
--
-- splitAtEnd n xs == (dropEnd n xs, takeEnd n xs)
--
splitAtEnd :: Int -> Seq a -> (Seq a, Seq a)
-- | <math>. All suffixes of a sequence, longest first.
--
-- Examples
--
--
-- >>> tails (fromList [1,2,3])
-- [[1,2,3],[2,3],[3],[]]
--
tails :: Seq a -> Seq (Seq a)
-- | <math>. All prefixes of a sequence, shortest first.
--
-- Examples
--
--
-- >>> inits (fromList [1,2,3])
-- [[],[1],[1,2],[1,2,3]]
--
inits :: Seq a -> Seq (Seq a)
-- | <math>. Split a sequence into chunks of the given length
-- c. If c <= 0, empty is returned.
--
-- Examples
--
--
-- >>> chunksOf 3 (fromList [1..10])
-- [[1,2,3],[4,5,6],[7,8,9],[10]]
--
-- >>> chunksOf 10 (fromList "hello")
-- ["hello"]
--
-- >>> chunksOf (-1) (singleton 7)
-- []
--
chunksOf :: Int -> Seq a -> Seq (Seq a)
-- | <math>. Keep elements that satisfy a predicate.
--
-- Examples
--
--
-- >>> filter even (fromList [1..10])
-- [2,4,6,8,10]
--
filter :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. Keep the Justs in a sequence.
--
-- Examples
--
--
-- >>> catMaybes (fromList [Just 1, Nothing, Nothing, Just 10, Just 100])
-- [1,10,100]
--
catMaybes :: Seq (Maybe a) -> Seq a
-- | <math>. Map over elements and collect the Justs.
mapMaybe :: (a -> Maybe b) -> Seq a -> Seq b
-- | <math>. Map over elements and split the Lefts and
-- Rights.
--
-- Examples
--
--
-- >>> mapEither (\x -> if odd x then Left x else Right x) (fromList [1..10])
-- ([1,3,5,7,9],[2,4,6,8,10])
--
mapEither :: (a -> Either b c) -> Seq a -> (Seq b, Seq c)
-- | <math>. Keep elements that satisfy an applicative predicate.
filterA :: Applicative f => (a -> f Bool) -> Seq a -> f (Seq a)
-- | <math>. Traverse over elements and collect the Justs.
mapMaybeA :: Applicative f => (a -> f (Maybe b)) -> Seq a -> f (Seq b)
-- | <math>. Traverse over elements and split the Lefts and
-- Rights.
mapEitherA :: Applicative f => (a -> f (Either b c)) -> Seq a -> f (Seq b, Seq c)
-- | <math>. The longest prefix of elements that satisfy a predicate.
-- <math> is the length of the prefix.
--
-- Examples
--
--
-- >>> takeWhile even (fromList [2,4,6,1,3,2,4])
-- [2,4,6]
--
takeWhile :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The remainder after removing the longest prefix of
-- elements that satisfy a predicate. <math> is the length of the
-- prefix.
--
-- Examples
--
--
-- >>> dropWhile even (fromList [2,4,6,1,3,2,4])
-- [1,3,2,4]
--
dropWhile :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The longest prefix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the prefix.
--
--
-- span p xs == (takeWhile p xs, dropWhile p xs)
--
--
-- Examples
--
--
-- >>> span even (fromList [2,4,6,1,3,2,4])
-- ([2,4,6],[1,3,2,4])
--
span :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. The longest prefix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the prefix.
--
--
-- break p == span (not . p)
--
--
-- Examples
--
--
-- >>> break odd (fromList [2,4,6,1,3,2,4])
-- ([2,4,6],[1,3,2,4])
--
break :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. The longest suffix of elements that satisfy a predicate.
-- <math> is the length of the suffix.
takeWhileEnd :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The remainder after removing the longest suffix of
-- elements that satisfy a predicate. <math> is the length of the
-- suffix.
dropWhileEnd :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The longest suffix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the suffix.
--
--
-- spanEnd p xs == (dropWhileEnd p xs, takeWhileEnd p xs)
--
spanEnd :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. The longest suffix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the suffix.
--
--
-- breakEnd p == spanEnd (not . p)
--
breakEnd :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. Reverse a sequence.
--
-- Examples
--
--
-- >>> reverse (fromList [1,2,3,4,5])
-- [5,4,3,2,1]
--
reverse :: Seq a -> Seq a
-- | <math>. Intersperse an element between the elements of a
-- sequence.
--
-- Examples
--
--
-- >>> intersperse '.' (fromList "HELLO")
-- "H.E.L.L.O"
--
intersperse :: a -> Seq a -> Seq a
-- | <math>. Like foldl' but keeps all intermediate values.
--
-- Examples
--
--
-- >>> scanl (+) 0 (fromList [1..5])
-- [0,1,3,6,10,15]
--
scanl :: (b -> a -> b) -> b -> Seq a -> Seq b
-- | <math>. Like foldr' but keeps all intermediate values.
--
-- Examples
--
--
-- >>> scanr (+) 0 (fromList [1..5])
-- [15,14,12,9,5,0]
--
scanr :: (a -> b -> b) -> b -> Seq a -> Seq b
-- | <math>. Sort a sequence. The sort is stable.
--
-- Examples
--
--
-- >>> sort (fromList [4,2,3,5,1])
-- [1,2,3,4,5]
--
sort :: Ord a => Seq a -> Seq a
-- | <math>. Sort a sequence using a comparison function. The sort is
-- stable.
--
-- Examples
--
--
-- >>> import Data.Ord (Down, comparing)
--
-- >>> sortBy (comparing Down) (fromList [4,2,3,5,1])
-- [5,4,3,2,1]
--
sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a
-- | <math>. The last element satisfying a predicate.
--
-- To get the first element, use Data.Foldable.find.
findEnd :: (a -> Bool) -> Seq a -> Maybe a
-- | <math>. The index of the first element satisfying a predicate.
--
-- Examples
--
--
-- >>> findIndex even (fromList [1..5])
-- Just 1
--
-- >>> findIndex (<0) (fromList [1..5])
-- Nothing
--
findIndex :: (a -> Bool) -> Seq a -> Maybe Int
-- | <math>. The index of the last element satisfying a predicate.
findIndexEnd :: (a -> Bool) -> Seq a -> Maybe Int
-- | <math>. Indices in the second sequence where the first sequence
-- begins as a substring. Includes overlapping occurences.
--
-- Examples
--
--
-- >>> infixIndices (fromList "ana") (fromList "banana")
-- [1,3]
--
-- >>> infixIndices (fromList [0]) (fromList [1,2,3])
-- []
--
-- >>> infixIndices (fromList "") (fromList "abc")
-- [0,1,2,3]
--
infixIndices :: Eq a => Seq a -> Seq a -> [Int]
-- | <math>. Binary search for an element in a sequence.
--
-- Given a function f this function returns an arbitrary element
-- x, if it exists, such that f x = EQ. f must
-- be monotonic on the sequence— specifically fmap f must result
-- in a sequence which has many (possibly zero) LTs, followed by
-- many EQs, followed by many GTs.
--
-- Examples
--
--
-- >>> binarySearchFind (`compare` 8) (fromList [2,4..10])
-- Just 8
--
-- >>> binarySearchFind (`compare` 3) (fromList [2,4..10])
-- Nothing
--
binarySearchFind :: (a -> Ordering) -> Seq a -> Maybe a
-- | <math>. Whether the first sequence is a prefix of the second.
--
-- Examples
--
--
-- >>> fromList "has" `isPrefixOf` fromList "haskell"
-- True
--
-- >>> fromList "ask" `isPrefixOf` fromList "haskell"
-- False
--
isPrefixOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Whether the first sequence is a suffix of the second.
--
-- Examples
--
--
-- >>> fromList "ell" `isSuffixOf` fromList "haskell"
-- True
--
-- >>> fromList "ask" `isSuffixOf` fromList "haskell"
-- False
--
isSuffixOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Whether the first sequence is a substring of the second.
--
-- Examples
--
--
-- >>> fromList "meow" `isInfixOf` fromList "homeowner"
-- True
--
-- >>> fromList [2,4] `isInfixOf` fromList [2,3,4]
-- False
--
isInfixOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Whether the first sequence is a subsequence of the
-- second.
--
-- Examples
--
--
-- >>> fromList [2,4] `isSubsequenceOf` [2,3,4]
-- True
--
-- >>> fromList "tab" `isSubsequenceOf` fromList "bat"
-- False
--
isSubsequenceOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Zip two sequences. The result is as long as the shorter
-- sequence.
zip :: Seq a -> Seq b -> Seq (a, b)
-- | <math>. Zip three sequences. The result is as long as the
-- shortest sequence.
zip3 :: Seq a -> Seq b -> Seq c -> Seq (a, b, c)
-- | <math>. Zip two sequences with a function. The result is as long
-- as the shorter sequence.
--
-- Examples
--
--
-- >>> zipWith (+) (fromList [1,2,3]) (fromList [1,1,1,1,1])
-- [2,3,4]
--
zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c
-- | <math>. Zip three sequences with a function. The result is as
-- long as the shortest sequence.
zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
-- | <math>. Zip two sequences with a monadic function. The result is
-- as long as the shorter sequence.
zipWithM :: Monad m => (a -> b -> m c) -> Seq a -> Seq b -> m (Seq c)
-- | <math>. Zip three sequences with a monadic function. The result
-- is as long as the shortest sequence.
zipWith3M :: Monad m => (a -> b -> c -> m d) -> Seq a -> Seq b -> Seq c -> m (Seq d)
-- | <math>. Unzip a sequence of pairs.
unzip :: Seq (a, b) -> (Seq a, Seq b)
-- | <math>. Unzip a sequence of triples.
unzip3 :: Seq (a, b, c) -> (Seq a, Seq b, Seq c)
-- | <math>. Map over a sequence and unzip the result.
--
-- Examples
--
--
-- >>> unzipWith (\x -> (x-1, x*2)) (fromList [1..5])
-- ([0,1,2,3,4],[2,4,6,8,10])
--
unzipWith :: (a -> (b, c)) -> Seq a -> (Seq b, Seq c)
-- | <math>. Map over a sequence and unzip the result.
unzipWith3 :: (a -> (b, c, d)) -> Seq a -> (Seq b, Seq c, Seq d)
fromTree :: Tree a -> Seq a
valid :: Seq a -> Bool
debugShowsPrec :: Show a => Int -> Seq a -> ShowS
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Seqn.Internal.Seq.Seq a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Seqn.Internal.Seq.Seq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Seqn.Internal.Seq.Seq a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Seqn.Internal.Seq.Seq a)
instance Data.Functor.Classes.Eq1 Data.Seqn.Internal.Seq.Seq
instance Data.Functor.Classes.Ord1 Data.Seqn.Internal.Seq.Seq
instance Data.Functor.Classes.Show1 Data.Seqn.Internal.Seq.Seq
instance Data.Functor.Classes.Read1 Data.Seqn.Internal.Seq.Seq
instance Data.Foldable.Foldable Data.Seqn.Internal.Seq.Seq
instance GHC.Base.Functor Data.Seqn.Internal.Seq.Seq
instance Data.Traversable.Traversable Data.Seqn.Internal.Seq.Seq
instance GHC.Base.Semigroup (Data.Seqn.Internal.Seq.Seq a)
instance GHC.Base.Monoid (Data.Seqn.Internal.Seq.Seq a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Seqn.Internal.Seq.Seq a)
instance Control.DeepSeq.NFData1 Data.Seqn.Internal.Seq.Seq
instance GHC.Base.Applicative Data.Seqn.Internal.Seq.Seq
instance GHC.Base.Alternative Data.Seqn.Internal.Seq.Seq
instance GHC.Base.Monad Data.Seqn.Internal.Seq.Seq
instance GHC.Base.MonadPlus Data.Seqn.Internal.Seq.Seq
instance Control.Monad.Fail.MonadFail Data.Seqn.Internal.Seq.Seq
instance Control.Monad.Fix.MonadFix Data.Seqn.Internal.Seq.Seq
instance Control.Monad.Zip.MonadZip Data.Seqn.Internal.Seq.Seq
instance (a GHC.Types.~ GHC.Types.Char) => Data.String.IsString (Data.Seqn.Internal.Seq.Seq a)
instance GHC.IsList.IsList (Data.Seqn.Internal.Seq.Seq a)
instance WithIndex.FunctorWithIndex GHC.Types.Int Data.Seqn.Internal.Seq.Seq
instance WithIndex.FoldableWithIndex GHC.Types.Int Data.Seqn.Internal.Seq.Seq
instance WithIndex.TraversableWithIndex GHC.Types.Int Data.Seqn.Internal.Seq.Seq
-- | This is an internal module. You probably don't need to import this.
-- Use Data.Seqn.MSeq instead.
--
-- WARNING
--
-- Definitions in this module allow violating invariants that would
-- otherwise be guaranteed by Data.Seqn.MSeq. Use at your own
-- risk!
module Data.Seqn.Internal.MTree
-- | Types that have a combinable property, called the measure.
class Semigroup (Measure a) => Measured a where {
type Measure a;
}
-- | Calculate the measure of a value.
measure :: Measured a => a -> Measure a
data MTree a
MBin :: {-# UNPACK #-} !Int -> !Measure a -> !a -> !MTree a -> !MTree a -> MTree a
MTip :: MTree a
singleton :: Measured a => a -> MTree a
size :: MTree a -> Int
(<>>) :: Measured a => MTree a -> Measure a -> Measure a
infixr 6 <>>
(<<>) :: Measured a => Measure a -> MTree a -> Measure a
infixr 6 <<>
bin :: Measured a => a -> MTree a -> MTree a -> MTree a
binn :: Measured a => Int -> a -> MTree a -> MTree a -> MTree a
foldMap :: forall a m. Monoid m => (a -> m) -> MTree a -> m
foldl' :: (b -> a -> b) -> b -> MTree a -> b
foldr' :: (a -> b -> b) -> b -> MTree a -> b
ifoldl' :: (Int -> b -> a -> b) -> b -> Int -> MTree a -> b
ifoldr' :: (Int -> a -> b -> b) -> b -> Int -> MTree a -> b
traverse :: (Measured b, Applicative f) => (a -> f b) -> MTree a -> f (MTree b)
ifoldMap :: Monoid m => (Int -> a -> m) -> Int -> MTree a -> m
itraverse :: (Measured b, Applicative f) => (Int -> a -> f b) -> Int -> MTree a -> f (MTree b)
generateA :: (Measured a, Applicative f) => (Int -> f a) -> Int -> Int -> f (MTree a)
index :: Int -> MTree a -> a
adjustF :: (Measured a, Functor f) => (a -> f a) -> Int -> MTree a -> f (MTree a)
insertAt :: Measured a => Int -> a -> MTree a -> MTree a
deleteAt :: Measured a => Int -> MTree a -> MTree a
cons :: Measured a => a -> MTree a -> MTree a
snoc :: Measured a => MTree a -> a -> MTree a
uncons :: Measured a => MTree a -> SMaybe (S2 a (MTree a))
unconsSure :: Measured a => a -> MTree a -> MTree a -> S2 a (MTree a)
unsnoc :: Measured a => MTree a -> SMaybe (S2 (MTree a) a)
unsnocSure :: Measured a => a -> MTree a -> MTree a -> S2 (MTree a) a
splitAtF :: (Measured a, Biapplicative f) => Int -> MTree a -> f (MTree a) (S2 a (MTree a))
mapMaybeA :: (Applicative f, Measured b) => (a -> f (Maybe b)) -> MTree a -> f (MTree b)
mapEitherA :: (Applicative f, Measured b, Measured c) => (a -> f (Either b c)) -> MTree a -> f (S2 (MTree b) (MTree c))
liftRnf2 :: (Measure a -> ()) -> (a -> ()) -> MTree a -> ()
zipWithStreamM :: (Measured c, Monad m) => (a -> b -> m c) -> MTree a -> Stream b -> m (MTree c)
unzipWithA :: (Measured b, Measured c, Applicative f) => (a -> f (b, c)) -> MTree a -> f (S2 (MTree b) (MTree c))
unzipWith3A :: (Measured b, Measured c, Measured d, Applicative f) => (a -> f (b, c, d)) -> MTree a -> f (S3 (MTree b) (MTree c) (MTree d))
fold :: b -> (Int -> a -> b -> b -> b) -> (Int -> a -> b -> b) -> (Int -> a -> b -> b) -> (a -> b) -> MTree a -> b
foldSimple :: b -> (Int -> a -> b -> b -> b) -> MTree a -> b
link :: Measured a => a -> MTree a -> MTree a -> MTree a
merge :: Measured a => MTree a -> MTree a -> MTree a
glue :: Measured a => MTree a -> MTree a -> MTree a
balanceL :: Measured a => a -> MTree a -> MTree a -> MTree a
balanceR :: Measured a => a -> MTree a -> MTree a -> MTree a
valid :: (Measured a, Eq (Measure a)) => MTree a -> Bool
debugShowsPrec :: (Show a, Show (Measure a)) => Int -> MTree a -> ShowS
instance (Control.DeepSeq.NFData (Data.Seqn.Internal.MTree.Measure a), Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Seqn.Internal.MTree.MTree a)
-- | This is an internal module. You probably don't need to import this.
-- Use Data.Seqn.MSeq instead.
--
-- WARNING
--
-- Definitions in this module allow violating invariants that would
-- otherwise be guaranteed by Data.Seqn.MSeq. Use at your own
-- risk!
module Data.Seqn.Internal.MSeq
-- | A sequence with elements of type a. An instance of
-- Measured a is required for most operations.
data MSeq a
MTree :: !a -> !MTree a -> MSeq a
MEmpty :: MSeq a
-- | The empty sequence.
empty :: MSeq a
-- | A singleton sequence.
singleton :: a -> MSeq a
-- | <math>. Create an MSeq from a list.
fromList :: Measured a => [a] -> MSeq a
-- | <math>. Create an MSeq from a reversed list.
fromRevList :: Measured a => [a] -> MSeq a
-- | <math>. A sequence with a repeated element. If the length is
-- negative, empty is returned.
replicate :: Measured a => Int -> a -> MSeq a
-- | <math>. Generate a sequence from a length and an applicative
-- action. If the length is negative, empty is returned.
replicateA :: (Measured a, Applicative f) => Int -> f a -> f (MSeq a)
-- | <math>. Generate a sequence from a length and a generator. If
-- the length is negative, empty is returned.
generate :: Measured a => Int -> (Int -> a) -> MSeq a
-- | <math>. Generate a sequence from a length and an applicative
-- generator. If the length is negative, empty is returned.
generateA :: (Measured a, Applicative f) => Int -> (Int -> f a) -> f (MSeq a)
-- | <math>. Unfold a sequence from left to right.
unfoldr :: Measured a => (b -> Maybe (a, b)) -> b -> MSeq a
-- | <math>. Unfold a sequence from right to left.
unfoldl :: Measured a => (b -> Maybe (b, a)) -> b -> MSeq a
-- | <math>. Unfold a sequence monadically from left to right.
unfoldrM :: (Measured a, Monad m) => (b -> m (Maybe (a, b))) -> b -> m (MSeq a)
-- | <math>. Unfold a sequence monadically from right to left.
unfoldlM :: (Measured a, Monad m) => (b -> m (Maybe (b, a))) -> b -> m (MSeq a)
-- | <math>. Map over a Foldable and concatenate the
-- results.
concatMap :: (Measured b, Foldable f) => (a -> MSeq b) -> f a -> MSeq b
-- | Monadic fixed point. See Control.Monad.Fix.
mfix :: Measured a => (a -> MSeq a) -> MSeq a
-- | <math>. Convert to a list in reverse.
--
-- To convert to a list without reversing, use
-- Data.Foldable.toList.
toRevList :: MSeq a -> [a]
-- | <math>. Look up the element at an index.
lookup :: Int -> MSeq a -> Maybe a
-- | <math>. Look up the element at an index. Calls error if
-- the index is out of bounds.
index :: Int -> MSeq a -> a
-- | <math>. Infix version of lookup.
(!?) :: MSeq a -> Int -> Maybe a
-- | <math>. Infix version of index. Calls error if
-- the index is out of bounds.
(!) :: MSeq a -> Int -> a
-- | <math>. Update an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
update :: Measured a => Int -> a -> MSeq a -> MSeq a
-- | <math>. Adjust the element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
adjust :: Measured a => (a -> a) -> Int -> MSeq a -> MSeq a
-- | <math>. Insert an element at an index. If the index is out of
-- bounds, the element is added to the closest end of the sequence.
insertAt :: Measured a => Int -> a -> MSeq a -> MSeq a
-- | <math>. Delete an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
deleteAt :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Append a value to the beginning of a sequence.
cons :: Measured a => a -> MSeq a -> MSeq a
-- | <math>. Append a value to the end of a sequence.
snoc :: Measured a => MSeq a -> a -> MSeq a
-- | <math>. The head and tail of a sequence.
uncons :: Measured a => MSeq a -> Maybe (a, MSeq a)
-- | <math>. The init and last of a sequence.
unsnoc :: Measured a => MSeq a -> Maybe (MSeq a, a)
-- | <math>. Take a number of elements from the beginning of a
-- sequence.
take :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Drop a number of elements from the beginning of a
-- sequence.
drop :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. The slice of a sequence between two indices (inclusive).
slice :: Measured a => (Int, Int) -> MSeq a -> MSeq a
-- | <math>. Split a sequence at a given index.
--
--
-- splitAt n xs == (take n xs, drop n xs)
--
splitAt :: Measured a => Int -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. Take a number of elements from the end of a sequence.
takeEnd :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Drop a number of elements from the end of a sequence.
dropEnd :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Split a sequence at a given index from the end.
--
--
-- splitAtEnd n xs == (dropEnd n xs, takeEnd n xs)
--
splitAtEnd :: Measured a => Int -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. Keep elements that satisfy a predicate.
filter :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. Map over elements and collect the Justs.
mapMaybe :: Measured b => (a -> Maybe b) -> MSeq a -> MSeq b
-- | <math>. Map over elements and split the Lefts and
-- Rights.
mapEither :: (Measured b, Measured c) => (a -> Either b c) -> MSeq a -> (MSeq b, MSeq c)
-- | <math>. Keep elements that satisfy an applicative predicate.
filterA :: (Measured a, Applicative f) => (a -> f Bool) -> MSeq a -> f (MSeq a)
-- | <math>. Traverse over elements and collect the Justs.
mapMaybeA :: (Measured b, Applicative f) => (a -> f (Maybe b)) -> MSeq a -> f (MSeq b)
-- | <math>. Traverse over elements and split the Lefts and
-- Rights.
mapEitherA :: (Measured b, Measured c, Applicative f) => (a -> f (Either b c)) -> MSeq a -> f (MSeq b, MSeq c)
-- | <math>. The longest prefix of elements that satisfy a predicate.
-- <math> is the length of the prefix.
takeWhile :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The remainder after removing the longest prefix of
-- elements that satisfy a predicate. <math> is the length of the
-- prefix.
dropWhile :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The longest prefix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the prefix.
--
--
-- span p xs == (takeWhile p xs, dropWhile p xs)
--
span :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. The longest prefix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the prefix.
--
--
-- break p == span (not . p)
--
break :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. The longest suffix of elements that satisfy a predicate.
-- <math> is the length of the suffix.
takeWhileEnd :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The remainder after removing the longest suffix of
-- elements that satisfy a predicate. <math> is the length of the
-- suffix.
dropWhileEnd :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The longest suffix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the suffix.
--
--
-- spanEnd p xs == (dropWhileEnd p xs, takeWhileEnd p xs)
--
spanEnd :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. The longest suffix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the suffix.
--
--
-- breakEnd p == spanEnd (not . p)
--
breakEnd :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. Map over a sequence.
map :: Measured b => (a -> b) -> MSeq a -> MSeq b
-- | <math>. Cartesian product of two sequences.
liftA2 :: Measured c => (a -> b -> c) -> MSeq a -> MSeq b -> MSeq c
-- | <math>. Traverse a sequence.
traverse :: (Measured b, Applicative f) => (a -> f b) -> MSeq a -> f (MSeq b)
-- | <math>. Map over a sequence with index.
imap :: Measured b => (Int -> a -> b) -> MSeq a -> MSeq b
-- | <math>. Traverse a sequence with index.
itraverse :: (Measured b, Applicative f) => (Int -> a -> f b) -> MSeq a -> f (MSeq b)
-- | <math>. Reverse a sequence.
reverse :: Measured a => MSeq a -> MSeq a
-- | <math>. Intersperse an element between the elements of a
-- sequence.
intersperse :: Measured a => a -> MSeq a -> MSeq a
-- | <math>. Like foldl' but keeps all intermediate values.
scanl :: Measured b => (b -> a -> b) -> b -> MSeq a -> MSeq b
-- | <math>. Like foldr' but keeps all intermediate values.
scanr :: Measured b => (a -> b -> b) -> b -> MSeq a -> MSeq b
-- | <math>. Sort a sequence.
sort :: (Ord a, Measured a) => MSeq a -> MSeq a
-- | <math>. Sort a sequence using a comparison function.
sortBy :: Measured a => (a -> a -> Ordering) -> MSeq a -> MSeq a
-- | <math>. The last element satisfying a predicate.
--
-- To get the first element, use Data.Foldable.find.
findEnd :: (a -> Bool) -> MSeq a -> Maybe a
-- | <math>. The index of the first element satisfying a predicate.
findIndex :: (a -> Bool) -> MSeq a -> Maybe Int
-- | <math>. The index of the last element satisfying a predicate.
findIndexEnd :: (a -> Bool) -> MSeq a -> Maybe Int
-- | <math>. Indices in the second sequence where the first sequence
-- begins as a substring. Includes overlapping occurences.
infixIndices :: Eq a => MSeq a -> MSeq a -> [Int]
-- | <math>. Binary search for an element in a sequence.
--
-- Given a function f this function returns an arbitrary element
-- x, if it exists, such that f x = EQ. f must
-- be monotonic on the sequence— specifically fmap f must result
-- in a sequence which has many (possibly zero) LTs, followed by
-- many EQs, followed by many GTs.
binarySearchFind :: (a -> Ordering) -> MSeq a -> Maybe a
-- | <math>. Whether the first sequence is a prefix of the second.
isPrefixOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Whether the first sequence is a suffix of the second.
isSuffixOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Whether the first sequence is a substring of the second.
isInfixOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Whether the first sequence is a subsequence of the
-- second.
isSubsequenceOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Zip two sequences with a function. The result is as long
-- as the shorter sequence.
zipWith :: Measured c => (a -> b -> c) -> MSeq a -> MSeq b -> MSeq c
-- | <math>. Zip three sequences with a function. The result is as
-- long as the shortest sequence.
zipWith3 :: Measured d => (a -> b -> c -> d) -> MSeq a -> MSeq b -> MSeq c -> MSeq d
-- | <math>. Zip two sequences with a monadic function.
zipWithM :: (Measured c, Monad m) => (a -> b -> m c) -> MSeq a -> MSeq b -> m (MSeq c)
-- | <math>. Zip three sequences with a monadic function.
zipWith3M :: (Measured d, Monad m) => (a -> b -> c -> m d) -> MSeq a -> MSeq b -> MSeq c -> m (MSeq d)
-- | <math>. Map over a sequence and unzip the result.
unzipWith :: (Measured b, Measured c) => (a -> (b, c)) -> MSeq a -> (MSeq b, MSeq c)
-- | <math>. Map over a sequence and unzip the result.
unzipWith3 :: (Measured b, Measured c, Measured d) => (a -> (b, c, d)) -> MSeq a -> (MSeq b, MSeq c, MSeq d)
-- | <math>. The summary is the fold of measures of all elements in
-- the sequence. Returns Nothing if the sequence is empty.
--
--
-- summaryMay == foldMap (Just . measure)
--
summaryMay :: Measured a => MSeq a -> Maybe (Measure a)
-- | <math>. The summary is the fold of measures of all elements in
-- the sequence.
--
--
-- summary == foldMap measure
--
summary :: (Measured a, Monoid (Measure a)) => MSeq a -> Measure a
-- | <math>. Perform a binary search on the summaries of the
-- non-empty prefixes of the sequence.
--
-- binarySearchPrefix p xs for a monotonic predicate p
-- returns two adjacent indices i and j, 0 <= i
-- < j < length xs.
--
--
-- - i is the greatest index such that p (fromJust
-- (summaryMay (take (i+1) xs))) is False, or
-- Nothing if there is no such index.
-- - j is the least index such that p (fromJust
-- (summaryMay (take (j+1) xs))) is True, or
-- Nothing if there is no such index.
--
--
-- Examples
--
--
-- import Data.Monoid (Sum(..))
--
-- newtype A = A Int deriving Show
--
-- instance Measured A where
-- type Measure A = Sum Int
-- measure (A x) = Sum x
--
--
--
-- >>> let xs = fromList [A 1, A 2, A 3, A 4]
--
--
-- The summaries of the prefixes of xs by index are:
--
--
-- - 0: measure (A 1) = Sum 1.
-- - 1: measure (A 1) <> measure (A 2) = Sum 3.
-- - 2: measure (A 1) <> measure (A 2) <> measure (A 3)
-- = Sum 6.
-- - 3: measure (A 1) <> measure (A 2) <> measure (A 3)
-- <> measure (A 4) = Sum 10.
--
--
--
-- >>> binarySearchPrefix (> Sum 4) xs
-- (Just 1,Just 2)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- prefix summary: │ Sum 1 │ Sum 3 │ Sum 6 | Sum 10 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 4): │ False │ False │ True │ True │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Just 1 , Just 2 )
--
--
--
-- >>> binarySearchPrefix (> Sum 20) xs
-- (Just 3,Nothing)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- prefix summary: │ Sum 1 │ Sum 3 │ Sum 6 | Sum 10 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 20): │ False │ False │ False │ False │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Just 3 , Nothing )
--
binarySearchPrefix :: Measured a => (Measure a -> Bool) -> MSeq a -> (Maybe Int, Maybe Int)
-- | <math>. Perform a binary search on the summaries of the
-- non-empty suffixes of the sequence.
--
-- binarySearchSuffix p xs for a monotonic predicate p
-- returns two adjacent indices i and j, 0 <= i
-- < j < length xs.
--
--
-- - i is the greatest index such that p (fromJust
-- (summaryMay (drop i xs))) is True, or Nothing
-- if there is no such index.
-- - j is the least index such that p (fromJust
-- (summaryMay (drop j xs))) is False, or Nothing
-- if there is no such index
--
--
-- Examples
--
--
-- import Data.Monoid (Sum(..))
--
-- newtype A = A Int deriving Show
--
-- instance Measured A where
-- type Measure A = Sum Int
-- measure (A x) = Sum x
--
--
--
-- >>> let xs = fromList [A 1, A 2, A 3, A 4]
--
--
-- The summaries of the suffixes of xs by index are:
--
--
-- - 0: measure (A 1) <> measure (A 2) <> measure (A 3)
-- <> measure (A 4) = Sum 10.
-- - 1: measure (A 2) <> measure (A 3) <> measure (A 4)
-- = Sum 9.
-- - 2: measure (A 3) <> measure (A 4) = Sum 7.
-- - 3: measure (A 4) = Sum 4.
--
--
--
-- >>> binarySearchSuffix (> Sum 4) xs
-- (Just 2,Just 3)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- suffix summary: │ Sum 10 │ Sum 9 │ Sum 7 | Sum 4 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 4): │ True │ True │ True │ False │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Just 2 , Just 3 )
--
--
--
-- >>> binarySearchSuffix (> Sum 20) xs
-- (Nothing,Just 0)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- suffix summary: │ Sum 10 │ Sum 9 │ Sum 7 | Sum 4 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 20): │ False │ False │ False │ False │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Nothing , Just 0 )
--
binarySearchSuffix :: Measured a => (Measure a -> Bool) -> MSeq a -> (Maybe Int, Maybe Int)
-- | Reduce a sequence to normal form, given functions to reduce its
-- contents.
liftRnf2 :: (Measure a -> ()) -> (a -> ()) -> MSeq a -> ()
fromMTree :: Measured a => MTree a -> MSeq a
valid :: (Measured a, Eq (Measure a)) => MSeq a -> Bool
debugShowsPrec :: (Show a, Show (Measure a)) => Int -> MSeq a -> ShowS
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Seqn.Internal.MSeq.MSeq a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Seqn.Internal.MSeq.MSeq a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Seqn.Internal.MSeq.MSeq a)
instance (Data.Seqn.Internal.MTree.Measured a, GHC.Read.Read a) => GHC.Read.Read (Data.Seqn.Internal.MSeq.MSeq a)
instance Data.Functor.Classes.Eq1 Data.Seqn.Internal.MSeq.MSeq
instance Data.Functor.Classes.Ord1 Data.Seqn.Internal.MSeq.MSeq
instance Data.Functor.Classes.Show1 Data.Seqn.Internal.MSeq.MSeq
instance Data.Foldable.Foldable Data.Seqn.Internal.MSeq.MSeq
instance Data.Seqn.Internal.MTree.Measured a => GHC.IsList.IsList (Data.Seqn.Internal.MSeq.MSeq a)
instance WithIndex.FoldableWithIndex GHC.Types.Int Data.Seqn.Internal.MSeq.MSeq
instance Data.Seqn.Internal.MTree.Measured a => GHC.Base.Semigroup (Data.Seqn.Internal.MSeq.MSeq a)
instance Data.Seqn.Internal.MTree.Measured a => GHC.Base.Monoid (Data.Seqn.Internal.MSeq.MSeq a)
instance (Control.DeepSeq.NFData (Data.Seqn.Internal.MTree.Measure a), Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Seqn.Internal.MSeq.MSeq a)
-- | Finite measured sequences
--
-- A value of type MSeq a is a sequence with elements of type
-- a. An MSeq is
--
--
-- - Spine-strict, hence finite. MSeq cannot represent
-- infinite sequences.
-- - Value-strict. It is guaranteed that if a MSeq is in
-- weak head normal form (WHNF), every element of the Seq
-- is also in WHNF.
--
--
-- An MSeq provides quick access to the combined "measure" of
-- all elements of the sequence. Please see the Tutorial at the
-- end of this page for an explanation.
--
-- It is recommended to import this module qualified to avoid name
-- clashes.
--
--
-- import Data.Seqn.MSeq (Measured, MSeq)
-- import qualified Data.Seqn.MSeq as MSeq
--
--
-- Warning
--
-- The length of a MSeq must not exceed (maxBound `div` 3)
-- :: Int. If this length is exceeded, the behavior of a
-- MSeq is undefined. This value is very large in practice,
-- greater than <math> on 32-bit systems and <math> on 64-bit
-- systems.
--
-- Implementation
--
-- MSeq is implemented as a weight-balanced binary tree.
-- This structure is described by
--
--
-- - J. Nievergelt and E. M. Reingold, "Binary search trees of
-- bounded balance", SIAM Journal of Computing 2(1), 1973,
-- https://doi.org/10.1137/0202005
-- - Stephen Adams, "Efficient sets—a balancing act", Journal of
-- Functional Programming 3(4), 553-561, 1993,
-- https://doi.org/10.1017/S0956796800000885
-- - Yoichi Hirai and Kazuhiko Yamamoto, "Balancing weight-balanced
-- trees", Journal of Functional Programming 21(3), 287-307, 2011,
-- https://doi.org/10.1017/S0956796811000104
-- - Guy Blelloch, Daniel Ferizovic, and Yihan Sun, "Parallel
-- Ordered Sets Using Join", 2016,
-- https://doi.org/10.48550/arXiv.1602.02120
--
module Data.Seqn.MSeq
-- | A sequence with elements of type a. An instance of
-- Measured a is required for most operations.
data MSeq a
-- | Types that have a combinable property, called the measure.
class Semigroup (Measure a) => Measured a where {
type Measure a;
}
-- | Calculate the measure of a value.
measure :: Measured a => a -> Measure a
-- | <math>. The summary is the fold of measures of all elements in
-- the sequence. Returns Nothing if the sequence is empty.
--
--
-- summaryMay == foldMap (Just . measure)
--
summaryMay :: Measured a => MSeq a -> Maybe (Measure a)
-- | <math>. The summary is the fold of measures of all elements in
-- the sequence.
--
--
-- summary == foldMap measure
--
summary :: (Measured a, Monoid (Measure a)) => MSeq a -> Measure a
-- | <math>. Perform a binary search on the summaries of the
-- non-empty prefixes of the sequence.
--
-- binarySearchPrefix p xs for a monotonic predicate p
-- returns two adjacent indices i and j, 0 <= i
-- < j < length xs.
--
--
-- - i is the greatest index such that p (fromJust
-- (summaryMay (take (i+1) xs))) is False, or
-- Nothing if there is no such index.
-- - j is the least index such that p (fromJust
-- (summaryMay (take (j+1) xs))) is True, or
-- Nothing if there is no such index.
--
--
-- Examples
--
--
-- import Data.Monoid (Sum(..))
--
-- newtype A = A Int deriving Show
--
-- instance Measured A where
-- type Measure A = Sum Int
-- measure (A x) = Sum x
--
--
--
-- >>> let xs = fromList [A 1, A 2, A 3, A 4]
--
--
-- The summaries of the prefixes of xs by index are:
--
--
-- - 0: measure (A 1) = Sum 1.
-- - 1: measure (A 1) <> measure (A 2) = Sum 3.
-- - 2: measure (A 1) <> measure (A 2) <> measure (A 3)
-- = Sum 6.
-- - 3: measure (A 1) <> measure (A 2) <> measure (A 3)
-- <> measure (A 4) = Sum 10.
--
--
--
-- >>> binarySearchPrefix (> Sum 4) xs
-- (Just 1,Just 2)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- prefix summary: │ Sum 1 │ Sum 3 │ Sum 6 | Sum 10 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 4): │ False │ False │ True │ True │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Just 1 , Just 2 )
--
--
--
-- >>> binarySearchPrefix (> Sum 20) xs
-- (Just 3,Nothing)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- prefix summary: │ Sum 1 │ Sum 3 │ Sum 6 | Sum 10 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 20): │ False │ False │ False │ False │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Just 3 , Nothing )
--
binarySearchPrefix :: Measured a => (Measure a -> Bool) -> MSeq a -> (Maybe Int, Maybe Int)
-- | <math>. Perform a binary search on the summaries of the
-- non-empty suffixes of the sequence.
--
-- binarySearchSuffix p xs for a monotonic predicate p
-- returns two adjacent indices i and j, 0 <= i
-- < j < length xs.
--
--
-- - i is the greatest index such that p (fromJust
-- (summaryMay (drop i xs))) is True, or Nothing
-- if there is no such index.
-- - j is the least index such that p (fromJust
-- (summaryMay (drop j xs))) is False, or Nothing
-- if there is no such index
--
--
-- Examples
--
--
-- import Data.Monoid (Sum(..))
--
-- newtype A = A Int deriving Show
--
-- instance Measured A where
-- type Measure A = Sum Int
-- measure (A x) = Sum x
--
--
--
-- >>> let xs = fromList [A 1, A 2, A 3, A 4]
--
--
-- The summaries of the suffixes of xs by index are:
--
--
-- - 0: measure (A 1) <> measure (A 2) <> measure (A 3)
-- <> measure (A 4) = Sum 10.
-- - 1: measure (A 2) <> measure (A 3) <> measure (A 4)
-- = Sum 9.
-- - 2: measure (A 3) <> measure (A 4) = Sum 7.
-- - 3: measure (A 4) = Sum 4.
--
--
--
-- >>> binarySearchSuffix (> Sum 4) xs
-- (Just 2,Just 3)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- suffix summary: │ Sum 10 │ Sum 9 │ Sum 7 | Sum 4 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 4): │ True │ True │ True │ False │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Just 2 , Just 3 )
--
--
--
-- >>> binarySearchSuffix (> Sum 20) xs
-- (Nothing,Just 0)
--
--
--
-- ╭──────────┬──────────┬──────────┬──────────╮
-- index: │ 0 │ 1 │ 2 │ 3 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- suffix summary: │ Sum 10 │ Sum 9 │ Sum 7 | Sum 4 │
-- ├──────────┼──────────┼──────────┼──────────┤
-- (> Sum 20): │ False │ False │ False │ False │
-- ╰──────────┴──────────┴──────────┴──────────╯
-- result: ( Nothing , Just 0 )
--
binarySearchSuffix :: Measured a => (Measure a -> Bool) -> MSeq a -> (Maybe Int, Maybe Int)
-- | The empty sequence.
empty :: MSeq a
-- | A singleton sequence.
singleton :: a -> MSeq a
-- | <math>. Create an MSeq from a list.
fromList :: Measured a => [a] -> MSeq a
-- | <math>. Create an MSeq from a reversed list.
fromRevList :: Measured a => [a] -> MSeq a
-- | <math>. A sequence with a repeated element. If the length is
-- negative, empty is returned.
replicate :: Measured a => Int -> a -> MSeq a
-- | <math>. Generate a sequence from a length and an applicative
-- action. If the length is negative, empty is returned.
replicateA :: (Measured a, Applicative f) => Int -> f a -> f (MSeq a)
-- | <math>. Generate a sequence from a length and a generator. If
-- the length is negative, empty is returned.
generate :: Measured a => Int -> (Int -> a) -> MSeq a
-- | <math>. Generate a sequence from a length and an applicative
-- generator. If the length is negative, empty is returned.
generateA :: (Measured a, Applicative f) => Int -> (Int -> f a) -> f (MSeq a)
-- | <math>. Unfold a sequence from left to right.
unfoldr :: Measured a => (b -> Maybe (a, b)) -> b -> MSeq a
-- | <math>. Unfold a sequence from right to left.
unfoldl :: Measured a => (b -> Maybe (b, a)) -> b -> MSeq a
-- | <math>. Unfold a sequence monadically from left to right.
unfoldrM :: (Measured a, Monad m) => (b -> m (Maybe (a, b))) -> b -> m (MSeq a)
-- | <math>. Unfold a sequence monadically from right to left.
unfoldlM :: (Measured a, Monad m) => (b -> m (Maybe (b, a))) -> b -> m (MSeq a)
-- | <math>. Map over a Foldable and concatenate the
-- results.
concatMap :: (Measured b, Foldable f) => (a -> MSeq b) -> f a -> MSeq b
-- | Monadic fixed point. See Control.Monad.Fix.
mfix :: Measured a => (a -> MSeq a) -> MSeq a
-- | <math>. Convert to a list in reverse.
--
-- To convert to a list without reversing, use
-- Data.Foldable.toList.
toRevList :: MSeq a -> [a]
-- | <math>. Look up the element at an index.
lookup :: Int -> MSeq a -> Maybe a
-- | <math>. Look up the element at an index. Calls error if
-- the index is out of bounds.
index :: Int -> MSeq a -> a
-- | <math>. Infix version of lookup.
(!?) :: MSeq a -> Int -> Maybe a
-- | <math>. Infix version of index. Calls error if
-- the index is out of bounds.
(!) :: MSeq a -> Int -> a
-- | <math>. Update an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
update :: Measured a => Int -> a -> MSeq a -> MSeq a
-- | <math>. Adjust the element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
adjust :: Measured a => (a -> a) -> Int -> MSeq a -> MSeq a
-- | <math>. Insert an element at an index. If the index is out of
-- bounds, the element is added to the closest end of the sequence.
insertAt :: Measured a => Int -> a -> MSeq a -> MSeq a
-- | <math>. Delete an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
deleteAt :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Append a value to the beginning of a sequence.
cons :: Measured a => a -> MSeq a -> MSeq a
-- | <math>. Append a value to the end of a sequence.
snoc :: Measured a => MSeq a -> a -> MSeq a
-- | <math>. The head and tail of a sequence.
uncons :: Measured a => MSeq a -> Maybe (a, MSeq a)
-- | <math>. The init and last of a sequence.
unsnoc :: Measured a => MSeq a -> Maybe (MSeq a, a)
-- | <math>. Take a number of elements from the beginning of a
-- sequence.
take :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Drop a number of elements from the beginning of a
-- sequence.
drop :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. The slice of a sequence between two indices (inclusive).
slice :: Measured a => (Int, Int) -> MSeq a -> MSeq a
-- | <math>. Split a sequence at a given index.
--
--
-- splitAt n xs == (take n xs, drop n xs)
--
splitAt :: Measured a => Int -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. Take a number of elements from the end of a sequence.
takeEnd :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Drop a number of elements from the end of a sequence.
dropEnd :: Measured a => Int -> MSeq a -> MSeq a
-- | <math>. Split a sequence at a given index from the end.
--
--
-- splitAtEnd n xs == (dropEnd n xs, takeEnd n xs)
--
splitAtEnd :: Measured a => Int -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. Keep elements that satisfy a predicate.
filter :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. Map over elements and collect the Justs.
mapMaybe :: Measured b => (a -> Maybe b) -> MSeq a -> MSeq b
-- | <math>. Map over elements and split the Lefts and
-- Rights.
mapEither :: (Measured b, Measured c) => (a -> Either b c) -> MSeq a -> (MSeq b, MSeq c)
-- | <math>. Keep elements that satisfy an applicative predicate.
filterA :: (Measured a, Applicative f) => (a -> f Bool) -> MSeq a -> f (MSeq a)
-- | <math>. Traverse over elements and collect the Justs.
mapMaybeA :: (Measured b, Applicative f) => (a -> f (Maybe b)) -> MSeq a -> f (MSeq b)
-- | <math>. Traverse over elements and split the Lefts and
-- Rights.
mapEitherA :: (Measured b, Measured c, Applicative f) => (a -> f (Either b c)) -> MSeq a -> f (MSeq b, MSeq c)
-- | <math>. The longest prefix of elements that satisfy a predicate.
-- <math> is the length of the prefix.
takeWhile :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The remainder after removing the longest prefix of
-- elements that satisfy a predicate. <math> is the length of the
-- prefix.
dropWhile :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The longest prefix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the prefix.
--
--
-- span p xs == (takeWhile p xs, dropWhile p xs)
--
span :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. The longest prefix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the prefix.
--
--
-- break p == span (not . p)
--
break :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. The longest suffix of elements that satisfy a predicate.
-- <math> is the length of the suffix.
takeWhileEnd :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The remainder after removing the longest suffix of
-- elements that satisfy a predicate. <math> is the length of the
-- suffix.
dropWhileEnd :: Measured a => (a -> Bool) -> MSeq a -> MSeq a
-- | <math>. The longest suffix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the suffix.
--
--
-- spanEnd p xs == (dropWhileEnd p xs, takeWhileEnd p xs)
--
spanEnd :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. The longest suffix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the suffix.
--
--
-- breakEnd p == spanEnd (not . p)
--
breakEnd :: Measured a => (a -> Bool) -> MSeq a -> (MSeq a, MSeq a)
-- | <math>. Map over a sequence.
map :: Measured b => (a -> b) -> MSeq a -> MSeq b
-- | <math>. Cartesian product of two sequences.
liftA2 :: Measured c => (a -> b -> c) -> MSeq a -> MSeq b -> MSeq c
-- | <math>. Traverse a sequence.
traverse :: (Measured b, Applicative f) => (a -> f b) -> MSeq a -> f (MSeq b)
-- | <math>. Map over a sequence with index.
imap :: Measured b => (Int -> a -> b) -> MSeq a -> MSeq b
-- | <math>. Traverse a sequence with index.
itraverse :: (Measured b, Applicative f) => (Int -> a -> f b) -> MSeq a -> f (MSeq b)
-- | <math>. Reverse a sequence.
reverse :: Measured a => MSeq a -> MSeq a
-- | <math>. Intersperse an element between the elements of a
-- sequence.
intersperse :: Measured a => a -> MSeq a -> MSeq a
-- | <math>. Like foldl' but keeps all intermediate values.
scanl :: Measured b => (b -> a -> b) -> b -> MSeq a -> MSeq b
-- | <math>. Like foldr' but keeps all intermediate values.
scanr :: Measured b => (a -> b -> b) -> b -> MSeq a -> MSeq b
-- | <math>. Sort a sequence.
sort :: (Ord a, Measured a) => MSeq a -> MSeq a
-- | <math>. Sort a sequence using a comparison function.
sortBy :: Measured a => (a -> a -> Ordering) -> MSeq a -> MSeq a
-- | <math>. The last element satisfying a predicate.
--
-- To get the first element, use Data.Foldable.find.
findEnd :: (a -> Bool) -> MSeq a -> Maybe a
-- | <math>. The index of the first element satisfying a predicate.
findIndex :: (a -> Bool) -> MSeq a -> Maybe Int
-- | <math>. The index of the last element satisfying a predicate.
findIndexEnd :: (a -> Bool) -> MSeq a -> Maybe Int
-- | <math>. Indices in the second sequence where the first sequence
-- begins as a substring. Includes overlapping occurences.
infixIndices :: Eq a => MSeq a -> MSeq a -> [Int]
-- | <math>. Binary search for an element in a sequence.
--
-- Given a function f this function returns an arbitrary element
-- x, if it exists, such that f x = EQ. f must
-- be monotonic on the sequence— specifically fmap f must result
-- in a sequence which has many (possibly zero) LTs, followed by
-- many EQs, followed by many GTs.
binarySearchFind :: (a -> Ordering) -> MSeq a -> Maybe a
-- | <math>. Whether the first sequence is a prefix of the second.
isPrefixOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Whether the first sequence is a suffix of the second.
isSuffixOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Whether the first sequence is a substring of the second.
isInfixOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Whether the first sequence is a subsequence of the
-- second.
isSubsequenceOf :: Eq a => MSeq a -> MSeq a -> Bool
-- | <math>. Zip two sequences with a function. The result is as long
-- as the shorter sequence.
zipWith :: Measured c => (a -> b -> c) -> MSeq a -> MSeq b -> MSeq c
-- | <math>. Zip three sequences with a function. The result is as
-- long as the shortest sequence.
zipWith3 :: Measured d => (a -> b -> c -> d) -> MSeq a -> MSeq b -> MSeq c -> MSeq d
-- | <math>. Zip two sequences with a monadic function.
zipWithM :: (Measured c, Monad m) => (a -> b -> m c) -> MSeq a -> MSeq b -> m (MSeq c)
-- | <math>. Zip three sequences with a monadic function.
zipWith3M :: (Measured d, Monad m) => (a -> b -> c -> m d) -> MSeq a -> MSeq b -> MSeq c -> m (MSeq d)
-- | <math>. Map over a sequence and unzip the result.
unzipWith :: (Measured b, Measured c) => (a -> (b, c)) -> MSeq a -> (MSeq b, MSeq c)
-- | <math>. Map over a sequence and unzip the result.
unzipWith3 :: (Measured b, Measured c, Measured d) => (a -> (b, c, d)) -> MSeq a -> (MSeq b, MSeq c, MSeq d)
-- | Reduce a sequence to normal form, given functions to reduce its
-- contents.
liftRnf2 :: (Measure a -> ()) -> (a -> ()) -> MSeq a -> ()
-- | This is an internal module. You probably don't need to import this.
-- Use Data.Seqn.PQueue instead.
--
-- WARNING
--
-- Definitions in this module allow violating invariants that would
-- otherwise be guaranteed by Data.Seqn.PQueue. Use at your own
-- risk!
module Data.Seqn.Internal.PQueue
-- | A minimum priority queue.
--
-- PQueue can be used as a maximum priority queue by wrapping
-- its elements with Down.
newtype PQueue a
PQueue :: MSeq (Elem a) -> PQueue a
newtype Elem a
Elem :: a -> Elem a
newtype Min a
Min :: a -> Min a
-- | The empty queue.
empty :: PQueue a
-- | A singleton queue.
singleton :: a -> PQueue a
-- | <math>. Create a queue from a list.
fromList :: Ord a => [a] -> PQueue a
-- | <math>. Map over a Foldable and concatenate the
-- results.
concatMap :: (Ord b, Foldable f) => (a -> PQueue b) -> f a -> PQueue b
-- | <math>. Insert an element into the queue.
--
-- Note: When inserting multiple elements, it is more efficient to
-- concatenate a fresh queue rather than repeatedly insert elements.
--
--
-- q <> fromList xs -- Good
-- foldl' (flip insert) q xs -- Worse
--
insert :: Ord a => a -> PQueue a -> PQueue a
-- | <math>. The minimum element in the queue.
min :: Ord a => PQueue a -> Maybe a
-- | <math>. The minimum element in the queue, with the rest of the
-- queue.
minView :: Ord a => PQueue a -> Maybe (a, PQueue a)
-- | <math>. Convert to a sorted list.
toSortedList :: Ord a => PQueue a -> [a]
-- | A priority associated with a value. A PQueue (Entry k a) may
-- be used when the priority is separate from the value.
data Entry k a
Entry :: !k -> a -> Entry k a
-- | The priority.
entryPrio :: Entry k a -> k
-- | The value.
entryValue :: Entry k a -> a
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Seqn.Internal.PQueue.Elem a)
instance GHC.Read.Read a => GHC.Read.Read (Data.Seqn.Internal.PQueue.Elem a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Seqn.Internal.PQueue.Elem a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Seqn.Internal.PQueue.Elem a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Seqn.Internal.PQueue.Elem a)
instance (GHC.Classes.Ord a, GHC.Read.Read a) => GHC.Read.Read (Data.Seqn.Internal.PQueue.PQueue a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Seqn.Internal.PQueue.PQueue a)
instance GHC.Classes.Ord a => GHC.Base.Monoid (Data.Seqn.Internal.PQueue.PQueue a)
instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.Seqn.Internal.PQueue.PQueue a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Seqn.Internal.PQueue.PQueue a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Seqn.Internal.PQueue.PQueue a)
instance GHC.Base.Functor (Data.Seqn.Internal.PQueue.Entry k)
instance (GHC.Read.Read k, GHC.Read.Read a) => GHC.Read.Read (Data.Seqn.Internal.PQueue.Entry k a)
instance (GHC.Show.Show k, GHC.Show.Show a) => GHC.Show.Show (Data.Seqn.Internal.PQueue.Entry k a)
instance GHC.Classes.Eq k => GHC.Classes.Eq (Data.Seqn.Internal.PQueue.Entry k a)
instance GHC.Classes.Ord k => GHC.Classes.Ord (Data.Seqn.Internal.PQueue.Entry k a)
instance (Control.DeepSeq.NFData k, Control.DeepSeq.NFData a) => Control.DeepSeq.NFData (Data.Seqn.Internal.PQueue.Entry k a)
instance Data.Functor.Classes.Eq1 Data.Seqn.Internal.PQueue.PQueue
instance Data.Functor.Classes.Ord1 Data.Seqn.Internal.PQueue.PQueue
instance Data.Functor.Classes.Show1 Data.Seqn.Internal.PQueue.PQueue
instance Data.Foldable.Foldable Data.Seqn.Internal.PQueue.PQueue
instance WithIndex.FoldableWithIndex GHC.Types.Int Data.Seqn.Internal.PQueue.PQueue
instance GHC.Classes.Ord a => GHC.IsList.IsList (Data.Seqn.Internal.PQueue.PQueue a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Seqn.Internal.PQueue.PQueue a)
instance Control.DeepSeq.NFData1 Data.Seqn.Internal.PQueue.PQueue
instance GHC.Classes.Ord a => Data.Seqn.Internal.MTree.Measured (Data.Seqn.Internal.PQueue.Elem a)
instance GHC.Classes.Ord a => GHC.Base.Semigroup (Data.Seqn.Internal.PQueue.Min a)
instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Seqn.Internal.PQueue.Min a)
instance Control.DeepSeq.NFData1 Data.Seqn.Internal.PQueue.Min
-- | Priority queues
--
-- PQueue is a minimum priority queue implemented using an
-- MSeq.
--
--
-- - It is spine-strict, and can contain only a finite number of
-- elements.
-- - It is value-strict. It is guaranteed that if a PQueue is
-- in weak head normal form (WHNF), every element of the
-- PQueue is also in WHNF.
-- - It maintains insertion order. If two elements compare equal, the
-- one which was inserted first will be removed first. Elements can also
-- be folded over in insertion order.
-- - It is a mergeable priority queue. Two queues can be concatenated
-- efficiently in logarithmic time.
--
--
-- It is recommended to import this module qualified to avoid name
-- clashes.
--
--
-- import Data.Seqn.PQueue (PQueue)
-- import qualified Data.Seqn.PQueue as PQueue
--
module Data.Seqn.PQueue
-- | A minimum priority queue.
--
-- PQueue can be used as a maximum priority queue by wrapping
-- its elements with Down.
data PQueue a
-- | The empty queue.
empty :: PQueue a
-- | A singleton queue.
singleton :: a -> PQueue a
-- | <math>. Create a queue from a list.
fromList :: Ord a => [a] -> PQueue a
-- | <math>. Map over a Foldable and concatenate the
-- results.
concatMap :: (Ord b, Foldable f) => (a -> PQueue b) -> f a -> PQueue b
-- | <math>. Insert an element into the queue.
--
-- Note: When inserting multiple elements, it is more efficient to
-- concatenate a fresh queue rather than repeatedly insert elements.
--
--
-- q <> fromList xs -- Good
-- foldl' (flip insert) q xs -- Worse
--
insert :: Ord a => a -> PQueue a -> PQueue a
-- | <math>. The minimum element in the queue.
min :: Ord a => PQueue a -> Maybe a
-- | <math>. The minimum element in the queue, with the rest of the
-- queue.
minView :: Ord a => PQueue a -> Maybe (a, PQueue a)
-- | <math>. Convert to a sorted list.
toSortedList :: Ord a => PQueue a -> [a]
-- | A priority associated with a value. A PQueue (Entry k a) may
-- be used when the priority is separate from the value.
data Entry k a
Entry :: !k -> a -> Entry k a
-- | The priority.
entryPrio :: Entry k a -> k
-- | The value.
entryValue :: Entry k a -> a
-- | Finite sequences
--
-- A value of type Seq a is a sequence with elements of type
-- a. A Seq is
--
--
-- - Spine-strict, hence finite. Seq cannot represent infinite
-- sequences.
-- - Value-strict. It is guaranteed that if a Seq is in
-- weak head normal form (WHNF), every element of the Seq
-- is also in WHNF.
--
--
-- It is recommended to import this module qualified to avoid name
-- clashes.
--
--
-- import Data.Seqn.Seq (Seq)
-- import qualified Data.Seqn.Seq as Seq
--
--
-- Warning
--
-- The length of a Seq must not exceed (maxBound `div` 3) ::
-- Int. If this length is exceeded, the behavior of a Seq
-- is undefined. This value is very large in practice, greater than
-- <math> on 32-bit systems and <math> on 64-bit systems.
--
-- Implementation
--
-- Seq is implemented as a weight-balanced binary tree.
-- This structure is described by
--
--
-- - J. Nievergelt and E. M. Reingold, "Binary search trees of
-- bounded balance", SIAM Journal of Computing 2(1), 1973,
-- https://doi.org/10.1137/0202005
-- - Stephen Adams, "Efficient sets—a balancing act", Journal of
-- Functional Programming 3(4), 553-561, 1993,
-- https://doi.org/10.1017/S0956796800000885
-- - Yoichi Hirai and Kazuhiko Yamamoto, "Balancing weight-balanced
-- trees", Journal of Functional Programming 21(3), 287-307, 2011,
-- https://doi.org/10.1017/S0956796811000104
-- - Guy Blelloch, Daniel Ferizovic, and Yihan Sun, "Parallel
-- Ordered Sets Using Join", 2016,
-- https://doi.org/10.48550/arXiv.1602.02120
--
module Data.Seqn.Seq
-- | A sequence with elements of type a.
data Seq a
-- | The empty sequence.
empty :: Seq a
-- | A singleton sequence.
singleton :: a -> Seq a
-- | <math>. Create a Seq from a list.
--
-- Examples
--
--
-- >>> fromList [8,1,19,11,5,12,12]
-- [8,1,19,11,5,12,12]
--
fromList :: [a] -> Seq a
-- | <math>. Create a Seq from a reversed list.
--
-- Examples
--
--
-- >>> fromRevList "!olleH"
-- "Hello!"
--
fromRevList :: [a] -> Seq a
-- | <math>. A sequence with a repeated element. If the length is
-- negative, empty is returned.
--
-- Examples
--
--
-- >>> replicate 3 "ha"
-- ["ha","ha","ha"]
--
replicate :: Int -> a -> Seq a
-- | <math>. Generate a sequence from a length and an applicative
-- action. If the length is negative, empty is returned.
--
-- Examples
--
--
-- >>> import System.Random (randomIO)
--
-- >>> import Data.Word (Word8)
--
-- >>> replicateA 5 (randomIO :: IO Word8)
-- [26,134,30,58,221]
--
replicateA :: Applicative f => Int -> f a -> f (Seq a)
-- | <math>. Generate a sequence from a length and a generator. If
-- the length is negative, empty is returned.
--
-- Examples
--
--
-- >>> generate 4 (10*)
-- [0,10,20,30]
--
generate :: Int -> (Int -> a) -> Seq a
-- | <math>. Generate a sequence from a length and an applicative
-- generator. If the length is negative, empty is returned.
generateA :: Applicative f => Int -> (Int -> f a) -> f (Seq a)
-- | <math>. Unfold a sequence from left to right.
--
-- Examples
--
--
-- >>> let f (i,a,b) = if i >= 10 then Nothing else Just (a, (i+1, b, a+b))
--
-- >>> unfoldr f (0,0,1)
-- [0,1,1,2,3,5,8,13,21,34]
--
unfoldr :: (b -> Maybe (a, b)) -> b -> Seq a
-- | <math>. Unfold a sequence from right to left.
--
-- Examples
--
--
-- >>> let f i = if i <= 0 then Nothing else Just (i `div` 2, i)
--
-- >>> unfoldl f 1024
-- [1,2,4,8,16,32,64,128,256,512,1024]
--
unfoldl :: (b -> Maybe (b, a)) -> b -> Seq a
-- | <math>. Unfold a sequence monadically from left to right.
unfoldrM :: Monad m => (b -> m (Maybe (a, b))) -> b -> m (Seq a)
-- | <math>. Unfold a sequence monadically from right to left.
unfoldlM :: Monad m => (b -> m (Maybe (b, a))) -> b -> m (Seq a)
-- | <math>. Map over a Foldable and concatenate the
-- results.
--
-- Examples
--
--
-- >>> concatMap (uncurry replicate) [(1,'H'),(1,'e'),(2,'l'),(1,'o')]
-- "Hello"
--
concatMap :: Foldable f => (a -> Seq b) -> f a -> Seq b
-- | <math>. Convert to a list in reverse.
--
-- To convert to a list without reversing, use
-- Data.Foldable.toList.
--
-- Examples
--
--
-- >>> toRevList (fromList "!olleH")
-- "Hello!"
--
toRevList :: Seq a -> [a]
-- | <math>. Look up the element at an index.
--
-- Examples
--
--
-- >>> lookup 3 (fromList "haskell")
-- Just 'k'
--
-- >>> lookup (-1) (singleton 7)
-- Nothing
--
lookup :: Int -> Seq a -> Maybe a
-- | <math>. Look up the element at an index. Calls error if
-- the index is out of bounds.
--
-- Examples
--
--
-- >>> index 3 (fromList "haskell")
-- 'k'
--
-- >>> index (-1) (singleton 7)
-- *** Exception: ...
--
index :: Int -> Seq a -> a
-- | <math>. Infix version of lookup.
(!?) :: Seq a -> Int -> Maybe a
-- | <math>. Infix version of index. Calls error if
-- the index is out of bounds.
(!) :: Seq a -> Int -> a
-- | <math>. Update an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
--
-- Examples
--
--
-- >>> update 3 'b' (fromList "bird")
-- "birb"
--
-- >>> update 3 True (singleton False)
-- [False]
--
update :: Int -> a -> Seq a -> Seq a
-- | <math>. Adjust the element at an index. If the index is out of
-- bounds the sequence is returned unchanged.
--
-- Examples
--
--
-- >>> adjust Data.List.reverse 1 (fromList ["Hello", "ereht"])
-- ["Hello","there"]
--
-- >>> adjust (*100) (-1) (singleton 7)
-- [7]
--
adjust :: (a -> a) -> Int -> Seq a -> Seq a
-- | <math>. Insert an element at an index. If the index is out of
-- bounds, the element is added to the closest end of the sequence.
--
-- Examples
--
--
-- >>> insertAt 1 'a' (fromList "ct")
-- "cat"
--
-- >>> insertAt (-10) 0 (fromList [5,6,7])
-- [0,5,6,7]
--
-- >>> insertAt 10 0 (fromList [5,6,7])
-- [5,6,7,0]
--
insertAt :: Int -> a -> Seq a -> Seq a
-- | <math>. Delete an element at an index. If the index is out of
-- bounds, the sequence is returned unchanged.
--
-- Examples
--
--
-- >>> deleteAt 2 (fromList "cart")
-- "cat"
--
-- >>> deleteAt 10 (fromList [5,6,7])
-- [5,6,7]
--
deleteAt :: Int -> Seq a -> Seq a
-- | <math>. Append a value to the beginning of a sequence.
--
-- Examples
--
--
-- >>> cons 1 (fromList [2,3])
-- [1,2,3]
--
cons :: a -> Seq a -> Seq a
-- | <math>. Append a value to the end of a sequence.
--
-- Examples
--
--
-- >>> snoc (fromList [1,2]) 3
-- [1,2,3]
--
snoc :: Seq a -> a -> Seq a
-- | <math>. The head and tail of a sequence.
--
-- Examples
--
--
-- >>> uncons (fromList [1,2,3])
-- Just (1,[2,3])
--
-- >>> uncons empty
-- Nothing
--
uncons :: Seq a -> Maybe (a, Seq a)
-- | <math>. The init and last of a sequence.
--
-- Examples
--
--
-- >>> unsnoc (fromList [1,2,3])
-- Just ([1,2],3)
--
-- >>> unsnoc empty
-- Nothing
--
unsnoc :: Seq a -> Maybe (Seq a, a)
-- | <math>. Take a number of elements from the beginning of a
-- sequence.
--
-- Examples
--
--
-- >>> take 3 (fromList "haskell")
-- "has"
--
-- >>> take (-1) (fromList [1,2,3])
-- []
--
-- >>> take 10 (fromList [1,2,3])
-- [1,2,3]
--
take :: Int -> Seq a -> Seq a
-- | <math>. Drop a number of elements from the beginning of a
-- sequence.
--
-- Examples
--
--
-- >>> drop 3 (fromList "haskell")
-- "kell"
--
-- >>> drop (-1) (fromList [1,2,3])
-- [1,2,3]
--
-- >>> drop 10 (fromList [1,2,3])
-- []
--
drop :: Int -> Seq a -> Seq a
-- | <math>. The slice of a sequence between two indices (inclusive).
--
-- Examples
--
--
-- >>> slice (1,3) (fromList "haskell")
-- "ask"
--
-- >>> slice (-10,2) (fromList [1,2,3,4,5])
-- [1,2,3]
--
-- >>> slice (2,1) (fromList [1,2,3,4,5])
-- []
--
slice :: (Int, Int) -> Seq a -> Seq a
-- | <math>. Split a sequence at a given index.
--
--
-- splitAt n xs == (take n xs, drop n xs)
--
--
-- Examples
--
--
-- >>> splitAt 3 (fromList "haskell")
-- ("has","kell")
--
-- >>> splitAt (-1) (fromList [1,2,3])
-- ([],[1,2,3])
--
-- >>> splitAt 10 (fromList [1,2,3])
-- ([1,2,3],[])
--
splitAt :: Int -> Seq a -> (Seq a, Seq a)
-- | <math>. Take a number of elements from the end of a sequence.
takeEnd :: Int -> Seq a -> Seq a
-- | <math>. Drop a number of elements from the end of a sequence.
dropEnd :: Int -> Seq a -> Seq a
-- | <math>. Split a sequence at a given index from the end.
--
--
-- splitAtEnd n xs == (dropEnd n xs, takeEnd n xs)
--
splitAtEnd :: Int -> Seq a -> (Seq a, Seq a)
-- | <math>. All suffixes of a sequence, longest first.
--
-- Examples
--
--
-- >>> tails (fromList [1,2,3])
-- [[1,2,3],[2,3],[3],[]]
--
tails :: Seq a -> Seq (Seq a)
-- | <math>. All prefixes of a sequence, shortest first.
--
-- Examples
--
--
-- >>> inits (fromList [1,2,3])
-- [[],[1],[1,2],[1,2,3]]
--
inits :: Seq a -> Seq (Seq a)
-- | <math>. Split a sequence into chunks of the given length
-- c. If c <= 0, empty is returned.
--
-- Examples
--
--
-- >>> chunksOf 3 (fromList [1..10])
-- [[1,2,3],[4,5,6],[7,8,9],[10]]
--
-- >>> chunksOf 10 (fromList "hello")
-- ["hello"]
--
-- >>> chunksOf (-1) (singleton 7)
-- []
--
chunksOf :: Int -> Seq a -> Seq (Seq a)
-- | <math>. Keep elements that satisfy a predicate.
--
-- Examples
--
--
-- >>> filter even (fromList [1..10])
-- [2,4,6,8,10]
--
filter :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. Keep the Justs in a sequence.
--
-- Examples
--
--
-- >>> catMaybes (fromList [Just 1, Nothing, Nothing, Just 10, Just 100])
-- [1,10,100]
--
catMaybes :: Seq (Maybe a) -> Seq a
-- | <math>. Map over elements and collect the Justs.
mapMaybe :: (a -> Maybe b) -> Seq a -> Seq b
-- | <math>. Map over elements and split the Lefts and
-- Rights.
--
-- Examples
--
--
-- >>> mapEither (\x -> if odd x then Left x else Right x) (fromList [1..10])
-- ([1,3,5,7,9],[2,4,6,8,10])
--
mapEither :: (a -> Either b c) -> Seq a -> (Seq b, Seq c)
-- | <math>. Keep elements that satisfy an applicative predicate.
filterA :: Applicative f => (a -> f Bool) -> Seq a -> f (Seq a)
-- | <math>. Traverse over elements and collect the Justs.
mapMaybeA :: Applicative f => (a -> f (Maybe b)) -> Seq a -> f (Seq b)
-- | <math>. Traverse over elements and split the Lefts and
-- Rights.
mapEitherA :: Applicative f => (a -> f (Either b c)) -> Seq a -> f (Seq b, Seq c)
-- | <math>. The longest prefix of elements that satisfy a predicate.
-- <math> is the length of the prefix.
--
-- Examples
--
--
-- >>> takeWhile even (fromList [2,4,6,1,3,2,4])
-- [2,4,6]
--
takeWhile :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The remainder after removing the longest prefix of
-- elements that satisfy a predicate. <math> is the length of the
-- prefix.
--
-- Examples
--
--
-- >>> dropWhile even (fromList [2,4,6,1,3,2,4])
-- [1,3,2,4]
--
dropWhile :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The longest prefix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the prefix.
--
--
-- span p xs == (takeWhile p xs, dropWhile p xs)
--
--
-- Examples
--
--
-- >>> span even (fromList [2,4,6,1,3,2,4])
-- ([2,4,6],[1,3,2,4])
--
span :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. The longest prefix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the prefix.
--
--
-- break p == span (not . p)
--
--
-- Examples
--
--
-- >>> break odd (fromList [2,4,6,1,3,2,4])
-- ([2,4,6],[1,3,2,4])
--
break :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. The longest suffix of elements that satisfy a predicate.
-- <math> is the length of the suffix.
takeWhileEnd :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The remainder after removing the longest suffix of
-- elements that satisfy a predicate. <math> is the length of the
-- suffix.
dropWhileEnd :: (a -> Bool) -> Seq a -> Seq a
-- | <math>. The longest suffix of elements that satisfy a predicate,
-- together with the remainder of the sequence. <math> is the
-- length of the suffix.
--
--
-- spanEnd p xs == (dropWhileEnd p xs, takeWhileEnd p xs)
--
spanEnd :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. The longest suffix of elements that do not
-- satisfy a predicate, together with the remainder of the sequence.
-- <math> is the length of the suffix.
--
--
-- breakEnd p == spanEnd (not . p)
--
breakEnd :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
-- | <math>. Reverse a sequence.
--
-- Examples
--
--
-- >>> reverse (fromList [1,2,3,4,5])
-- [5,4,3,2,1]
--
reverse :: Seq a -> Seq a
-- | <math>. Intersperse an element between the elements of a
-- sequence.
--
-- Examples
--
--
-- >>> intersperse '.' (fromList "HELLO")
-- "H.E.L.L.O"
--
intersperse :: a -> Seq a -> Seq a
-- | <math>. Like foldl' but keeps all intermediate values.
--
-- Examples
--
--
-- >>> scanl (+) 0 (fromList [1..5])
-- [0,1,3,6,10,15]
--
scanl :: (b -> a -> b) -> b -> Seq a -> Seq b
-- | <math>. Like foldr' but keeps all intermediate values.
--
-- Examples
--
--
-- >>> scanr (+) 0 (fromList [1..5])
-- [15,14,12,9,5,0]
--
scanr :: (a -> b -> b) -> b -> Seq a -> Seq b
-- | <math>. Sort a sequence. The sort is stable.
--
-- Examples
--
--
-- >>> sort (fromList [4,2,3,5,1])
-- [1,2,3,4,5]
--
sort :: Ord a => Seq a -> Seq a
-- | <math>. Sort a sequence using a comparison function. The sort is
-- stable.
--
-- Examples
--
--
-- >>> import Data.Ord (Down, comparing)
--
-- >>> sortBy (comparing Down) (fromList [4,2,3,5,1])
-- [5,4,3,2,1]
--
sortBy :: (a -> a -> Ordering) -> Seq a -> Seq a
-- | <math>. The last element satisfying a predicate.
--
-- To get the first element, use Data.Foldable.find.
findEnd :: (a -> Bool) -> Seq a -> Maybe a
-- | <math>. The index of the first element satisfying a predicate.
--
-- Examples
--
--
-- >>> findIndex even (fromList [1..5])
-- Just 1
--
-- >>> findIndex (<0) (fromList [1..5])
-- Nothing
--
findIndex :: (a -> Bool) -> Seq a -> Maybe Int
-- | <math>. The index of the last element satisfying a predicate.
findIndexEnd :: (a -> Bool) -> Seq a -> Maybe Int
-- | <math>. Indices in the second sequence where the first sequence
-- begins as a substring. Includes overlapping occurences.
--
-- Examples
--
--
-- >>> infixIndices (fromList "ana") (fromList "banana")
-- [1,3]
--
-- >>> infixIndices (fromList [0]) (fromList [1,2,3])
-- []
--
-- >>> infixIndices (fromList "") (fromList "abc")
-- [0,1,2,3]
--
infixIndices :: Eq a => Seq a -> Seq a -> [Int]
-- | <math>. Binary search for an element in a sequence.
--
-- Given a function f this function returns an arbitrary element
-- x, if it exists, such that f x = EQ. f must
-- be monotonic on the sequence— specifically fmap f must result
-- in a sequence which has many (possibly zero) LTs, followed by
-- many EQs, followed by many GTs.
--
-- Examples
--
--
-- >>> binarySearchFind (`compare` 8) (fromList [2,4..10])
-- Just 8
--
-- >>> binarySearchFind (`compare` 3) (fromList [2,4..10])
-- Nothing
--
binarySearchFind :: (a -> Ordering) -> Seq a -> Maybe a
-- | <math>. Whether the first sequence is a prefix of the second.
--
-- Examples
--
--
-- >>> fromList "has" `isPrefixOf` fromList "haskell"
-- True
--
-- >>> fromList "ask" `isPrefixOf` fromList "haskell"
-- False
--
isPrefixOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Whether the first sequence is a suffix of the second.
--
-- Examples
--
--
-- >>> fromList "ell" `isSuffixOf` fromList "haskell"
-- True
--
-- >>> fromList "ask" `isSuffixOf` fromList "haskell"
-- False
--
isSuffixOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Whether the first sequence is a substring of the second.
--
-- Examples
--
--
-- >>> fromList "meow" `isInfixOf` fromList "homeowner"
-- True
--
-- >>> fromList [2,4] `isInfixOf` fromList [2,3,4]
-- False
--
isInfixOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Whether the first sequence is a subsequence of the
-- second.
--
-- Examples
--
--
-- >>> fromList [2,4] `isSubsequenceOf` [2,3,4]
-- True
--
-- >>> fromList "tab" `isSubsequenceOf` fromList "bat"
-- False
--
isSubsequenceOf :: Eq a => Seq a -> Seq a -> Bool
-- | <math>. Zip two sequences. The result is as long as the shorter
-- sequence.
zip :: Seq a -> Seq b -> Seq (a, b)
-- | <math>. Zip three sequences. The result is as long as the
-- shortest sequence.
zip3 :: Seq a -> Seq b -> Seq c -> Seq (a, b, c)
-- | <math>. Zip two sequences with a function. The result is as long
-- as the shorter sequence.
--
-- Examples
--
--
-- >>> zipWith (+) (fromList [1,2,3]) (fromList [1,1,1,1,1])
-- [2,3,4]
--
zipWith :: (a -> b -> c) -> Seq a -> Seq b -> Seq c
-- | <math>. Zip three sequences with a function. The result is as
-- long as the shortest sequence.
zipWith3 :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
-- | <math>. Zip two sequences with a monadic function. The result is
-- as long as the shorter sequence.
zipWithM :: Monad m => (a -> b -> m c) -> Seq a -> Seq b -> m (Seq c)
-- | <math>. Zip three sequences with a monadic function. The result
-- is as long as the shortest sequence.
zipWith3M :: Monad m => (a -> b -> c -> m d) -> Seq a -> Seq b -> Seq c -> m (Seq d)
-- | <math>. Unzip a sequence of pairs.
unzip :: Seq (a, b) -> (Seq a, Seq b)
-- | <math>. Unzip a sequence of triples.
unzip3 :: Seq (a, b, c) -> (Seq a, Seq b, Seq c)
-- | <math>. Map over a sequence and unzip the result.
--
-- Examples
--
--
-- >>> unzipWith (\x -> (x-1, x*2)) (fromList [1..5])
-- ([0,1,2,3,4],[2,4,6,8,10])
--
unzipWith :: (a -> (b, c)) -> Seq a -> (Seq b, Seq c)
-- | <math>. Map over a sequence and unzip the result.
unzipWith3 :: (a -> (b, c, d)) -> Seq a -> (Seq b, Seq c, Seq d)