{-# 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\"] -- (http://staff.city.ac.uk/~ross/papers/FingerTree.html), -- /Journal of Functional Programming/ 16:2 (2006) pp 197-217. -- ----------------------------------------------------------------------------- module Data.Sequence ( -- * Finite sequences #if defined(DEFINE_PATTERN_SYNONYMS) Seq (Empty, (:<|), (:|>)), -- $patterns #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, -- :: Applicative 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 'Data.Foldable.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 sortOn, -- :: Ord b => (a -> b) -> Seq a -> Seq a unstableSort, -- :: Ord a => Seq a -> Seq a unstableSortBy, -- :: (a -> a -> Ordering) -> Seq a -> Seq a unstableSortOn, -- :: Ord b => (a -> b) -> 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 'Data.Foldable.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 and unzip 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 unzip, -- :: Seq (a, b) -> (Seq a, Seq b) unzipWith -- :: (a -> (b, c)) -> Seq a -> (Seq b, Seq c) ) where import Data.Sequence.Internal import Data.Sequence.Internal.Sorting import Prelude () #ifdef __HADDOCK_VERSION__ import Control.Monad (Monad (..)) import Control.Applicative (Applicative (..)) import Data.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]) @ -}