{-# LANGUAGE CPP #-} #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 : [email protected] -- Portability : portable -- -- General purpose finite sequences. -- Apart from being finite and having strict operations, sequences -- also differ from lists in supporting a wider variety of operations -- efficiently. -- -- 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. -- -- 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> -- -- /Note/: Many of these operations have the same names as similar -- operations on lists in the "Prelude". The ambiguity may be resolved -- using either qualification or the @hiding@ clause. -- -- /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'. -- ----------------------------------------------------------------------------- module Data.Sequence ( #if defined(DEFINE_PATTERN_SYNONYMS) Seq (Empty, (:<|), (:|>)), #else Seq, #endif -- * Construction empty, -- :: Seq a singleton, -- :: a -> Seq a (<|), -- :: a -> Seq a -> Seq a (|>), -- :: Seq a -> a -> Seq a (><), -- :: Seq a -> Seq a -> Seq a fromList, -- :: [a] -> Seq a fromFunction, -- :: Int -> (Int -> a) -> Seq a fromArray, -- :: Ix i => Array i a -> Seq a -- ** Repetition replicate, -- :: Int -> a -> Seq a replicateA, -- :: Applicative f => Int -> f a -> f (Seq a) replicateM, -- :: Monad m => Int -> m a -> m (Seq a) cycleTaking, -- :: Int -> Seq a -> Seq a -- ** Iterative construction iterateN, -- :: Int -> (a -> a) -> a -> Seq a unfoldr, -- :: (b -> Maybe (a, b)) -> b -> Seq a unfoldl, -- :: (b -> Maybe (b, a)) -> b -> Seq a -- * Deconstruction -- | Additional functions for deconstructing sequences are available -- via the 'Foldable' instance of 'Seq'. -- ** Queries null, -- :: Seq a -> Bool length, -- :: Seq a -> Int -- ** Views ViewL(..), viewl, -- :: Seq a -> ViewL a ViewR(..), viewr, -- :: Seq a -> ViewR a -- * Scans scanl, -- :: (a -> b -> a) -> a -> Seq b -> Seq a scanl1, -- :: (a -> a -> a) -> Seq a -> Seq a scanr, -- :: (a -> b -> b) -> b -> Seq a -> Seq b scanr1, -- :: (a -> a -> a) -> Seq a -> Seq a -- * Sublists tails, -- :: Seq a -> Seq (Seq a) inits, -- :: Seq a -> Seq (Seq a) chunksOf, -- :: Int -> Seq a -> Seq (Seq a) -- ** Sequential searches takeWhileL, -- :: (a -> Bool) -> Seq a -> Seq a takeWhileR, -- :: (a -> Bool) -> Seq a -> Seq a dropWhileL, -- :: (a -> Bool) -> Seq a -> Seq a dropWhileR, -- :: (a -> Bool) -> Seq a -> Seq a spanl, -- :: (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 -- * Sorting sort, -- :: Ord a => Seq a -> Seq a sortBy, -- :: (a -> a -> Ordering) -> Seq a -> Seq a unstableSort, -- :: Ord a => Seq a -> Seq a unstableSortBy, -- :: (a -> a -> Ordering) -> Seq a -> Seq a -- * Indexing lookup, -- :: Int -> Seq a -> Maybe a (!?), -- :: Seq a -> Int -> Maybe a index, -- :: Seq a -> Int -> a adjust, -- :: (a -> a) -> Int -> Seq a -> Seq a adjust', -- :: (a -> a) -> Int -> Seq a -> Seq a update, -- :: Int -> a -> Seq a -> Seq a take, -- :: Int -> Seq a -> Seq a drop, -- :: Int -> Seq a -> Seq a insertAt, -- :: Int -> a -> Seq a -> Seq a deleteAt, -- :: Int -> Seq a -> Seq a splitAt, -- :: 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 Int elemIndicesL, -- :: Eq a => a -> Seq a -> [Int] elemIndexR, -- :: Eq a => a -> Seq a -> Maybe Int elemIndicesR, -- :: Eq a => a -> Seq a -> [Int] findIndexL, -- :: (a -> Bool) -> Seq a -> Maybe Int findIndicesL, -- :: (a -> Bool) -> Seq a -> [Int] findIndexR, -- :: (a -> Bool) -> Seq a -> Maybe Int findIndicesR, -- :: (a -> Bool) -> Seq a -> [Int] -- * Folds -- | General folds are available via the 'Foldable' instance of 'Seq'. foldMapWithIndex, -- :: Monoid m => (Int -> a -> m) -> Seq a -> m foldlWithIndex, -- :: (b -> Int -> a -> b) -> b -> Seq a -> b foldrWithIndex, -- :: (Int -> a -> b -> b) -> b -> Seq a -> b -- * Transformations mapWithIndex, -- :: (Int -> a -> b) -> Seq a -> Seq b traverseWithIndex, -- :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b) reverse, -- :: Seq a -> Seq a intersperse, -- :: a -> Seq a -> Seq a -- ** Zips zip, -- :: Seq a -> Seq b -> Seq (a, b) zipWith, -- :: (a -> b -> c) -> Seq a -> Seq b -> Seq c zip3, -- :: Seq a -> Seq b -> Seq c -> Seq (a, b, c) zipWith3, -- :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d zip4, -- :: 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 e ) where import Data.Sequence.Internal import Prelude ()