Ticket #3271: second-round-of-methods-for-data_sequence.dpatch

File second-round-of-methods-for-data_sequence.dpatch, 11.9 KB (added by LouisWasserman, 5 years ago)

The remaining methods specified in the ticket.

Line 
1Wed Jun  3 12:14:47 CDT 2009  wasserman.louis@gmail.com
2  * Second round of methods for Data.Sequence
3 
4  This patch includes the following methods: inits, tails, span, break, iterate, unfoldr, partition, and one or two more.
5 
6
7New patches:
8
9[Second round of methods for Data.Sequence
10wasserman.louis@gmail.com**20090603171447
11 Ignore-this: 5c14e067dd93e64db1794bac21b53295
12 
13 This patch includes the following methods: inits, tails, span, break, iterate, unfoldr, partition, and one or two more.
14 
15] {
16hunk ./Data/Sequence.hs 44
17        (|>),           -- :: Seq a -> a -> Seq a
18        (><),           -- :: Seq a -> Seq a -> Seq a
19        fromList,       -- :: [a] -> Seq a
20+       -- ** Sequential construction
21+       iterate,        -- :: Int -> (a -> a) -> a -> Seq a
22+       unfoldr,        -- :: (b -> Maybe (a, b)) -> b -> Seq a
23        -- * Deconstruction
24        -- | Additional functions for deconstructing sequences are available
25        -- via the 'Foldable' instance of 'Seq'.
26hunk ./Data/Sequence.hs 64
27        scanl1,         -- :: (a -> a -> a) -> Seq a -> Seq a
28        scanr,          -- :: (a -> b -> b) -> b -> Seq a -> Seq b
29        scanr1,         -- :: (a -> a -> a) -> Seq a -> Seq a
30+       -- ** Sublists
31+       tails,          -- :: Seq a -> Seq (Seq a)
32+       inits,          -- :: Seq a -> Seq (Seq a)
33+       takeWhile,      -- :: (a -> Bool) -> Seq a -> Seq a
34+       dropWhile,      -- :: (a -> Bool) -> Seq a -> Seq a
35+       span,           -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
36+       break,          -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
37+       partition,      -- :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
38        -- ** Indexing
39        index,          -- :: Seq a -> Int -> a
40        adjust,         -- :: (a -> a) -> Int -> Seq a -> Seq a
41hunk ./Data/Sequence.hs 94
42        ) where
43 
44 import Prelude hiding (
45-       null, length, take, drop, splitAt, foldl, foldl1, foldr, foldr1,
46-       scanl, scanl1, scanr, scanr1,
47-       replicate,
48-       zip, zipWith, zip3, zipWith3,
49-       reverse)
50+       null, length, take, drop, splitAt, foldl, foldl1, foldr, foldr1, span,
51+       scanl, scanl1, scanr, scanr1, replicate, zip, zipWith, zip3, zipWith3,
52+       takeWhile, dropWhile, break, iterate, reverse)
53 import qualified Data.List (foldl')
54 import Control.Applicative (Applicative(..), (<$>))
55 import Control.Monad (MonadPlus(..))
56hunk ./Data/Sequence.hs 801
57 snocDigitToTree (Deep n pr m (Four a b c d)) (Four x y z w)
58        = Deep (n + 4) pr (m `snocDigitToTree` Two (node3 a b c) (node3 d x y)) (Two z w)
59 
60+-- | Builds a sequence from a seed value.  Takes time linear in the number of generated elements.  /WARNING: If the number of generated elements is infinite, this method will not terminate./
61+unfoldr :: (b -> Maybe (a, b)) -> b -> Seq a
62+unfoldr f b = unfoldr' empty b where
63+       -- uses tail recursion rather than, for instance, the List implementation.
64+       unfoldr' as b = case f b of
65+               Nothing         -> as
66+               Just (a, b')    -> unfoldr' (as |> a) b'
67+
68+-- | /O(n)/.  Constructs a sequence by repeated application of a function to a seed value.
69+--
70+-- > iterate n f x = fromList (Prelude.take n (Prelude.iterate f x))
71+iterate :: Int -> (a -> a) -> a -> Seq a
72+-- borrows the structure of the sequence from replicate and preserves it with mapAccumL
73+iterate n f x = snd (mapAccumL iterate' x (replicate n ())) where
74+       iterate' y _ = let y' = f y in (y', y')
75+
76 ------------------------------------------------------------------------
77 -- Deconstruction
78 ------------------------------------------------------------------------
79hunk ./Data/Sequence.hs 1143
80 splitAt i (Seq xs)     =  (Seq l, Seq r)
81   where        (l, r)          =  split i xs
82 
83+-- | /O(n)/.  Returns a sequence of all suffixes of this sequence, longest first.  For example,
84+--
85+-- > tails (fromList "abc") = fromList [fromList "abc", fromList "bc", fromList "c", fromList ""]
86+--
87+-- The suffixes are computed lazily from left to right.
88+tails                  :: Seq a -> Seq (Seq a)
89+tails xs               = xs <| snd (mapAccumL tails' xs xs) where
90+       -- By using mapAccumL, we keep the structure of xs for free, without having to do any cons operations.
91+       -- We simply ignore the values coming from xs.
92+       tails' ys _ = case viewl ys of
93+               _ :< ys'        -> (ys', ys')
94+               _               -> error "Invariant failure in Data.Sequence.tails" -- should never happen
95+
96+-- | /O(n)/.  Returns a sequence of all prefixes of this sequence, shortest first. For example,
97+--
98+-- > inits (fromList "abc") = fromList [fromList "", fromList "a", fromList "ab", fromList "abc"]
99+--
100+-- The prefixes are computed lazily from left to right. 
101+inits                  :: Seq a -> Seq (Seq a)
102+inits xs               = empty <| snd (mapAccumL inits' empty xs) where
103+       inits' ys y = let ys' = ys |> y in (ys', ys')
104+
105 split :: Int -> FingerTree (Elem a) ->
106        (FingerTree (Elem a), FingerTree (Elem a))
107 split i Empty  = i `seq` (Empty, Empty)
108hunk ./Data/Sequence.hs 1261
109        sab     = sa + size b
110        sabc    = sab + size c
111 
112+-- | /O(i)/ where /i/ is the breakpoint index.  'takeWhile', applied to a predicate @p@ and a sequence @xs@, returns the longest prefix (possibly empty) of @xs@ of elements that satisfy @p@.
113+takeWhile :: (a -> Bool) -> Seq a -> Seq a
114+takeWhile p xs = fst (span p xs)
115+
116+-- | /O(i)/ where /i/ is the breakpoint index.  @'dropWhile' p xs@ returns the suffix remaining after @takeWhile p xs@.
117+dropWhile :: (a -> Bool) -> Seq a -> Seq a
118+dropWhile p xs = snd (span p xs)
119+
120+-- | /O(i)/ where /i/ is the breakpoint index.  'span', applied to a predicate @p@ and a sequence @xs@, returns a tuple whose first element is the longest prefix (possibly empty) of @xs@ of elements that satisfy @p@ and the second element is the remainder of the sequence.
121+span :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
122+span p xs = splitAt ix xs
123+       where   indexed = snd (mapAccumL (\ i x -> (i + 1, (x, i))) 0 xs)
124+               ix = foldr (\ (x, i) i' -> if p x then i' else i) (length xs) indexed
125+
126+-- | /O(i)/ where /i/ is the breakpoint index.  'break', applied to a predicate @p@ and a sequence @xs@, returns a tuple whose first element is the longest prefix (possibly empty) of @xs@ of elements that /do not satisfy/ @p@ and the second element is the remainder of the sequence.
127+break :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
128+break p xs = span (not . p) xs
129+
130+-- | /O(n)/.  The 'partition' function takes a predicate @p@ and a sequence @xs@ and returns sequences of those elements which do and do not satisfy the predicate.
131+partition :: (a -> Bool) -> Seq a -> (Seq a, Seq a)
132+partition p (Seq xs) = case partitionTree (\ (Elem x) -> p x) xs of
133+       (xsT, xsF) -> (Seq xsT, Seq xsF)
134+
135+partitionTree :: (Elem a -> Bool) -> FingerTree (Elem a) -> (FingerTree (Elem a), FingerTree (Elem a))
136+partitionTree _ Empty  = (Empty, Empty)
137+partitionTree p (Single x)
138+       | p x           = (Single x, Empty)
139+       | otherwise     = (Empty, Single x)
140+partitionTree p (Deep _ pr m sf) =
141+       let     (prT, prF) = partitionDigit p pr
142+               (sfT, sfF) = partitionDigit p sf in case partitionTree p (pull m) of
143+               (mT, mF)        -> (combine prT mT sfT, combine prF mF sfF)
144+       where   pull :: FingerTree (Node (Elem a)) -> FingerTree (Elem a)
145+               pull t = case viewLTree t of
146+                       Nothing2        -> Empty
147+                       Just2 l t'      -> case viewRTree t' of
148+                               Nothing2        -> digitToTree (nodeToDigit l)
149+                               Just2 t'' r     -> Deep (size t) (nodeToDigit l) t'' (nodeToDigit r)
150+               combine :: Sized a => Maybe (Digit a) -> FingerTree a -> Maybe (Digit a) -> FingerTree a
151+               combine pr m sf = maybe id consDigitToTree pr $ (maybe m (m `snocDigitToTree`) sf)
152+
153+partitionDigit :: (a -> Bool) -> Digit a -> (Maybe (Digit a), Maybe (Digit a))
154+partitionDigit p (One a) = case (p a) of
155+       (False)         -> (Nothing, Just (One a))
156+       (True)          -> (Just (One a), Nothing)
157+partitionDigit p (Two a b) = case (p a, p b) of
158+       (False, False)          -> (Nothing, Just (Two a b))
159+       (False, True)           -> (Just (One b), Just (One a))
160+       (True, False)           -> (Just (One a), Just (One b))
161+       (True, True)            -> (Just (Two a b), Nothing)
162+partitionDigit p (Three a b c) = case (p a, p b, p c) of
163+       (False, False, False)           -> (Nothing, Just (Three a b c))
164+       (False, False, True)            -> (Just (One c), Just (Two a b))
165+       (False, True, False)            -> (Just (One b), Just (Two a c))
166+       (False, True, True)             -> (Just (Two b c), Just (One a))
167+       (True, False, False)            -> (Just (One a), Just (Two b c))
168+       (True, False, True)             -> (Just (Two a c), Just (One b))
169+       (True, True, False)             -> (Just (Two a b), Just (One c))
170+       (True, True, True)              -> (Just (Three a b c), Nothing)
171+partitionDigit p (Four a b c d) = case (p a, p b, p c, p d) of
172+       (False, False, False, False)            -> (Nothing, Just (Four a b c d))
173+       (False, False, False, True)             -> (Just (One d), Just (Three a b c))
174+       (False, False, True, False)             -> (Just (One c), Just (Three a b d))
175+       (False, False, True, True)              -> (Just (Two c d), Just (Two a b))
176+       (False, True, False, False)             -> (Just (One b), Just (Three a c d))
177+       (False, True, False, True)              -> (Just (Two b d), Just (Two a c))
178+       (False, True, True, False)              -> (Just (Two b c), Just (Two a d))
179+       (False, True, True, True)               -> (Just (Three b c d), Just (One a))
180+       (True, False, False, False)             -> (Just (One a), Just (Three b c d))
181+       (True, False, False, True)              -> (Just (Two a d), Just (Two b c))
182+       (True, False, True, False)              -> (Just (Two a c), Just (Two b d))
183+       (True, False, True, True)               -> (Just (Three a c d), Just (One b))
184+       (True, True, False, False)              -> (Just (Two a b), Just (Two c d))
185+       (True, True, False, True)               -> (Just (Three a b d), Just (One c))
186+       (True, True, True, False)               -> (Just (Three a b c), Just (One d))
187+       (True, True, True, True)                -> (Just (Four a b c d), Nothing)
188+
189 ------------------------------------------------------------------------
190 -- Lists
191 ------------------------------------------------------------------------
192}
193
194Context:
195
196[New methods for Data.Sequence
197wasserman.louis@gmail.com**20090601192920
198 Ignore-this: b975d876022f0788997319dce83dbc93
199 
200 This patch includes several new methods for Data.Sequence.  Scan and replicate methods analogous to their List versions have been included, and most importantly there are fast zip functions, which run considerably faster than the workaround of converting to lists and zipping those.
201]
202[Use left/right rather than old/new to describe the arguments to unionWithKey
203Ian Lynagh <igloo@earth.li>**20090208192132
204 Fixes trac #3002.
205]
206[help nhc98 by making import decl more explicit
207Malcolm.Wallace@cs.york.ac.uk**20090203142144]
208[Add instance Data.Traversable for IntMap
209Matti Niemenmaa <matti.niemenmaa+darcs@iki.fi>**20090116190353
210 Ignore-this: df88a286935926aecec3f8a5dd291699
211]
212[Require Cabal version >= 1.6
213Ian Lynagh <igloo@earth.li>**20090122011256]
214[Add "bug-reports" and "source-repository" info to the Cabal file
215Ian Lynagh <igloo@earth.li>**20090121182106]
216[Fix warnings in containers
217Ian Lynagh <igloo@earth.li>**20090116200251]
218[optimize IntMap/IntSet findMin/findMax
219sedillard@gmail.com**20081002152055]
220[O(n) fromAscList IntSet / IntMap
221sedillard@gmail.com**20080521195941
222 
223 Added algorithm by Scott Dillard and Bertram Felgenhauer to build IntSets and
224 IntMaps from sorted input in linear time. Also changed quickcheck prop_Ordered
225 (no longer a tautology!) to include negative and duplicate keys.
226 
227]
228[correct type for IntMap.intersectionWith[Key]
229sedillard@gmail.com**20081002144828]
230[Export mapAccumRWithKey from Map and IntMap (Trac #2769)
231matti.niemenmaa+darcs@iki.fi**20081210160205]
232[Bump the version number to 0.2.0.1, to work-around cabal-install problems
233Ian Lynagh <igloo@earth.li>**20081212201829]
234[Fix #2760: change mkNorepType to mkNoRepType
235'Jose Pedro Magalhaes <jpm@cs.uu.nl>'**20081202083424]
236[Doc fix, from hackage trac #378
237Ian Lynagh <igloo@earth.li>**20081024143949]
238[import Data.Data instead of Data.Generics.*, eliminating the dependency on syb
239Ross Paterson <ross@soi.city.ac.uk>**20081005002559]
240[fixed typo in highestBitMask
241sedillard@gmail.com**20081002215438]
242[export Data.Map.toDescList, foldlWithKey, and foldrWithKey (trac ticket 2580)
243qdunkan@gmail.com**20080922213200
244 
245 toDescList was previously implemented, but not exported.
246 
247 foldlWithKey was previously implemented, but not exported.  It can be used to
248 implement toDescList.
249 
250 foldrWithKey is already exported as foldWithKey, but foldrWithKey is explicitly
251 the mirror of foldlWithKey, and foldWithKey kept for compatibility.
252]
253[Bump version number to 0.2.0.0
254Ian Lynagh <igloo@earth.li>**20080920160016]
255[TAG 6.10 branch has been forked
256Ian Lynagh <igloo@earth.li>**20080919123438]
257Patch bundle hash:
258e1955d8836e9a7b3ac4b5d743aa240252ab56f47