Add foldr', foldr1', ifoldr'
authorRoman Leshchinskiy <rl@cse.unsw.edu.au>
Fri, 11 Dec 2009 01:52:15 +0000 (01:52 +0000)
committerRoman Leshchinskiy <rl@cse.unsw.edu.au>
Fri, 11 Dec 2009 01:52:15 +0000 (01:52 +0000)
Data/Vector.hs
Data/Vector/Fusion/Stream.hs
Data/Vector/Fusion/Stream/Monadic.hs
Data/Vector/Generic.hs
Data/Vector/Primitive.hs
Data/Vector/Storable.hs
Data/Vector/Unboxed.hs
tests/Tests/Vector.hs

index ec1fb73..e72279d 100644 (file)
@@ -55,8 +55,8 @@ module Data.Vector (
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  ifoldl, ifoldl', ifoldr,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
 
   -- * Specialised folds
   all, any, and, or,
@@ -612,6 +612,16 @@ foldr1 :: (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1 #-}
 foldr1 = G.foldr1
 
+-- | Right fold with a strict accumulator
+foldr' :: (a -> b -> b) -> b -> Vector a -> b
+{-# INLINE foldr' #-}
+foldr' = G.foldr'
+
+-- | Right fold on non-empty vectors with strict accumulator
+foldr1' :: (a -> a -> a) -> Vector a -> a
+{-# INLINE foldr1' #-}
+foldr1' = G.foldr1'
+
 -- | Left fold (function applied to each element and its index)
 ifoldl :: (a -> Int -> b -> a) -> a -> Vector b -> a
 {-# INLINE ifoldl #-}
@@ -628,6 +638,12 @@ ifoldr :: (Int -> a -> b -> b) -> b -> Vector a -> b
 {-# INLINE ifoldr #-}
 ifoldr = G.ifoldr
 
+-- | Right fold with strict accumulator (function applied to each element and
+-- its index)
+ifoldr' :: (Int -> a -> b -> b) -> b -> Vector a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' = G.ifoldr'
+
 -- Specialised folds
 -- -----------------
 
index ae9a225..be0f801 100644 (file)
@@ -38,7 +38,7 @@ module Data.Vector.Fusion.Stream (
   map, concatMap, unbox,
   
   -- * Zipping
-  indexed,
+  indexed, indexedR,
   zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
   zip, zip3, zip4, zip5, zip6,
 
@@ -250,11 +250,17 @@ concatMap = M.concatMap
 -- Zipping
 -- -------
 
--- | Associate all 'Stream' elements with their indices
+-- | Pair each element in a 'Stream' with its index
 indexed :: Stream a -> Stream (Int,a)
 {-# INLINE indexed #-}
 indexed = M.indexed
 
+-- | Pair each element in a 'Stream' with its index, starting from the right
+-- and counting down
+indexedR :: Int -> Stream a -> Stream (Int,a)
+{-# INLINE_STREAM indexedR #-}
+indexedR = M.indexedR
+
 -- | Zip two 'Stream's with the given function
 zipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
 {-# INLINE zipWith #-}
index a81551a..02fb0c1 100644 (file)
@@ -34,7 +34,7 @@ module Data.Vector.Fusion.Stream.Monadic (
   map, mapM, mapM_, trans, unbox, concatMap,
   
   -- * Zipping
-  indexed,
+  indexed, indexedR,
   zipWithM, zipWith3M, zipWith4M, zipWith5M, zipWith6M,
   zipWith, zipWith3, zipWith4, zipWith5, zipWith6,
   zip, zip3, zip4, zip5, zip6,
@@ -425,6 +425,23 @@ indexed (Stream step s n) = Stream step' (s,0) n
                       Skip    s' -> return $ Skip        (s', i)
                       Done       -> return Done
 
+-- | Pair each element in a 'Stream' with its index, starting from the right
+-- and counting down
+indexedR :: Monad m => Int -> Stream m a -> Stream m (Int,a)
+{-# INLINE_STREAM indexedR #-}
+indexedR m (Stream step s n) = Stream step' (s,m) n
+  where
+    {-# INLINE_INNER step' #-}
+    step' (s,i) = i `seq`
+                  do
+                    r <- step s
+                    case r of
+                      Yield x s' -> let i' = i-1
+                                    in
+                                    return $ Yield (i',x) (s', i')
+                      Skip    s' -> return $ Skip         (s', i)
+                      Done       -> return Done
+
 -- | Zip two 'Stream's with the given monadic function
 zipWithM :: Monad m => (a -> b -> m c) -> Stream m a -> Stream m b -> Stream m c
 {-# INLINE_STREAM zipWithM #-}
index 6fb407a..e6f8f3c 100644 (file)
@@ -59,8 +59,8 @@ module Data.Vector.Generic (
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  ifoldl, ifoldl', ifoldr,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
  
   -- * Specialised folds
   all, any, and, or,
@@ -993,6 +993,16 @@ foldr1 :: Vector v a => (a -> a -> a) -> v a -> a
 {-# INLINE foldr1 #-}
 foldr1 f = Stream.foldr1 f . stream
 
+-- | Right fold with a strict accumulator
+foldr' :: Vector v a => (a -> b -> b) -> b -> v a -> b
+{-# INLINE foldr' #-}
+foldr' f z = Stream.foldl' (flip f) z . streamR
+
+-- | Right fold on non-empty vectors with strict accumulator
+foldr1' :: Vector v a => (a -> a -> a) -> v a -> a
+{-# INLINE foldr1' #-}
+foldr1' f = Stream.foldl1' (flip f) . streamR
+
 -- | Left fold (function applied to each element and its index)
 ifoldl :: Vector v b => (a -> Int -> b -> a) -> a -> v b -> a
 {-# INLINE ifoldl #-}
@@ -1009,6 +1019,13 @@ ifoldr :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
 {-# INLINE ifoldr #-}
 ifoldr f z = Stream.foldr (uncurry f) z . Stream.indexed . stream
 
+-- | Right fold with strict accumulator (function applied to each element and
+-- its index)
+ifoldr' :: Vector v a => (Int -> a -> b -> b) -> b -> v a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' f z xs = Stream.foldl' (flip (uncurry f)) z
+               $ Stream.indexedR (length xs) $ streamR xs
+
 -- Specialised folds
 -- -----------------
 
index ecdc46e..d4cf10b 100644 (file)
@@ -51,8 +51,8 @@ module Data.Vector.Primitive (
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  ifoldl, ifoldl', ifoldr,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
 
   -- * Specialised folds
   all, any,
@@ -563,6 +563,16 @@ foldr1 :: Prim a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1 #-}
 foldr1 = G.foldr1
 
+-- | Right fold with a strict accumulator
+foldr' :: Prim a => (a -> b -> b) -> b -> Vector a -> b
+{-# INLINE foldr' #-}
+foldr' = G.foldr'
+
+-- | Right fold on non-empty vectors with strict accumulator
+foldr1' :: Prim a => (a -> a -> a) -> Vector a -> a
+{-# INLINE foldr1' #-}
+foldr1' = G.foldr1'
+
 -- | Left fold (function applied to each element and its index)
 ifoldl :: Prim b => (a -> Int -> b -> a) -> a -> Vector b -> a
 {-# INLINE ifoldl #-}
@@ -579,6 +589,12 @@ ifoldr :: Prim a => (Int -> a -> b -> b) -> b -> Vector a -> b
 {-# INLINE ifoldr #-}
 ifoldr = G.ifoldr
 
+-- | Right fold with strict accumulator (function applied to each element and
+-- its index)
+ifoldr' :: Prim a => (Int -> a -> b -> b) -> b -> Vector a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' = G.ifoldr'
+
 -- Specialised folds
 -- -----------------
 
index 31aa67d..bab7c27 100644 (file)
@@ -51,8 +51,8 @@ module Data.Vector.Storable (
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  ifoldl, ifoldl', ifoldr,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
 
   -- * Specialised folds
   all, any, and, or,
@@ -599,6 +599,16 @@ foldr1 :: Storable a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1 #-}
 foldr1 = G.foldr1
 
+-- | Right fold with a strict accumulator
+foldr' :: Storable a => (a -> b -> b) -> b -> Vector a -> b
+{-# INLINE foldr' #-}
+foldr' = G.foldr'
+
+-- | Right fold on non-empty vectors with strict accumulator
+foldr1' :: Storable a => (a -> a -> a) -> Vector a -> a
+{-# INLINE foldr1' #-}
+foldr1' = G.foldr1'
+
 -- | Left fold (function applied to each element and its index)
 ifoldl :: Storable b => (a -> Int -> b -> a) -> a -> Vector b -> a
 {-# INLINE ifoldl #-}
@@ -615,6 +625,12 @@ ifoldr :: Storable a => (Int -> a -> b -> b) -> b -> Vector a -> b
 {-# INLINE ifoldr #-}
 ifoldr = G.ifoldr
 
+-- | Right fold with strict accumulator (function applied to each element and
+-- its index)
+ifoldr' :: Storable a => (Int -> a -> b -> b) -> b -> Vector a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' = G.ifoldr'
+
 -- Specialised folds
 -- -----------------
 
index 3d3f198..2c6c5d2 100644 (file)
@@ -53,8 +53,8 @@ module Data.Vector.Unboxed (
   elem, notElem, find, findIndex, findIndices, elemIndex, elemIndices,
 
   -- * Folding
-  foldl, foldl1, foldl', foldl1', foldr, foldr1,
-  ifoldl, ifoldl', ifoldr,
+  foldl, foldl1, foldl', foldl1', foldr, foldr1, foldr', foldr1',
+  ifoldl, ifoldl', ifoldr, ifoldr',
 
   -- * Specialised folds
   all, any, and, or,
@@ -557,6 +557,16 @@ foldr1 :: Unbox a => (a -> a -> a) -> Vector a -> a
 {-# INLINE foldr1 #-}
 foldr1 = G.foldr1
 
+-- | Right fold with a strict accumulator
+foldr' :: Unbox a => (a -> b -> b) -> b -> Vector a -> b
+{-# INLINE foldr' #-}
+foldr' = G.foldr'
+
+-- | Right fold on non-empty vectors with strict accumulator
+foldr1' :: Unbox a => (a -> a -> a) -> Vector a -> a
+{-# INLINE foldr1' #-}
+foldr1' = G.foldr1'
+
 -- | Left fold (function applied to each element and its index)
 ifoldl :: Unbox b => (a -> Int -> b -> a) -> a -> Vector b -> a
 {-# INLINE ifoldl #-}
@@ -573,6 +583,12 @@ ifoldr :: Unbox a => (Int -> a -> b -> b) -> b -> Vector a -> b
 {-# INLINE ifoldr #-}
 ifoldr = G.ifoldr
 
+-- | Right fold with strict accumulator (function applied to each element and
+-- its index)
+ifoldr' :: Unbox a => (Int -> a -> b -> b) -> b -> Vector a -> b
+{-# INLINE ifoldr' #-}
+ifoldr' = G.ifoldr'
+
 -- Specialised folds
 -- -----------------
 
index 279ed2f..ce46d84 100644 (file)
@@ -101,8 +101,8 @@ testPolymorphicFunctions _ = $(testProperties [
         'prop_elemIndex, 'prop_elemIndices,
 
         'prop_foldl, 'prop_foldl1, 'prop_foldl', 'prop_foldl1',
-        'prop_foldr, 'prop_foldr1,
-        'prop_ifoldl, 'prop_ifoldl', 'prop_ifoldr,
+        'prop_foldr, 'prop_foldr1, 'prop_foldr', 'prop_foldr1',
+        'prop_ifoldl, 'prop_ifoldl', 'prop_ifoldr, 'prop_ifoldr',
 
         'prop_all, 'prop_any,
 
@@ -220,12 +220,17 @@ testPolymorphicFunctions _ = $(testProperties [
     prop_foldr :: P ((a -> a -> a) -> a -> v a -> a) = V.foldr `eq` foldr
     prop_foldr1 :: P ((a -> a -> a) -> v a -> a)     = notNull2 ===>
                         V.foldr1 `eq` foldr1
+    prop_foldr' :: P ((a -> a -> a) -> a -> v a -> a) = V.foldr' `eq` foldr
+    prop_foldr1' :: P ((a -> a -> a) -> v a -> a)     = notNull2 ===>
+                        V.foldr1' `eq` foldr1
     prop_ifoldl :: P ((a -> Int -> a -> a) -> a -> v a -> a)
         = V.ifoldl `eq` ifoldl
     prop_ifoldl' :: P ((a -> Int -> a -> a) -> a -> v a -> a)
         = V.ifoldl' `eq` ifoldl
     prop_ifoldr :: P ((Int -> a -> a -> a) -> a -> v a -> a)
         = V.ifoldr `eq` ifoldr
+    prop_ifoldr' :: P ((Int -> a -> a -> a) -> a -> v a -> a)
+        = V.ifoldr' `eq` ifoldr
 
     prop_all :: P ((a -> Bool) -> v a -> Bool) = V.all `eq` all
     prop_any :: P ((a -> Bool) -> v a -> Bool) = V.any `eq` any