containers-0.5.8.1: Data/Sequence.hs
{-# 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 : libraries@haskell.org
-- Stability : experimental
-- 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.Base
import Prelude ()