Add concat and make concatMap more efficient
authorRoman Leshchinskiy <rl@cse.unsw.edu.au>
Wed, 5 May 2010 14:11:41 +0000 (14:11 +0000)
committerRoman Leshchinskiy <rl@cse.unsw.edu.au>
Wed, 5 May 2010 14:11:41 +0000 (14:11 +0000)
Data/Vector.hs
Data/Vector/Generic.hs
Data/Vector/Primitive.hs
Data/Vector/Storable.hs
Data/Vector/Unboxed.hs

index ec67c15..7b4f48e 100644 (file)
@@ -58,7 +58,7 @@ module Data.Vector (
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- ** Concatenation
-  cons, snoc, (++),
+  cons, snoc, (++), concat,
 
   -- ** Restricting memory usage
   force,
@@ -150,7 +150,7 @@ import Control.Monad.ST ( ST )
 import Control.Monad.Primitive
 
 import Prelude hiding ( length, null,
-                        replicate, (++),
+                        replicate, (++), concat,
                         head, last,
                         init, tail, take, drop, reverse,
                         map, concatMap,
@@ -496,6 +496,11 @@ infixr 5 ++
 {-# INLINE (++) #-}
 (++) = (G.++)
 
+-- | /O(n)/ Concatenate all vectors in the list
+concat :: [Vector a] -> Vector a
+{-# INLINE concat #-}
+concat = G.concat
+
 -- Monadic initialisation
 -- ----------------------
 
index 9c9fbe0..74e4bd3 100644 (file)
@@ -48,7 +48,7 @@ module Data.Vector.Generic (
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- ** Concatenation
-  cons, snoc, (++),
+  cons, snoc, (++), concat,
 
   -- ** Restricting memory usage
   force,
@@ -165,10 +165,10 @@ import Control.Monad.Primitive
 import qualified Control.Monad as Monad
 import qualified Data.List as List
 import Prelude hiding ( length, null,
-                        replicate, (++),
+                        replicate, (++), concat,
                         head, last,
                         init, tail, take, drop, reverse,
-                        map, concatMap,
+                        map, concat, concatMap,
                         zipWith, zipWith3, zip, zip3, unzip, unzip3,
                         filter, takeWhile, dropWhile, span, break,
                         elem, notElem,
@@ -561,6 +561,11 @@ infixr 5 ++
 {-# INLINE (++) #-}
 v ++ w = unstream (stream v Stream.++ stream w)
 
+-- | /O(n)/ Concatenate all vectors in the list
+concat :: Vector v a => [v a] -> v a
+{-# INLINE concat #-}
+concat vs = create (thawMany vs)
+
 -- Monadic initialisation
 -- ----------------------
 
@@ -823,7 +828,9 @@ imap f = unstream . inplace (MStream.map (uncurry f) . MStream.indexed)
 -- | Map a function over a vector and concatenate the results.
 concatMap :: (Vector v a, Vector v b) => (a -> v b) -> v a -> v b
 {-# INLINE concatMap #-}
-concatMap f = unstream . Stream.concatMap (stream . f) . stream
+-- NOTE: We can't fuse concatMap anyway so don't pretend we do.
+-- concatMap f = unstream . Stream.concatMap (stream . f) . stream
+concatMap f = concat . Stream.toList . Stream.map f . stream
 
 -- Monadic mapping
 -- ---------------
index 4694e12..5b7d1cc 100644 (file)
@@ -51,7 +51,7 @@ module Data.Vector.Primitive (
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- ** Concatenation
-  cons, snoc, (++),
+  cons, snoc, (++), concat,
 
   -- ** Restricting memory usage
   force,
@@ -140,7 +140,7 @@ import Control.Monad.ST ( ST )
 import Control.Monad.Primitive
 
 import Prelude hiding ( length, null,
-                        replicate, (++),
+                        replicate, (++), concat,
                         head, last,
                         init, tail, take, drop, reverse,
                         map, concatMap,
@@ -497,6 +497,11 @@ infixr 5 ++
 {-# INLINE (++) #-}
 (++) = (G.++)
 
+-- | /O(n)/ Concatenate all vectors in the list
+concat :: Prim a => [Vector a] -> Vector a
+{-# INLINE concat #-}
+concat = G.concat
+
 -- Monadic initialisation
 -- ----------------------
 
index 4da3532..51dbe7d 100644 (file)
@@ -48,7 +48,7 @@ module Data.Vector.Storable (
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- ** Concatenation
-  cons, snoc, (++),
+  cons, snoc, (++), concat,
 
   -- ** Restricting memory usage
   force,
@@ -143,7 +143,7 @@ import Control.Monad.ST ( ST )
 import Control.Monad.Primitive
 
 import Prelude hiding ( length, null,
-                        replicate, (++),
+                        replicate, (++), concat,
                         head, last,
                         init, tail, take, drop, reverse,
                         map, concatMap,
@@ -529,6 +529,11 @@ infixr 5 ++
 {-# INLINE (++) #-}
 (++) = (G.++)
 
+-- | /O(n)/ Concatenate all vectors in the list
+concat :: Storable a => [Vector a] -> Vector a
+{-# INLINE concat #-}
+concat = G.concat
+
 -- Monadic initialisation
 -- ----------------------
 
index ef9b0a5..f023560 100644 (file)
@@ -71,7 +71,7 @@ module Data.Vector.Unboxed (
   enumFromN, enumFromStepN, enumFromTo, enumFromThenTo,
 
   -- ** Concatenation
-  cons, snoc, (++),
+  cons, snoc, (++), concat,
 
   -- ** Restricting memory usage
   force,
@@ -161,7 +161,7 @@ import Control.Monad.ST ( ST )
 import Control.Monad.Primitive
 
 import Prelude hiding ( length, null,
-                        replicate, (++),
+                        replicate, (++), concat,
                         head, last,
                         init, tail, take, drop, reverse,
                         map, concatMap,
@@ -476,6 +476,11 @@ infixr 5 ++
 {-# INLINE (++) #-}
 (++) = (G.++)
 
+-- | /O(n)/ Concatenate all vectors in the list
+concat :: Unbox a => [Vector a] -> Vector a
+{-# INLINE concat #-}
+concat = G.concat
+
 -- Monadic initialisation
 -- ----------------------