Fri Aug 21 00:46:25 EDT 2009 wasserman.louis@gmail.com
* Ticket #3271: New methods for Data.Sequence
New patches:
[Ticket #3271: New methods for Data.Sequence
wasserman.louis@gmail.com**20090821044625
Ignorethis: f92f642d4fd04bd7a03bb5b5c20b39f6
] {
hunk ./Data/IntMap.hs 185
#if __GLASGOW_HASKELL__
import Text.Read
import Data.Data (Data(..), mkNoRepType)
+import Data.Data (Data(..), mkNorepType)
#endif
#if __GLASGOW_HASKELL__ >= 503
hunk ./Data/IntMap.hs 276
gfoldl f z im = z fromList `f` (toList im)
toConstr _ = error "toConstr"
gunfold _ _ = error "gunfold"
 dataTypeOf _ = mkNoRepType "Data.IntMap.IntMap"
+ dataTypeOf _ = mkNorepType "Data.IntMap.IntMap"
dataCast1 f = gcast1 f
#endif
hunk ./Data/IntSet.hs 122
#if __GLASGOW_HASKELL__
import Text.Read
import Data.Data (Data(..), mkNoRepType)
+import Data.Data (Data(..), mkNorepType)
#endif
#if __GLASGOW_HASKELL__ >= 503
hunk ./Data/IntSet.hs 200
gfoldl f z is = z fromList `f` (toList is)
toConstr _ = error "toConstr"
gunfold _ _ = error "gunfold"
 dataTypeOf _ = mkNoRepType "Data.IntSet.IntSet"
+ dataTypeOf _ = mkNorepType "Data.IntSet.IntSet"
#endif
hunk ./Data/Map.hs 200
#if __GLASGOW_HASKELL__
import Text.Read
import Data.Data (Data(..), mkNoRepType, gcast2)
+import Data.Data (Data(..), mkNorepType, gcast2)
#endif
{
hunk ./Data/Map.hs 248
gfoldl f z m = z fromList `f` toList m
toConstr _ = error "toConstr"
gunfold _ _ = error "gunfold"
 dataTypeOf _ = mkNoRepType "Data.Map.Map"
+ dataTypeOf _ = mkNorepType "Data.Map.Map"
dataCast2 f = gcast2 f
#endif
hunk ./Data/Sequence.hs 6
 
 Module : Data.Sequence
 Copyright : (c) Ross Paterson 2005
+ (c) Louis Wasserman 2009
 License : BSDstyle
 Maintainer : libraries@haskell.org
 Stability : experimental
hunk ./Data/Sequence.hs 40
 * Construction
empty,  :: Seq a
singleton,  :: a > Seq a
+ replicate,  :: Int > a > Seq a
+ replicateA,  :: Applicative f => Int > f a > f (Seq a)
+ replicateM,  :: Monad m => Int > m a > m (Seq a)
(<),  :: a > Seq a > Seq a
(>),  :: Seq a > a > Seq a
(><),  :: Seq a > Seq a > Seq a
hunk ./Data/Sequence.hs 47
fromList,  :: [a] > Seq a
+  ** Sequential 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'.
hunk ./Data/Sequence.hs 63
viewl,  :: Seq a > ViewL a
ViewR(..),
viewr,  :: Seq a > ViewR a
  ** Indexing
+  * Scanning
+ 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)
+ 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
+  * Sorts
+ 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
index,  :: Seq a > Int > a
adjust,  :: (a > a) > Int > Seq a > Seq a
update,  :: Int > a > Seq a > Seq a
hunk ./Data/Sequence.hs 93
take,  :: Int > Seq a > Seq a
drop,  :: Int > Seq a > Seq a
splitAt,  :: Int > Seq a > (Seq a, Seq a)
+  ** Indexing with predicates
+ elemIndexL,  :: Eq a => a > Seq a > Maybe Int
+ elemIndicesL,  :: Eq a => a > Seq a > [Int]
+ elemIndexR,  :: Eq a => a > Seq a > Maybe Ind
+ 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
+ foldWithIndexL,  :: (b > Int > a > b) > b > Seq a > b
+ foldWithIndexR,  :: (Int > a > b > b) > b > Seq a > b
 * Transformations
hunk ./Data/Sequence.hs 106
+ mapWithIndex,  :: (Int > a > b) > Seq a > Seq b
reverse,  :: Seq a > Seq a
hunk ./Data/Sequence.hs 108
+  ** 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
#if TESTING
valid,
#endif
hunk ./Data/Sequence.hs 121
) where
import Prelude hiding (
 null, length, take, drop, splitAt, foldl, foldl1, foldr, foldr1,
 reverse)
import qualified Data.List (foldl')
import Control.Applicative (Applicative(..), (<$>))
import Control.Monad (MonadPlus(..))
+ null, length, take, drop, splitAt, foldl, foldl1, foldr, foldr1, span,
+ scanl, scanl1, scanr, scanr1, replicate, zip, zipWith, zip3, zipWith3,
+ takeWhile, dropWhile, break, iterate, reverse, filter, mapM, all)
+import qualified Data.List (foldl', zipWith)
+import Control.Applicative (Applicative(..), (<$>), WrappedMonad(..), liftA, liftA2, liftA3)
+import Control.Monad (MonadPlus(..), ap, liftM, liftM2, liftM3, liftM4)
+import qualified Control.Monad
import Data.Monoid (Monoid(..))
import Data.Foldable
import Data.Traversable
hunk ./Data/Sequence.hs 137
import Data.Typeable (TyCon, Typeable1(..), mkTyCon, mkTyConApp )
#ifdef __GLASGOW_HASKELL__
+import GHC.Exts (build)
import Text.Read (Lexeme(Ident), lexP, parens, prec,
readPrec, readListPrec, readListPrecDefault)
import Data.Data (Data(..), DataType, Constr, Fixity(..),
hunk ./Data/Sequence.hs 145
#endif
#if TESTING
import Control.Monad (liftM, liftM3, liftM4)
import Test.QuickCheck
+import Test.QuickCheck hiding ((><))
#endif
infixr 5 `consTree`
hunk ./Data/Sequence.hs 302
traverse f sf
{# INLINE deep #}
{# SPECIALIZE deep :: Digit (Elem a) > FingerTree (Node (Elem a)) > Digit (Elem a) > FingerTree (Elem a) #}
{# SPECIALIZE deep :: Digit (Node a) > FingerTree (Node (Node a)) > Digit (Node a) > FingerTree (Node a) #}
+{# SPECIALIZE INLINE deep :: Digit (Elem a) > FingerTree (Node (Elem a)) > Digit (Elem a) > FingerTree (Elem a) #}
+{# SPECIALIZE INLINE deep :: Digit (Node a) > FingerTree (Node (Node a)) > Digit (Node a) > FingerTree (Node a) #}
deep :: Sized a => Digit a > FingerTree (Node a) > Digit a > FingerTree a
deep pr m sf = Deep (size pr + size m + size sf) pr m sf
hunk ./Data/Sequence.hs 307
+{# INLINE pullL #}
+pullL :: Sized a => Int > FingerTree (Node a) > Digit a > FingerTree a
+pullL s m sf = case viewLTree m of
+ Nothing2 > digitToTree' s sf
+ Just2 pr m' > Deep s (nodeToDigit pr) m' sf
+
+{# INLINE pullR #}
+pullR :: Sized a => Int > Digit a > FingerTree (Node a) > FingerTree a
+pullR s pr m = case viewRTree m of
+ Nothing2 > digitToTree' s pr
+ Just2 m' sf > Deep s pr m' (nodeToDigit sf)
+
+{# SPECIALIZE deepL :: Maybe (Digit (Elem a)) > FingerTree (Node (Elem a)) > Digit (Elem a) > FingerTree (Elem a) #}
+{# SPECIALIZE deepL :: Maybe (Digit (Node a)) > FingerTree (Node (Node a)) > Digit (Node a) > FingerTree (Node a) #}
+deepL :: Sized a => Maybe (Digit a) > FingerTree (Node a) > Digit a > FingerTree a
+deepL Nothing m sf = pullL (size m + size sf) m sf
+deepL (Just pr) m sf = deep pr m sf
+
+{# SPECIALIZE deepR :: Digit (Elem a) > FingerTree (Node (Elem a)) > Maybe (Digit (Elem a)) > FingerTree (Elem a) #}
+{# SPECIALIZE deepR :: Digit (Node a) > FingerTree (Node (Node a)) > Maybe (Digit (Node a)) > FingerTree (Node a) #}
+deepR :: Sized a => Digit a > FingerTree (Node a) > Maybe (Digit a) > FingerTree a
+deepR pr m Nothing = pullR (size m + size pr) pr m
+deepR pr m (Just sf) = deep pr m sf
+
 Digits
data Digit a
hunk ./Data/Sequence.hs 367
fmap = fmapDefault
instance Traversable Digit where
+ {# INLINE traverse #}
traverse f (One a) = One <$> f a
traverse f (Two a b) = Two <$> f a <*> f b
traverse f (Three a b c) = Three <$> f a <*> f b <*> f c
hunk ./Data/Sequence.hs 374
traverse f (Four a b c d) = Four <$> f a <*> f b <*> f c <*> f d
instance Sized a => Sized (Digit a) where
 {# SPECIALIZE instance Sized (Digit (Elem a)) #}
 {# SPECIALIZE instance Sized (Digit (Node a)) #}
 size xs = foldl (\ i x > i + size x) 0 xs
+ {# INLINE size #}
+ size = foldl1 (+) . fmap size
{# SPECIALIZE digitToTree :: Digit (Elem a) > FingerTree (Elem a) #}
{# SPECIALIZE digitToTree :: Digit (Node a) > FingerTree (Node a) #}
hunk ./Data/Sequence.hs 385
digitToTree (Three a b c) = deep (Two a b) Empty (One c)
digitToTree (Four a b c d) = deep (Two a b) Empty (Two c d)
+  Given the size of a digit and the digit itself, efficiently converts it to a FingerTree.
+digitToTree' :: Int > Digit a > FingerTree a
+digitToTree' n (Four a b c d) = Deep n (Two a b) Empty (Two c d)
+digitToTree' n (Three a b c) = Deep n (Two a b) Empty (One c)
+digitToTree' n (Two a b) = Deep n (One a) Empty (One b)
+digitToTree' n (One a) = n `seq` Single a
+
+
+
 Nodes
data Node a
hunk ./Data/Sequence.hs 411
foldl f z (Node3 _ a b c) = ((z `f` a) `f` b) `f` c
instance Functor Node where
+ {# INLINE fmap #}
fmap = fmapDefault
instance Traversable Node where
hunk ./Data/Sequence.hs 415
+ {# INLINE traverse #}
traverse f (Node2 v a b) = Node2 v <$> f a <*> f b
traverse f (Node3 v a b c) = Node3 v <$> f a <*> f b <*> f c
hunk ./Data/Sequence.hs 461
showsPrec p (Elem x) = showsPrec p x
#endif
+
+ Applicative construction
+
+
+newtype Id a = Id {runId :: a}
+
+instance Functor Id where
+ fmap f (Id x) = Id (f x)
+
+instance Monad Id where
+ return = Id
+ m >>= k = k (runId m)
+
+instance Applicative Id where
+ pure = return
+ (<*>) = ap
+
+  This is essentially a clone of Control.Monad.State.Strict.
+newtype State s a = State {runState :: s > (s, a)}
+
+instance Functor (State s) where
+ fmap = liftA
+
+instance Monad (State s) where
+ {# INLINE return #}
+ {# INLINE (>>=) #}
+ return x = State $ \ s > (s, x)
+ m >>= k = State $ \ s > case runState m s of
+ (s', x) > runState (k x) s'
+
+instance Applicative (State s) where
+ pure = return
+ (<*>) = ap
+
+execState :: State s a > s > a
+execState m x = snd (runState m x)
+
+  A helper method: a strict version of mapAccumL.
+mapAccumL' :: Traversable t => (a > b > (a, c)) > a > t b > (a, t c)
+mapAccumL' f s t = runState (traverse (State . flip f) t) s
+
+  'applicativeTree' takes an Applicativewrapped construction of a piece of a FingerTree, assumed
+ to always have the same size (which is put in the second argument), and replicates it as many times
+ as specified. This is a generalization of 'replicateA', which itself is a generalization of many
+ Data.Sequence methods.
+{# SPECIALIZE applicativeTree :: Int > Int > State s a > State s (FingerTree a) #}
+{# SPECIALIZE applicativeTree :: Int > Int > Id a > Id (FingerTree a) #}
+  Special note: the Id specialization automatically does node sharing, reducing memory usage of the
+  resulting tree to /O(log n)/.
+applicativeTree :: Applicative f => Int > Int > f a > f (FingerTree a)
+applicativeTree n mSize m = mSize `seq` case n of
+ 0 > pure Empty
+ 1 > liftA Single m
+ 2 > deepA one empty one
+ 3 > deepA two empty one
+ 4 > deepA two empty two
+ 5 > deepA three empty two
+ 6 > deepA three empty three
+ 7 > deepA four empty three
+ 8 > deepA four empty four
+ _ > let (q, r) = n `quotRem` 3 in q `seq` case r of
+ 0 > deepA three (applicativeTree (q  2) mSize' n3) three
+ 1 > deepA four (applicativeTree (q  2) mSize' n3) three
+ _ > deepA four (applicativeTree (q  2) mSize' n3) four
+ where one = liftA One m
+ two = liftA2 Two m m
+ three = liftA3 Three m m m
+ four = liftA3 Four m m m <*> m
+ deepA = liftA3 (Deep (n * mSize))
+ mSize' = 3 * mSize
+ n3 = liftA3 (Node3 mSize') m m m
+ empty = pure Empty
+

 Construction

hunk ./Data/Sequence.hs 546
singleton :: a > Seq a
singleton x = Seq (Single (Elem x))
+  /O(log n)/. @replicate n x@ is a sequence of length @n@ with @x@ the value of every element.
+replicate :: Int > a > Seq a
+replicate n x
+  n < 0 = error "replicate takes a nonnegative integer argument"
+  otherwise = runId (replicateA n (Id x))
+
+  'replicateA' is an 'Applicative' version of 'replicate', and makes /O(log n)/ calls to '<*>' and 'pure'. @'replicateA' n x@ is equivalent to @'sequenceA' ('replicate' n x)@.
+replicateA :: Applicative f => Int > f a > f (Seq a)
+replicateA n x
+  n < 0 = error "replicateA takes a nonnegative integer argument"
+  otherwise = Seq <$> applicativeTree n 1 (Elem <$> x)
+
+  'replicateM' is a generalization of 'Control.Monad.replicateM'.
+replicateM :: Monad m => Int > m a > m (Seq a)
+replicateM n x
+  n < 0 = error "replicateM takes a nonnegative integer argument"
+  otherwise = unwrapMonad (replicateA n (WrapMonad x))
+
  /O(1)/. Add an element to the left end of a sequence.
 Mnemonic: a triangle with the single element at the pointy end.
(<) :: a > Seq a > Seq a
hunk ./Data/Sequence.hs 838
addDigits4 m1 (Four a b c d) e f g h (Four i j k l) m2 =
appendTree4 m1 (node3 a b c) (node3 d e f) (node3 g h i) (node3 j k l) m2
+  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./
+unfoldr :: (b > Maybe (a, b)) > b > Seq a
+unfoldr f b = unfoldr' empty b where
+  uses tail recursion rather than, for instance, the List implementation.
+ unfoldr' as b = maybe as (\ (a, b') > unfoldr' (as > a) b') (f b)
+
+  @'unfoldl' f x@ is equivalent to @'reverse' ('unfoldr' f x)@.
+unfoldl :: (b > Maybe (b, a)) > b > Seq a
+unfoldl f b = unfoldl' empty b where
+ unfoldl' as b = maybe as (\ (b', a) > unfoldl' (a < as) b') (f b)
+
+  /O(n)/. Constructs a sequence by repeated application of a function to a seed value.
+
+ > iterateN n f x = fromList (Prelude.take n (Prelude.iterate f x))
+iterateN :: Int > (a > a) > a > Seq a
+iterateN n f x
+  n < 0 = error "iterateN takes a nonnegative integer argument"
+  otherwise = replicateA n (State (\ x > (f x, x))) `execState` x
+

 Deconstruction

hunk ./Data/Sequence.hs 922
viewLTree :: Sized a => FingerTree a > Maybe2 a (FingerTree a)
viewLTree Empty = Nothing2
viewLTree (Single a) = Just2 a Empty
viewLTree (Deep s (One a) m sf) = Just2 a (case viewLTree m of
 Nothing2 > digitToTree sf
 Just2 b m' > Deep (s  size a) (nodeToDigit b) m' sf)
+viewLTree (Deep s (One a) m sf) = Just2 a (pullL (s  size a) m sf)
viewLTree (Deep s (Two a b) m sf) =
Just2 a (Deep (s  size a) (One b) m sf)
viewLTree (Deep s (Three a b c) m sf) =
hunk ./Data/Sequence.hs 959
foldr f z (xs :> x) = foldr f (f x z) xs
foldl _ z EmptyR = z
 foldl f z (xs :> x) = f (foldl f z xs) x
+ foldl f z (xs :> x) = foldl f z xs `f` x
foldr1 _ EmptyR = error "foldr1: empty view"
foldr1 f (xs :> x) = foldr f x xs
hunk ./Data/Sequence.hs 979
viewRTree :: Sized a => FingerTree a > Maybe2 (FingerTree a) a
viewRTree Empty = Nothing2
viewRTree (Single z) = Just2 Empty z
viewRTree (Deep s pr m (One z)) = Just2 (case viewRTree m of
 Nothing2 > digitToTree pr
 Just2 m' y > Deep (s  size z) pr m' (nodeToDigit y)) z
+viewRTree (Deep s pr m (One z)) = Just2 (pullR (s  size z) pr m) z
viewRTree (Deep s pr m (Two y z)) =
Just2 (Deep (s  size z) pr m (One y)) z
viewRTree (Deep s pr m (Three x y z)) =
hunk ./Data/Sequence.hs 987
viewRTree (Deep s pr m (Four w x y z)) =
Just2 (Deep (s  size z) pr m (Three w x y)) z
+
+ Scans
+
+ These are not particularly complex applications of the Traversable
+ functor, though making the correspondence with Data.List exact
+ requires the use of (<) and (>).
+
+ Note that save for the single (<) or (>), we maintain the original
+ structure of the Seq, not having to do any restructuring of our own.
+
+ wasserman.louis@gmail.com, 5/23/09
+
+
+  'scanl' is similar to 'foldl', but returns a sequence of reduced values from the left:
+
+ > scanl f z (fromList [x1, x2, ...]) = fromList [z, z `f` x1, (z `f` x1) `f` x2, ...]
+scanl :: (a > b > a) > a > Seq b > Seq a
+scanl f z0 xs = z0 < snd (mapAccumL (\ x z > let x' = f x z in (x', x')) z0 xs)
+
+  'scanl1' is a variant of 'scanl' that has no starting value argument:
+
+ > scanl1 f (fromList [x1, x2, ...]) = fromList [x1, x1 `f` x2, ...]
+scanl1 :: (a > a > a) > Seq a > Seq a
+scanl1 f xs = case viewl xs of
+ EmptyL > error "scanl1 takes a nonempty sequence as an argument"
+ x :< xs' > scanl f x xs'
+
+  'scanr' is the righttoleft dual of 'scanl'.
+scanr :: (a > b > b) > b > Seq a > Seq b
+scanr f z0 xs = snd (mapAccumR (\ z x > let z' = f x z in (z', z')) z0 xs) > z0
+
+  'scanr1' is a variant of 'scanr' that has no starting value argument.
+scanr1 :: (a > a > a) > Seq a > Seq a
+scanr1 f xs = case viewr xs of
+ EmptyR > error "scanr1 takes a nonempty sequence as an argument"
+ xs' :> x > scanr f x xs'
+
 Indexing
  /O(log(min(i,ni)))/. The element at the specified position,
hunk ./Data/Sequence.hs 1152
sab = sa + size b
sabc = sab + size c
+  A generalization of 'fmap', 'mapWithIndex' takes a mapping function that also depends on the element's
+ index, and applies it to every element in the sequence.
+mapWithIndex :: (Int > a > b) > Seq a > Seq b
+mapWithIndex f xs = snd (mapAccumL' (\ i x > (i + 1, f i x)) 0 xs)
+
 Splitting
  /O(log(min(i,ni)))/. The first @i@ elements of a sequence.
hunk ./Data/Sequence.hs 1167
take i = fst . splitAt i
  /O(log(min(i,ni)))/. Elements of a sequence after the first @i@.
 If @i@ is negative, @'take' i s@ yields the whole sequence.
+ If @i@ is negative, @'drop' i s@ yields the whole sequence.
 If the sequence contains fewer than @i@ elements, the empty sequence
 is returned.
drop :: Int > Seq a > Seq a
hunk ./Data/Sequence.hs 1202
Split l x r > Split (maybe Empty digitToTree l) x (deepL r m sf)
 i < spm = case splitTree im m of
Split ml xs mr > case splitNode (im  size ml) xs of
 Split l x r > Split (deepR pr ml l) x (deepL r mr sf)
+ Split l x r > Split (deepR pr ml l) x (deepL r mr sf)
 otherwise = case splitDigit (i  spm) sf of
hunk ./Data/Sequence.hs 1204
 Split l x r > Split (deepR pr m l) x (maybe Empty digitToTree r)
+ Split l x r > Split (deepR pr m l) x (maybe Empty digitToTree r)
where spr = size pr
spm = spr + size m
im = i  spr
hunk ./Data/Sequence.hs 1209
{# SPECIALIZE deepL :: Maybe (Digit (Elem a)) > FingerTree (Node (Elem a)) > Digit (Elem a) > FingerTree (Elem a) #}
{# SPECIALIZE deepL :: Maybe (Digit (Node a)) > FingerTree (Node (Node a)) > Digit (Node a) > FingerTree (Node a) #}
deepL :: Sized a => Maybe (Digit a) > FingerTree (Node a) > Digit a > FingerTree a
deepL Nothing m sf = case viewLTree m of
 Nothing2 > digitToTree sf
 Just2 a m' > Deep (size m + size sf) (nodeToDigit a) m' sf
deepL (Just pr) m sf = deep pr m sf

{# SPECIALIZE deepR :: Digit (Elem a) > FingerTree (Node (Elem a)) > Maybe (Digit (Elem a)) > FingerTree (Elem a) #}
{# SPECIALIZE deepR :: Digit (Node a) > FingerTree (Node (Node a)) > Maybe (Digit (Node a)) > FingerTree (Node a) #}
deepR :: Sized a => Digit a > FingerTree (Node a) > Maybe (Digit a) > FingerTree a
deepR pr m Nothing = case viewRTree m of
 Nothing2 > digitToTree pr
 Just2 m' a > Deep (size pr + size m) pr m' (nodeToDigit a)
deepR pr m (Just sf) = deep pr m sf

{# SPECIALIZE splitNode :: Int > Node (Elem a) > Split (Maybe (Digit (Elem a))) (Elem a) #}
{# SPECIALIZE splitNode :: Int > Node (Node a) > Split (Maybe (Digit (Node a))) (Node a) #}
splitNode :: Sized a => Int > Node a > Split (Maybe (Digit a)) a
hunk ./Data/Sequence.hs 1245
where sa = size a
sab = sa + size b
sabc = sab + size c
+
+  /O(n)/. Returns a sequence of all suffixes of this sequence, longest first. For example,
+
+ > tails (fromList "abc") = fromList [fromList "abc", fromList "bc", fromList "c", fromList ""]
+
+ Evaluating the /i/th suffix takes /O(log(min(i, ni)))/, but evaluating every suffix in the sequence
+ takes /O(n)/ due to sharing.
+tails :: Seq a > Seq (Seq a)
+tails (Seq xs) = Seq (tailsTree (Elem . Seq) xs) > empty
+
+  /O(n)/. Returns a sequence of all prefixes of this sequence, shortest first. For example,
+
+ > inits (fromList "abc") = fromList [fromList "", fromList "a", fromList "ab", fromList "abc"]
+
+ Evaluating the /i/th prefix takes /O(log(min(i, ni)))/, but evaluating every prefix in the sequence
+ takes /O(n)/ due to sharing.
+inits :: Seq a > Seq (Seq a)
+inits (Seq xs) = empty < Seq (initsTree (Elem . Seq) xs)
+
+ This implementation of tails (and, analogously, inits) has the following algorithmic advantages:
+ Evaluating each tail in the sequence takes linear total time, which is better than we could say for
+ @fromList [drop n xs  n < [0..length xs]]@.
+ Evaluating any individual tail takes logarithmic time, which is better than we can say for either
+ @scanr (<) empty xs@ or @iterateN (length xs + 1) (\ xs > let _ :< xs' = viewl xs in xs') xs@.
+
+ Moreover, if we actually look at every tail in the sequence, the following benchmarks demonstrate that
+ this implementation is modestly faster than any of the above:
+
+ Times (ms)
+ min mean +/sd median max
+ Seq.tails: 21.986 24.961 10.169 22.417 86.485
+ scanr: 85.392 87.942 2.488 87.425 100.217
+ iterateN: 29.952 31.245 1.574 30.412 37.268
+
+ The algorithm for tails (and, analogously, inits) is as follows:
+
+ A Node in the FingerTree of tails is constructed by evaluating the corresponding tail of the FingerTree
+ of Nodes, considering the first Node in this tail, and constructing a Node in which each tail of this
+ Node is made to be the prefix of the remaining tree. This ends up working quite elegantly, as the remainder of
+ the tail of the FingerTree of Nodes becomes the middle of a new tail, the suffix of the Node is the
+ prefix, and the suffix of the original tree is retained.
+
+ In particular, evaluating the /i/th tail involves making as many partial evaluations as the Node depth of
+ the /i/th element. In addition, when we evaluate the /i/th tail, and we also evaluate the /j/th tail,
+ and /m/ Nodes are on the path to both /i/ and /j/, each of those /m/ evaluations are shared between
+ the computation of the /i/th and /j/th tails.
+
+ wasserman.louis@gmail.com, 7/16/09
+
+tailsDigit :: Digit a > Digit (Digit a)
+tailsDigit (One a) = One (One a)
+tailsDigit (Two a b) = Two (Two a b) (One b)
+tailsDigit (Three a b c) = Three (Three a b c) (Two b c) (One c)
+tailsDigit (Four a b c d) = Four (Four a b c d) (Three b c d) (Two c d) (One d)
+
+initsDigit :: Digit a > Digit (Digit a)
+initsDigit (One a) = One (One a)
+initsDigit (Two a b) = Two (One a) (Two a b)
+initsDigit (Three a b c) = Three (One a) (Two a b) (Three a b c)
+initsDigit (Four a b c d) = Four (One a) (Two a b) (Three a b c) (Four a b c d)
+
+tailsNode :: Node a > Node (Digit a)
+tailsNode (Node2 s a b) = Node2 s (Two a b) (One b)
+tailsNode (Node3 s a b c) = Node3 s (Three a b c) (Two b c) (One c)
+
+initsNode :: Node a > Node (Digit a)
+initsNode (Node2 s a b) = Node2 s (One a) (Two a b)
+initsNode (Node3 s a b c) = Node3 s (One a) (Two a b) (Three a b c)
+
+{# SPECIALIZE tailsTree :: (FingerTree (Elem a) > Elem b) > FingerTree (Elem a) > FingerTree (Elem b) #}
+{# SPECIALIZE tailsTree :: (FingerTree (Node a) > Node b) > FingerTree (Node a) > FingerTree (Node b) #}
+  Given a function to apply to tails of a tree, applies that function to every tail of the specified tree.
+tailsTree :: (Sized a, Sized b) => (FingerTree a > b) > FingerTree a > FingerTree b
+tailsTree _ Empty = Empty
+tailsTree f (Single x) = Single (f (Single x))
+tailsTree f (Deep n pr m sf) =
+ Deep n (fmap (\ pr' > f (deep pr' m sf)) (tailsDigit pr))
+ (tailsTree f' m)
+ (fmap (f . digitToTree) (tailsDigit sf))
+ where f' ms = let Just2 node m' = viewLTree ms in
+ fmap (\ pr' > f (deep pr' m' sf)) (tailsNode node)
+
+{# SPECIALIZE initsTree :: (FingerTree (Elem a) > Elem b) > FingerTree (Elem a) > FingerTree (Elem b) #}
+{# SPECIALIZE initsTree :: (FingerTree (Node a) > Node b) > FingerTree (Node a) > FingerTree (Node b) #}
+  Given a function to apply to inits of a tree, applies that function to every init of the specified tree.
+initsTree :: (Sized a, Sized b) => (FingerTree a > b) > FingerTree a > FingerTree b
+initsTree _ Empty = Empty
+initsTree f (Single x) = Single (f (Single x))
+initsTree f (Deep n pr m sf) =
+ Deep n (fmap (f . digitToTree) (initsDigit pr))
+ (initsTree f' m)
+ (fmap (f . deep pr m) (initsDigit sf))
+ where f' ms = let Just2 m' node = viewRTree ms in
+ fmap (\ sf' > f (deep pr m' sf')) (initsNode node)
hunk ./Data/Sequence.hs 1340
+{# INLINE foldWithIndexL #}
+  'foldWithIndexL' is a version of 'foldl' that also provides access to the index of each element.
+foldWithIndexL :: (b > Int > a > b) > b > Seq a > b
+foldWithIndexL f z xs = foldl (\ g x i > i `seq` f (g (i  1)) i x) (const z) xs (length xs  1)
+
+{# INLINE foldWithIndexR #}
+  'foldWithIndexR' is a version of 'foldr' that also provides access to the index of each element.
+foldWithIndexR :: (Int > a > b > b) > b > Seq a > b
+foldWithIndexR f z xs = foldr (\ x g i > i `seq` f i x (g (i+1))) (const z) xs 0
+
+{# INLINE [1] foldIndicesR #}
+  foldIndicesR folds in every satisfying value, from right to left.
+foldIndicesR :: (a > Bool) > Seq a > (Int > b > b) > b > b
+foldIndicesR p xs f z0 =
+ foldl (\ z x n > n `seq` if p x then f n (z (n1)) else z (n1))
+ (const z0) xs (length xs  1)
+
+{# INLINE listToMaybe' #}
+ 'listToMaybe\'' is a good consumer version of 'listToMaybe'.
+listToMaybe' :: [a] > Maybe a
+listToMaybe' = foldr (\ x _ > Just x) Nothing
+
+  /O(i)/ where /i/ is the prefix length. 'takeWhileL', applied to a predicate @p@ and a sequence @xs@, returns the
+ longest prefix (possibly empty) of @xs@ of elements that satisfy @p@.
+takeWhileL :: (a > Bool) > Seq a > Seq a
+takeWhileL p = fst . spanl p
+
+  /O(i)/ where /i/ is the suffix length. 'takeWhileR', applied to a predicate @p@ and a sequence @xs@, returns
+ the longest suffix (possibly empty) of @xs@ of elements that satisfy @p@.
+
+ @'takeWhileR' p xs@ is equivalent to @'reverse' ('takeWhileL' p ('reverse' xs))@.
+takeWhileR :: (a > Bool) > Seq a > Seq a
+takeWhileR p = fst . spanr p
+
+  /O(i)/ where /i/ is the prefix length. @'dropWhileL' p xs@ returns the suffix remaining after @'takeWhileL' p xs@.
+dropWhileL :: (a > Bool) > Seq a > Seq a
+dropWhileL p = snd . spanl p
+
+  /O(i)/ where /i/ is the suffix length. @'dropWhileR' p xs@ returns the prefix remaining after @'takeWhileR' p xs@.
+
+ @'dropWhileR' p xs@ is equivalent to @'reverse' ('dropWhileL' p ('reverse' xs))@.
+dropWhileR :: (a > Bool) > Seq a > Seq a
+dropWhileR p = snd . spanr p
+
+  /O(i)/ where /i/ is the prefix length. 'spanl', 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.
+spanl :: (a > Bool) > Seq a > (Seq a, Seq a)
+spanl p = breakl (not . p)
+
+  /O(i)/ where /i/ is the suffix length. 'spanr', applied to a predicate @p@ and a sequence @xs@, returns a tuple
+ whose /first/ element is the longest /suffix/ (possibly empty) of @xs@ of elements that satisfy @p@ and the second
+ element is the remainder of the sequence.
+spanr :: (a > Bool) > Seq a > (Seq a, Seq a)
+spanr p = breakr (not . p)
+
+{# INLINE breakl #}
+  /O(i)/ where /i/ is the breakpoint index. 'breakl', 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.
+
+ @'breakl' p@ is equivalent to @'spanl' (not . p)@.
+breakl :: (a > Bool) > Seq a > (Seq a, Seq a)
+breakl p xs = foldr (\ i _ > splitAt i xs) (xs, empty) (findIndicesL p xs)
+
+{# INLINE breakr #}
+  @'breakr' p@ is equivalent to @'spanr' (not . p)@.
+breakr :: (a > Bool) > Seq a > (Seq a, Seq a)
+breakr p xs = foldr (\ i _ > flipPair (splitAt i xs)) (xs, empty) (findIndicesR p xs) where
+ flipPair (x, y) = (y, x)
+
+  /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.
+partition :: (a > Bool) > Seq a > (Seq a, Seq a)
+partition p = foldl part (empty, empty) where
+ part (xs, ys) x
+  p x = (xs > x, ys)
+  otherwise = (xs, ys > x)
+
+  /O(n)/. The 'filter' function takes a predicate @p@ and a sequence @xs@ and returns a sequence of those
+ elements which satisfy the predicate.
+filter :: (a > Bool) > Seq a > Seq a
+filter p = foldl (\ xs x > if p x then xs > x else xs) empty
+
+ Indexing sequences
+
+  'elemIndexL' finds the first index of the specified element, if it is present.
+elemIndexL :: Eq a => a > Seq a > Maybe Int
+elemIndexL x = findIndexL (x ==)
+
+  'elemIndexR' finds the last index of the specified element, if it is present.
+elemIndexR :: Eq a => a > Seq a > Maybe Int
+elemIndexR x = findIndexR (x ==)
+
+  'elemIndicesL' finds the indices of the specified element, in ascending order.
+elemIndicesL :: Eq a => a > Seq a > [Int]
+elemIndicesL x = findIndicesL (x ==)
+
+  'elemIndicesR' finds the indices of the specified element, in descending order.
+elemIndicesR :: Eq a => a > Seq a > [Int]
+elemIndicesR x = findIndicesR (x ==)
+
+  @'findIndexL' p xs@ finds the index of the first element that satisfies @p@, if any exist.
+findIndexL :: (a > Bool) > Seq a > Maybe Int
+findIndexL p = listToMaybe' . findIndicesL p
+
+  @'findIndexR' p xs@ finds the index of the last element that satisfies @p@, if any exist.
+findIndexR :: (a > Bool) > Seq a > Maybe Int
+findIndexR p = listToMaybe' . findIndicesR p
+
+{# INLINE findIndicesL #}
+  @'findIndicesL' p@ finds all indices of elements that satisfy @p@, in ascending order.
+findIndicesL :: (a > Bool) > Seq a > [Int]
+#if __GLASGOW_HASKELL__
+findIndicesL p xs = build (\ c n > let g i x z = if p x then i `c` z else z in
+ foldWithIndexR g n xs)
+#else
+findIndicesL p xs = foldWithIndexR g [] xs where
+ g i x is = if p x then i:is else is
+#endif
+
+{# INLINE findIndicesR #}
+  @'findIndicesR' p@ finds all indices of elements that satisfy @p@, in descending order.
+findIndicesR :: (a > Bool) > Seq a > [Int]
+#if __GLASGOW_HASKELL__
+findIndicesR p xs = build (\ c n > let g z i x = if p x then i `c` z else z in
+ foldWithIndexL g n xs)
+#else
+findIndicesR p xs = foldWithIndexL g [] xs where
+ g is i x = if p x then i:is else is
+#endif
+

 Lists

hunk ./Data/Sequence.hs 1498
(reverseTree (reverseNode f) m)
(reverseDigit f pr)
+{# INLINE reverseDigit #}
reverseDigit :: (a > a) > Digit a > Digit a
reverseDigit f (One a) = One (f a)
reverseDigit f (Two a b) = Two (f b) (f a)
hunk ./Data/Sequence.hs 1509
reverseNode f (Node2 s a b) = Node2 s (f b) (f a)
reverseNode f (Node3 s a b c) = Node3 s (f c) (f b) (f a)
+
+ Zipping
+
+
+  /O(n)/. 'zip' takes two sequences and returns a sequence of corresponding pairs.
+ If one input is short, excess elements of the longer sequence are discarded.
+zip :: Seq a > Seq b > Seq (a, b)
+zip = zipWith (,)
+
+  /O(n)/. 'zipWith' generalizes 'zip' by zipping with the function given as the first argument,
+ instead of a tupling function. For example, @zipWith (+)@ is applied to two sequences to take
+ the sequence of corresponding sums.
+zipWith :: (a > b > c) > Seq a > Seq b > Seq c
+zipWith f xs ys
+  length xs <= length ys = zipWith' f xs ys
+  otherwise = zipWith' (flip f) ys xs
+ where zipWith' f xs ys = snd (mapAccumL ((\ (y :< ys) x > (ys, f x y)) . viewl) ys xs)
+
+zip3 :: Seq a > Seq b > Seq c > Seq (a,b,c)
+zip3 = zipWith3 (,,)
+
+zipWith3 :: (a > b > c > d) > Seq a > Seq b > Seq c > Seq d
+zipWith3 f s1 s2 s3 = zipWith ($) (zipWith f s1 s2) s3
+
+zip4 :: Seq a > Seq b > Seq c > Seq d > Seq (a,b,c,d)
+zip4 = zipWith4 (,,,)
+
+zipWith4 :: (a > b > c > d > e) > Seq a > Seq b > Seq c > Seq d > Seq e
+zipWith4 f s1 s2 s3 s4 = zipWith ($) (zipWith ($) (zipWith f s1 s2) s3) s4
+
+
+ Sorting
+
+ sort and sortBy are implemented by simple deforestations of
+ \ xs > fromList2 (length xs) . Data.List.sortBy cmp . toList
+ which does not get deforested automatically, it would appear.
+
+ Unstable sorting is performed by a heap sort implementation based on pairing heaps. Because the
+ internal structure of sequences is quite varied, it is difficult to get blocks of elements of
+ roughly the same length, which would improve merge sort performance. Pairing heaps, on the other
+ hand, are relatively resistant to the effects of merging heaps of wildly different sizes, as
+ guaranteed by its amortized constanttime merge operation. Moreover, extensive use of SpecConstr
+ transformations can be done on pairing heaps, especially when we're only constructing them
+ to immediately be unrolled.
+
+ On purely random sequences of length 50000, with no RTS options, I get the following statistics,
+ in which heapsort is about 42.5% faster: (all comparisons done with O2)
+
+ Times (ms) min mean +/sd median max
+ to/from list: 103.802 108.572 7.487 106.436 143.339
+ unstable heapsort: 60.686 62.968 4.275 61.187 79.151
+
+ Heapsort, it would seem, is less of a memory hog than Data.List.sortBy. The gap is narrowed
+ when more memory is available, but heapsort still wins, 15% faster, with +RTS H128m:
+
+ Times (ms) min mean +/sd median max
+ to/from list: 42.692 45.074 2.596 44.600 56.601
+ unstable heapsort: 37.100 38.344 3.043 37.715 55.526
+
+ In addition, on strictly increasing sequences the gap is even wider than normal; heapsort is
+ 68.5% faster with no RTS options:
+ Times (ms) min mean +/sd median max
+ to/from list: 52.236 53.574 1.987 53.034 62.098
+ unstable heapsort: 16.433 16.919 0.931 16.681 21.622
+
+ This may be attributed to the elegant nature of the pairing heap.
+
+ wasserman.louis@gmail.com, 7/20/09
+
+
+  /O(n log n)/. 'sort' sorts the specified 'Seq' by the natural ordering of its elements. The sort is stable.
+ If a stable sort is not required, 'unstableSort' can be considerably faster, and in particular uses less memory.
+sort :: Ord a => Seq a > Seq a
+sort = sortBy compare
+
+  /O(n log n)/. 'sortBy' sorts the specified 'Seq' according to the specified comparator. The sort is stable.
+ If a stable sort is not required, 'unstableSortBy' can be considerably faster, and in particular uses less memory.
+sortBy :: (a > a > Ordering) > Seq a > Seq a
+ fromList . Data.List.sortBy cmp . toList doesn't actually deforest well, so I did so manually and got a moderate
+ performance boost.
+sortBy cmp xs = case foldr (\ x > ([x]:)) [] xs of
+ [] > empty
+ ys:yss > fromList2 (length xs) (merger0 ys yss)
+ where xs@(x:xs1) <> ys@(y:ys1) = case cmp x y of
+ GT > y:(xs <> ys1)
+ _ > x:(xs1 <> ys)
+ [] <> ys = ys
+ xs <> [] = xs
+ merger (xs1:xs2:xss) = (xs1 <> xs2) : merger xss
+ merger xss = xss
+ merger0 xs1 (xs2:xss) = merger0 (xs1 <> xs2) (merger xss)
+ merger0 xs [] = xs
+
+  /O(n log n)/. 'unstableSort' sorts the specified 'Seq' by the natural ordering of its elements, but the sort is not stable.
+ This algorithm is frequently faster and uses less memory than 'sort', and performs extremely well  frequently twice as fast as
+ 'sort'  when the sequence is already nearly sorted.
+unstableSort :: Ord a => Seq a > Seq a
+unstableSort = unstableSortBy compare
+
+  /O(n log n)/. A generalization of 'unstableSort', 'unstableSortBy' takes an arbitrary comparator and sorts the specified sequence.
+ The sort is not stable. This algorithm is frequently faster and uses less memory than 'sortBy', and performs extremely well 
+ frequently twice as fast as 'sortBy'  when the sequence is already nearly sorted.
+unstableSortBy :: (a > a > Ordering) > Seq a > Seq a
+unstableSortBy cmp (Seq xs) = fromList2 (size xs) $ maybe [] (unrollPQ cmp) $ toPQ cmp (\ (Elem x) > PQueue x Nil) xs
+
+fromList2 :: Int > [a] > Seq a
+ fromList2, given a list and its length, constructs a completely balanced Seq whose elements are that list
+ using the applicativeTree generalization.
+fromList2 n = execState (replicateA n (State (\ (x:xs) > (xs, x))))
+
+  A 'PQueue' is a simple pairing heap.
+data PQueue e = PQueue e (PQL e)
+data PQL e = Nil  {# UNPACK #} !(PQueue e) :& PQL e
+
+infixr 8 :&
+
+#if TESTING
+
+instance Functor PQueue where
+ fmap f (PQueue x ts) = PQueue (f x) (fmap f ts)
+
+instance Functor PQL where
+ fmap f (q :& qs) = fmap f q :& fmap f qs
+ fmap _ Nil = Nil
+
+instance Show e => Show (PQueue e) where
+ show = unlines . draw . fmap show
+
+ borrowed wholesale from Data.Tree, as Data.Tree actually depends on Data.Sequence
+draw :: PQueue String > [String]
+draw (PQueue x ts0) = x : drawSubTrees ts0
+ where drawSubTrees Nil = []
+ drawSubTrees (t :& Nil) =
+ "" : shift "` " " " (draw t)
+ drawSubTrees (t :& ts) =
+ "" : shift "+ " " " (draw t) ++ drawSubTrees ts
+
+ shift first other = Data.List.zipWith (++) (first : repeat other)
+#endif
+
+  'unrollPQ', given a comparator function, unrolls a 'PQueue' into a sorted list.
+unrollPQ :: (e > e > Ordering) > PQueue e > [e]
+unrollPQ cmp = unrollPQ' where
+ {# INLINE unrollPQ' #}
+ unrollPQ' (PQueue x ts) = x:mergePQs0 ts
+ (<>) = mergePQ cmp
+ mergePQs0 Nil = []
+ mergePQs0 (t :& Nil) = unrollPQ' t
+ mergePQs0 (t1 :& t2 :& ts) = mergePQs (t1 <> t2) ts
+ mergePQs t ts = t `seq` case ts of
+ Nil > unrollPQ' t
+ t1 :& Nil > unrollPQ' (t <> t1)
+ t1 :& t2 :& ts > mergePQs (t <> (t1 <> t2)) ts
+
+  'toPQ', given an ordering function and a mechanism for queueifying elements, converts a 'FingerTree' to a 'PQueue'.
+toPQ :: (e > e > Ordering) > (a > PQueue e) > FingerTree a > Maybe (PQueue e)
+toPQ _ _ Empty = Nothing
+toPQ _ f (Single x) = Just (f x)
+toPQ cmp f (Deep _ pr m sf) = Just (maybe (pr' <> sf') ((pr' <> sf') <>) (toPQ cmp fNode m)) where
+ fDigit d = case fmap f d of
+ One a > a
+ Two a b > a <> b
+ Three a b c > a <> b <> c
+ Four a b c d > (a <> b) <> (c <> d)
+ (<>) = mergePQ cmp
+ fNode = fDigit . nodeToDigit
+ pr' = fDigit pr
+ sf' = fDigit sf
+
+  'mergePQ' merges two 'PQueue's.
+mergePQ :: (a > a > Ordering) > PQueue a > PQueue a > PQueue a
+mergePQ cmp q1@(PQueue x1 ts1) q2@(PQueue x2 ts2)
+  cmp x1 x2 == GT = PQueue x2 (q1 :& ts2)
+  otherwise = PQueue x1 (q2 :& ts1)
+
#if TESTING

hunk ./Data/Sequence.hs 1692
instance Arbitrary a => Arbitrary (Seq a) where
arbitrary = liftM Seq arbitrary
 coarbitrary (Seq x) = coarbitrary x
+ shrink (Seq x) = map Seq (shrink x)
instance Arbitrary a => Arbitrary (Elem a) where
arbitrary = liftM Elem arbitrary
hunk ./Data/Sequence.hs 1696
 coarbitrary (Elem x) = coarbitrary x
instance (Arbitrary a, Sized a) => Arbitrary (FingerTree a) where
arbitrary = sized arb
hunk ./Data/Sequence.hs 1704
arb 1 = liftM Single arbitrary
arb n = liftM3 deep arbitrary (arb (n `div` 2)) arbitrary
 coarbitrary Empty = variant 0
 coarbitrary (Single x) = variant 1 . coarbitrary x
 coarbitrary (Deep _ pr m sf) =
 variant 2 . coarbitrary pr . coarbitrary m . coarbitrary sf
+ shrink (Deep _ (One a) Empty (One b)) = [Single a, Single b]
+ shrink (Deep _ pr m sf) = [deep pr' m sf  pr' < shrink pr] ++ [deep pr m' sf  m' < shrink m] ++ [deep pr m sf'  sf' < shrink sf]
+ shrink (Single x) = map Single (shrink x)
+ shrink Empty = []
instance (Arbitrary a, Sized a) => Arbitrary (Node a) where
arbitrary = oneof [
hunk ./Data/Sequence.hs 1714
liftM2 node2 arbitrary arbitrary,
liftM3 node3 arbitrary arbitrary arbitrary]
 coarbitrary (Node2 _ a b) = variant 0 . coarbitrary a . coarbitrary b
 coarbitrary (Node3 _ a b c) =
 variant 1 . coarbitrary a . coarbitrary b . coarbitrary c
+ shrink (Node2 _ a b) = [node2 a' b  a' < shrink a] ++ [node2 a b'  b' < shrink b]
+ shrink (Node3 _ a b c) = [node2 a b, node2 a c, node2 b c] ++
+ [node3 a' b c  a' < shrink a] ++ [node3 a b' c  b' < shrink b] ++ [node3 a b c'  c' < shrink c]
instance Arbitrary a => Arbitrary (Digit a) where
arbitrary = oneof [
hunk ./Data/Sequence.hs 1724
liftM2 Two arbitrary arbitrary,
liftM3 Three arbitrary arbitrary arbitrary,
liftM4 Four arbitrary arbitrary arbitrary arbitrary]

 coarbitrary (One a) = variant 0 . coarbitrary a
 coarbitrary (Two a b) = variant 1 . coarbitrary a . coarbitrary b
 coarbitrary (Three a b c) =
 variant 2 . coarbitrary a . coarbitrary b . coarbitrary c
 coarbitrary (Four a b c d) =
 variant 3 . coarbitrary a . coarbitrary b . coarbitrary c . coarbitrary d
+
+ shrink (One a) = map One (shrink a)
+ shrink (Two a b) = [One a, One b]
+ shrink (Three a b c) = [Two a b, Two a c, Two b c]
+ shrink (Four a b c d) = [Three a b c, Three a b d, Three a c d, Three b c d]

 Valid trees
hunk ./Data/Sequence.hs 1750
s == size pr + size m + size sf && valid pr && valid m && valid sf
instance (Sized a, Valid a) => Valid (Node a) where
 valid (Node2 s a b) = s == size a + size b && valid a && valid b
 valid (Node3 s a b c) =
 s == size a + size b + size c && valid a && valid b && valid c
+ valid node = (size node == foldl1 (+) (fmap size node)) && (all valid node)
instance Valid a => Valid (Digit a) where
hunk ./Data/Sequence.hs 1753
 valid (One a) = valid a
 valid (Two a b) = valid a && valid b
 valid (Three a b c) = valid a && valid b && valid c
 valid (Four a b c d) = valid a && valid b && valid c && valid d
+ valid = all valid
#endif
hunk ./Data/Set.hs 122
#if __GLASGOW_HASKELL__
import Text.Read
import Data.Data (Data(..), mkNoRepType, gcast1)
+import Data.Data (Data(..), mkNorepType, gcast1)
#endif
{
hunk ./Data/Set.hs 165
gfoldl f z set = z fromList `f` (toList set)
toConstr _ = error "toConstr"
gunfold _ _ = error "gunfold"
 dataTypeOf _ = mkNoRepType "Data.Set.Set"
+ dataTypeOf _ = mkNorepType "Data.Set.Set"
dataCast1 f = gcast1 f
#endif
hunk ./containers.cabal 23
location: http://darcs.haskell.org/packages/containers/
Library {
 builddepends: base, array
+ builddepends: base >= 4.0.0.0, array
exposedmodules:
Data.Graph
Data.IntMap
}
Context:
[Use left/right rather than old/new to describe the arguments to unionWithKey
Ian Lynagh **20090208192132
Fixes trac #3002.
]
[help nhc98 by making import decl more explicit
Malcolm.Wallace@cs.york.ac.uk**20090203142144]
[Add instance Data.Traversable for IntMap
Matti Niemenmaa **20090116190353
Ignorethis: df88a286935926aecec3f8a5dd291699
]
[Require Cabal version >= 1.6
Ian Lynagh **20090122011256]
[Add "bugreports" and "sourcerepository" info to the Cabal file
Ian Lynagh **20090121182106]
[Fix warnings in containers
Ian Lynagh **20090116200251]
[optimize IntMap/IntSet findMin/findMax
sedillard@gmail.com**20081002152055]
[O(n) fromAscList IntSet / IntMap
sedillard@gmail.com**20080521195941
Added algorithm by Scott Dillard and Bertram Felgenhauer to build IntSets and
IntMaps from sorted input in linear time. Also changed quickcheck prop_Ordered
(no longer a tautology!) to include negative and duplicate keys.
]
[correct type for IntMap.intersectionWith[Key]
sedillard@gmail.com**20081002144828]
[Export mapAccumRWithKey from Map and IntMap (Trac #2769)
matti.niemenmaa+darcs@iki.fi**20081210160205]
[Bump the version number to 0.2.0.1, to workaround cabalinstall problems
Ian Lynagh **20081212201829]
[Fix #2760: change mkNorepType to mkNoRepType
'Jose Pedro Magalhaes '**20081202083424]
[Doc fix, from hackage trac #378
Ian Lynagh **20081024143949]
[import Data.Data instead of Data.Generics.*, eliminating the dependency on syb
Ross Paterson **20081005002559]
[fixed typo in highestBitMask
sedillard@gmail.com**20081002215438]
[export Data.Map.toDescList, foldlWithKey, and foldrWithKey (trac ticket 2580)
qdunkan@gmail.com**20080922213200
toDescList was previously implemented, but not exported.
foldlWithKey was previously implemented, but not exported. It can be used to
implement toDescList.
foldrWithKey is already exported as foldWithKey, but foldrWithKey is explicitly
the mirror of foldlWithKey, and foldWithKey kept for compatibility.
]
[Bump version number to 0.2.0.0
Ian Lynagh **20080920160016]
[TAG 6.10 branch has been forked
Ian Lynagh **20080919123438]
[Fixed typo in updateMinWithKey / updateMaxWithKey
sedillard@gmail.com**20080704054350]
[follow library changes
Ian Lynagh **20080903223610]
[add include/Typeable.h to extrasourcefiles
Ross Paterson **20080831181402]
[fix cabal builddepends for nhc98
Malcolm.Wallace@cs.york.ac.uk**20080828104248]
[Add a dep on syb
Ian Lynagh **20080825214314]
[add category field
Ross Paterson **20080824003013]
[we depend on st, now split off from base
Ian Lynagh **20080823223053]
[specialize functions that fail in a Monad to Maybe (proposal #2309)
Ross Paterson **20080722154812
Specialize functions signatures like
lookup :: (Monad m, Ord k) => k > Map k a > m a
to
lookup :: (Ord k) => k > Map k a > Maybe a
for simplicity and safety. No information is lost, as each of these
functions had only one use of fail, which is now changed to Nothing.
]
[tighter description of split (addresses #2447)
Ross Paterson **20080717064838]
[Make warningclean with GHC again
Ian Lynagh **20080623232023
With any luck we have now converged on a solution that works everywhere!
]
[Undo more Data.Typeablerelated breakage for nonghc.
Malcolm.Wallace@cs.york.ac.uk**20080623092757]
[Placate GHC with explicit import lists
Ian Lynagh **20080620183926]
[undo breakage caused by Wall cleaning
Malcolm.Wallace@cs.york.ac.uk**20080620093922
The import of Data.Typeable is still required, at least for nonGHC.
]
[Make the package Wall clean
Ian Lynagh **20080618233627]
[List particular extensions rather than fglasgowexts
Ian Lynagh **20080616232035]
[Avoid using deprecated flags
Ian Lynagh **20080616145241]
[TAG 20080528
Ian Lynagh **20080528004309]
Patch bundle hash:
6c3e5d64b47db0d11f2d860c23ad3d77430e8da6