{-# LANGUAGE CPP #-}
#ifdef __HADDOCK_VERSION__
{-# OPTIONS_GHC -Wno-unused-imports #-}
#endif

#include "containers.h"
------------------------------------------------------------------------------- |-- Module : Data.Sequence-- Copyright : (c) Ross Paterson 2005-- (c) Louis Wasserman 2009-- (c) Bertram Felgenhauer, David Feuer, Ross Paterson, and-- Milan Straka 2014-- License : BSD-style-- Maintainer : libraries@haskell.org-- Portability : portable---- = Finite sequences---- The @'Seq' a@ type represents a finite sequence of values of-- type @a@.---- Sequences generally behave very much like lists.---- * The class instances for sequences are all based very closely on those for-- lists.---- * Many functions in this module have the same names as functions in-- the "Prelude" or in "Data.List". In almost all cases, these functions-- behave analogously. For example, 'filter' filters a sequence in exactly the-- same way that @"Prelude".'Prelude.filter'@ filters a list. The only major-- exception is the 'lookup' function, which is based on the function by-- that name in "Data.IntMap" rather than the one in "Prelude".---- There are two major differences between sequences and lists:---- * Sequences support a wider variety of efficient operations than-- do lists. Notably, they offer---- * Constant-time access to both the front and the rear with-- '<|', '|>', 'viewl', 'viewr'. For recent GHC versions, this can-- be done more conveniently using the bidirectional patterns 'Empty',-- ':<|', and ':|>'. See the detailed explanation in the \"Pattern synonyms\"-- section.-- * Logarithmic-time concatenation with '><'-- * Logarithmic-time splitting with 'splitAt', 'take' and 'drop'-- * Logarithmic-time access to any element with-- 'lookup', '!?', 'index', 'insertAt', 'deleteAt', 'adjust'', and 'update'---- Note that sequences are typically /slower/ than lists when using only-- operations for which they have the same big-\(O\) complexity: sequences-- make rather mediocre stacks!---- * Whereas lists can be either finite or infinite, sequences are-- always finite. As a result, a sequence is strict in its-- length. Ignoring efficiency, you can imagine that 'Seq' is defined---- @ data Seq a = Empty | a :<| !(Seq a) @---- This means that many operations on sequences are stricter than-- those on lists. For example,---- @ (1 : undefined) !! 0 = 1 @---- but---- @ (1 :<| undefined) ``index`` 0 = undefined @---- Sequences may also be compared to immutable-- [arrays](https://hackage.haskell.org/package/array)-- or [vectors](https://hackage.haskell.org/package/vector).-- Like these structures, sequences support fast indexing,-- although not as fast. But editing an immutable array or vector,-- or combining it with another, generally requires copying the-- entire structure; sequences generally avoid that, copying only-- the portion that has changed.---- == Detailed performance information---- An amortized running time is given for each operation, with \(n\) referring-- to the length of the sequence and /i/ being the integral index used by-- some operations. These bounds hold even in a persistent (shared) setting.---- Despite sequences being structurally strict from a semantic standpoint,-- they are in fact implemented using laziness internally. As a result,-- many operations can be performed /incrementally/, producing their results-- as they are demanded. This greatly improves performance in some cases. These-- functions include---- * The 'Functor' methods 'fmap' and '<$', along with 'mapWithIndex'-- * The 'Applicative' methods '<*>', '*>', and '<*'-- * The zips: 'zipWith', 'zip', etc.-- * 'inits', 'tails'-- * 'fromFunction', 'replicate', 'intersperse', and 'cycleTaking'-- * 'reverse'-- * 'chunksOf'---- Note that the 'Monad' method, '>>=', is not particularly lazy. It will-- take time proportional to the sum of the logarithms of the individual-- result sequences to produce anything whatsoever.---- Several functions take special advantage of sharing to produce-- results using much less time and memory than one might expect. These-- are documented individually for functions, but also include certain-- class methods:---- '<$' and '*>' each take time and space proportional-- to the logarithm of the size of their result.---- '<*' takes time and space proportional to the product of the length-- of its first argument and the logarithm of the length of its second-- argument.---- == Warning---- The size of a 'Seq' must not exceed @maxBound::Int@. Violation-- of this condition is not detected and if the size limit is exceeded, the-- behaviour of the sequence is undefined. This is unlikely to occur in most-- applications, but some care may be required when using '><', '<*>', '*>', or-- '>>', particularly repeatedly and particularly in combination with-- 'replicate' or 'fromFunction'.---- == Implementation---- The implementation uses 2-3 finger trees annotated with sizes,-- as described in section 4.2 of---- * Ralf Hinze and Ross Paterson,-- \"/Finger trees: a simple general-purpose data structure/\",-- Journal of Functional Programming 16:2 (2006) pp 197-217.-- <http://staff.city.ac.uk/~ross/papers/FingerTree.html>.-------------------------------------------------------------------------------moduleData.Sequence(-- * Finite sequences
#if defined(DEFINE_PATTERN_SYNONYMS)
Seq (Empty ,(:<|) ,(:|>) ),-- $patterns
#else
Seq,
#endif
-- * Constructionempty ,-- :: Seq asingleton ,-- :: a -> Seq a(<|) ,-- :: a -> Seq a -> Seq a(|>) ,-- :: Seq a -> a -> Seq a(><) ,-- :: Seq a -> Seq a -> Seq afromList ,-- :: [a] -> Seq afromFunction ,-- :: Int -> (Int -> a) -> Seq afromArray ,-- :: Ix i => Array i a -> Seq a-- ** Repetitionreplicate ,-- :: Int -> a -> Seq areplicateA ,-- :: Applicative f => Int -> f a -> f (Seq a)replicateM ,-- :: Applicative m => Int -> m a -> m (Seq a)cycleTaking ,-- :: Int -> Seq a -> Seq a-- ** Iterative constructioniterateN ,-- :: Int -> (a -> a) -> a -> Seq aunfoldr ,-- :: (b -> Maybe (a, b)) -> b -> Seq aunfoldl ,-- :: (b -> Maybe (b, a)) -> b -> Seq a-- * Deconstruction-- | Additional functions for deconstructing sequences are available-- via the 'Data.Foldable.Foldable' instance of 'Seq'.-- ** Queriesnull ,-- :: Seq a -> Boollength ,-- :: Seq a -> Int-- ** ViewsViewL (..),viewl ,-- :: Seq a -> ViewL aViewR (..),viewr ,-- :: Seq a -> ViewR a-- * Scansscanl ,-- :: (a -> b -> a) -> a -> Seq b -> Seq ascanl1 ,-- :: (a -> a -> a) -> Seq a -> Seq ascanr ,-- :: (a -> b -> b) -> b -> Seq a -> Seq bscanr1 ,-- :: (a -> a -> a) -> Seq a -> Seq a-- * Subliststails ,-- :: Seq a -> Seq (Seq a)inits ,-- :: Seq a -> Seq (Seq a)chunksOf ,-- :: Int -> Seq a -> Seq (Seq a)-- ** Sequential searchestakeWhileL ,-- :: (a -> Bool) -> Seq a -> Seq atakeWhileR ,-- :: (a -> Bool) -> Seq a -> Seq adropWhileL ,-- :: (a -> Bool) -> Seq a -> Seq adropWhileR ,-- :: (a -> Bool) -> Seq a -> Seq aspanl ,-- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)spanr ,-- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)breakl ,-- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)breakr ,-- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)partition ,-- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)filter ,-- :: (a -> Bool) -> Seq a -> Seq a-- * Sortingsort ,-- :: Ord a => Seq a -> Seq asortBy ,-- :: (a -> a -> Ordering) -> Seq a -> Seq asortOn ,-- :: Ord b => (a -> b) -> Seq a -> Seq aunstableSort ,-- :: Ord a => Seq a -> Seq aunstableSortBy ,-- :: (a -> a -> Ordering) -> Seq a -> Seq aunstableSortOn ,-- :: Ord b => (a -> b) -> Seq a -> Seq a-- * Indexinglookup ,-- :: Int -> Seq a -> Maybe a(!?) ,-- :: Seq a -> Int -> Maybe aindex ,-- :: Seq a -> Int -> aadjust ,-- :: (a -> a) -> Int -> Seq a -> Seq aadjust' ,-- :: (a -> a) -> Int -> Seq a -> Seq aupdate ,-- :: Int -> a -> Seq a -> Seq atake ,-- :: Int -> Seq a -> Seq adrop ,-- :: Int -> Seq a -> Seq ainsertAt ,-- :: Int -> a -> Seq a -> Seq adeleteAt ,-- :: Int -> Seq a -> Seq asplitAt ,-- :: Int -> Seq a -> (Seq a, Seq a)-- ** Indexing with predicates-- | These functions perform sequential searches from the left-- or right ends of the sequence, returning indices of matching-- elements.elemIndexL ,-- :: Eq a => a -> Seq a -> Maybe IntelemIndicesL ,-- :: Eq a => a -> Seq a -> [Int]elemIndexR ,-- :: Eq a => a -> Seq a -> Maybe IntelemIndicesR ,-- :: Eq a => a -> Seq a -> [Int]findIndexL ,-- :: (a -> Bool) -> Seq a -> Maybe IntfindIndicesL ,-- :: (a -> Bool) -> Seq a -> [Int]findIndexR ,-- :: (a -> Bool) -> Seq a -> Maybe IntfindIndicesR ,-- :: (a -> Bool) -> Seq a -> [Int]-- * Folds-- | General folds are available via the 'Data.Foldable.Foldable' instance-- of 'Seq'.foldMapWithIndex ,-- :: Monoid m => (Int -> a -> m) -> Seq a -> mfoldlWithIndex ,-- :: (b -> Int -> a -> b) -> b -> Seq a -> bfoldrWithIndex ,-- :: (Int -> a -> b -> b) -> b -> Seq a -> b-- * TransformationsmapWithIndex ,-- :: (Int -> a -> b) -> Seq a -> Seq btraverseWithIndex ,-- :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b)reverse ,-- :: Seq a -> Seq aintersperse ,-- :: a -> Seq a -> Seq a-- ** Zips and unzipzip ,-- :: Seq a -> Seq b -> Seq (a, b)zipWith ,-- :: (a -> b -> c) -> Seq a -> Seq b -> Seq czip3 ,-- :: Seq a -> Seq b -> Seq c -> Seq (a, b, c)zipWith3 ,-- :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq dzip4 ,-- :: Seq a -> Seq b -> Seq c -> Seq d -> Seq (a, b, c, d)zipWith4 ,-- :: (a -> b -> c -> d -> e) -> Seq a -> Seq b -> Seq c -> Seq d -> Seq eunzip ,-- :: Seq (a, b) -> (Seq a, Seq b)unzipWith -- :: (a -> (b, c)) -> Seq a -> (Seq b, Seq c))whereimportData.Sequence.Internal importData.Sequence.Internal.Sorting importPrelude()
#ifdef __HADDOCK_VERSION__
importControl.Monad(Monad(..))importData.Functor(Functor(..))
#endif
{- $patterns
== Pattern synonyms
Much like lists can be constructed and matched using the
@:@ and @[]@ constructors, sequences can be constructed and
matched using the 'Empty', ':<|', and ':|>' pattern synonyms.
=== Note
These patterns are only available with GHC version 8.0 or later,
and version 8.2 works better with them. When writing for such recent
versions of GHC, the patterns can be used in place of 'empty',
'<|', '|>', 'viewl', and 'viewr'.
=== __Pattern synonym examples__
Import the patterns:
@
import Data.Sequence (Seq (..))
@
Look at the first three elements of a sequence
@
getFirst3 :: Seq a -> Maybe (a,a,a)
getFirst3 (x1 :<| x2 :<| x3 :<| _xs) = Just (x1,x2,x3)
getFirst3 _ = Nothing
@
@
\> getFirst3 ('fromList' [1,2,3,4]) = Just (1,2,3)
\> getFirst3 ('fromList' [1,2]) = Nothing
@
Move the last two elements from the end of the first list
onto the beginning of the second one.
@
shift2Right :: Seq a -> Seq a -> (Seq a, Seq a)
shift2Right Empty ys = (Empty, ys)
shift2Right (Empty :|> x) ys = (Empty, x :<| ys)
shift2Right (xs :|> x1 :|> x2) ys = (xs, x1 :<| x2 :<| ys)
@
@
\> shift2Right ('fromList' []) ('fromList' [10]) = ('fromList' [], 'fromList' [10])
\> shift2Right ('fromList' [9]) ('fromList' [10]) = ('fromList' [], 'fromList' [9,10])
\> shift2Right ('fromList' [8,9]) ('fromList' [10]) = ('fromList' [], 'fromList' [8,9,10])
\> shift2Right ('fromList' [7,8,9]) ('fromList' [10]) = ('fromList' [7], 'fromList' [8,9,10])
@
-}