Refactor internal modules (#324)
[packages/containers.git] / Data / Sequence.hs
1 {-# LANGUAGE CPP #-}
2
3 #include "containers.h"
4
5 -----------------------------------------------------------------------------
6 -- |
7 -- Module : Data.Sequence
8 -- Copyright : (c) Ross Paterson 2005
9 -- (c) Louis Wasserman 2009
10 -- (c) Bertram Felgenhauer, David Feuer, Ross Paterson, and
11 -- Milan Straka 2014
12 -- License : BSD-style
13 -- Maintainer : libraries@haskell.org
14 -- Stability : experimental
15 -- Portability : portable
16 --
17 -- General purpose finite sequences.
18 -- Apart from being finite and having strict operations, sequences
19 -- also differ from lists in supporting a wider variety of operations
20 -- efficiently.
21 --
22 -- An amortized running time is given for each operation, with /n/ referring
23 -- to the length of the sequence and /i/ being the integral index used by
24 -- some operations. These bounds hold even in a persistent (shared) setting.
25 --
26 -- The implementation uses 2-3 finger trees annotated with sizes,
27 -- as described in section 4.2 of
28 --
29 -- * Ralf Hinze and Ross Paterson,
30 -- \"Finger trees: a simple general-purpose data structure\",
31 -- /Journal of Functional Programming/ 16:2 (2006) pp 197-217.
32 -- <http://staff.city.ac.uk/~ross/papers/FingerTree.html>
33 --
34 -- /Note/: Many of these operations have the same names as similar
35 -- operations on lists in the "Prelude". The ambiguity may be resolved
36 -- using either qualification or the @hiding@ clause.
37 --
38 -- /Warning/: The size of a 'Seq' must not exceed @maxBound::Int@. Violation
39 -- of this condition is not detected and if the size limit is exceeded, the
40 -- behaviour of the sequence is undefined. This is unlikely to occur in most
41 -- applications, but some care may be required when using '><', '<*>', '*>', or
42 -- '>>', particularly repeatedly and particularly in combination with
43 -- 'replicate' or 'fromFunction'.
44 --
45 -----------------------------------------------------------------------------
46
47
48 module Data.Sequence (
49 #if defined(DEFINE_PATTERN_SYNONYMS)
50 Seq (Empty, (:<|), (:|>)),
51 #else
52 Seq,
53 #endif
54 -- * Construction
55 empty, -- :: Seq a
56 singleton, -- :: a -> Seq a
57 (<|), -- :: a -> Seq a -> Seq a
58 (|>), -- :: Seq a -> a -> Seq a
59 (><), -- :: Seq a -> Seq a -> Seq a
60 fromList, -- :: [a] -> Seq a
61 fromFunction, -- :: Int -> (Int -> a) -> Seq a
62 fromArray, -- :: Ix i => Array i a -> Seq a
63 -- ** Repetition
64 replicate, -- :: Int -> a -> Seq a
65 replicateA, -- :: Applicative f => Int -> f a -> f (Seq a)
66 replicateM, -- :: Monad m => Int -> m a -> m (Seq a)
67 cycleTaking, -- :: Int -> Seq a -> Seq a
68 -- ** Iterative construction
69 iterateN, -- :: Int -> (a -> a) -> a -> Seq a
70 unfoldr, -- :: (b -> Maybe (a, b)) -> b -> Seq a
71 unfoldl, -- :: (b -> Maybe (b, a)) -> b -> Seq a
72 -- * Deconstruction
73 -- | Additional functions for deconstructing sequences are available
74 -- via the 'Foldable' instance of 'Seq'.
75
76 -- ** Queries
77 null, -- :: Seq a -> Bool
78 length, -- :: Seq a -> Int
79 -- ** Views
80 ViewL(..),
81 viewl, -- :: Seq a -> ViewL a
82 ViewR(..),
83 viewr, -- :: Seq a -> ViewR a
84 -- * Scans
85 scanl, -- :: (a -> b -> a) -> a -> Seq b -> Seq a
86 scanl1, -- :: (a -> a -> a) -> Seq a -> Seq a
87 scanr, -- :: (a -> b -> b) -> b -> Seq a -> Seq b
88 scanr1, -- :: (a -> a -> a) -> Seq a -> Seq a
89 -- * Sublists
90 tails, -- :: Seq a -> Seq (Seq a)
91 inits, -- :: Seq a -> Seq (Seq a)
92 chunksOf, -- :: Int -> Seq a -> Seq (Seq a)
93 -- ** Sequential searches
94 takeWhileL, -- :: (a -> Bool) -> Seq a -> Seq a
95 takeWhileR, -- :: (a -> Bool) -> Seq a -> Seq a
96 dropWhileL, -- :: (a -> Bool) -> Seq a -> Seq a
97 dropWhileR, -- :: (a -> Bool) -> Seq a -> Seq a
98 spanl, -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
99 spanr, -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
100 breakl, -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
101 breakr, -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
102 partition, -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
103 filter, -- :: (a -> Bool) -> Seq a -> Seq a
104 -- * Sorting
105 sort, -- :: Ord a => Seq a -> Seq a
106 sortBy, -- :: (a -> a -> Ordering) -> Seq a -> Seq a
107 unstableSort, -- :: Ord a => Seq a -> Seq a
108 unstableSortBy, -- :: (a -> a -> Ordering) -> Seq a -> Seq a
109 -- * Indexing
110 lookup, -- :: Int -> Seq a -> Maybe a
111 (!?), -- :: Seq a -> Int -> Maybe a
112 index, -- :: Seq a -> Int -> a
113 adjust, -- :: (a -> a) -> Int -> Seq a -> Seq a
114 adjust', -- :: (a -> a) -> Int -> Seq a -> Seq a
115 update, -- :: Int -> a -> Seq a -> Seq a
116 take, -- :: Int -> Seq a -> Seq a
117 drop, -- :: Int -> Seq a -> Seq a
118 insertAt, -- :: Int -> a -> Seq a -> Seq a
119 deleteAt, -- :: Int -> Seq a -> Seq a
120 splitAt, -- :: Int -> Seq a -> (Seq a, Seq a)
121 -- ** Indexing with predicates
122 -- | These functions perform sequential searches from the left
123 -- or right ends of the sequence, returning indices of matching
124 -- elements.
125 elemIndexL, -- :: Eq a => a -> Seq a -> Maybe Int
126 elemIndicesL, -- :: Eq a => a -> Seq a -> [Int]
127 elemIndexR, -- :: Eq a => a -> Seq a -> Maybe Int
128 elemIndicesR, -- :: Eq a => a -> Seq a -> [Int]
129 findIndexL, -- :: (a -> Bool) -> Seq a -> Maybe Int
130 findIndicesL, -- :: (a -> Bool) -> Seq a -> [Int]
131 findIndexR, -- :: (a -> Bool) -> Seq a -> Maybe Int
132 findIndicesR, -- :: (a -> Bool) -> Seq a -> [Int]
133 -- * Folds
134 -- | General folds are available via the 'Foldable' instance of 'Seq'.
135 foldMapWithIndex, -- :: Monoid m => (Int -> a -> m) -> Seq a -> m
136 foldlWithIndex, -- :: (b -> Int -> a -> b) -> b -> Seq a -> b
137 foldrWithIndex, -- :: (Int -> a -> b -> b) -> b -> Seq a -> b
138 -- * Transformations
139 mapWithIndex, -- :: (Int -> a -> b) -> Seq a -> Seq b
140 traverseWithIndex, -- :: Applicative f => (Int -> a -> f b) -> Seq a -> f (Seq b)
141 reverse, -- :: Seq a -> Seq a
142 intersperse, -- :: a -> Seq a -> Seq a
143 -- ** Zips
144 zip, -- :: Seq a -> Seq b -> Seq (a, b)
145 zipWith, -- :: (a -> b -> c) -> Seq a -> Seq b -> Seq c
146 zip3, -- :: Seq a -> Seq b -> Seq c -> Seq (a, b, c)
147 zipWith3, -- :: (a -> b -> c -> d) -> Seq a -> Seq b -> Seq c -> Seq d
148 zip4, -- :: Seq a -> Seq b -> Seq c -> Seq d -> Seq (a, b, c, d)
149 zipWith4, -- :: (a -> b -> c -> d -> e) -> Seq a -> Seq b -> Seq c -> Seq d -> Seq e
150 ) where
151
152 import Data.Sequence.Internal
153 import Prelude ()