Commits

Bryan O'Sullivan committed 9c2cd37

Implement and test lazy zipWith

  • Participants
  • Parent commits 8980730

Comments (0)

Files changed (6)

File Data/Text.hs

 -------------------------------------------------------------------------------
 -- ** Indexing 'Text's
 
--- | /O(1)/ 'Text' index (subscript) operator, starting from 0.
+-- | /O(n)/ 'Text' index (subscript) operator, starting from 0.
 index :: Text -> Int -> Char
 index t n = S.index (stream t) n
 {-# INLINE index #-}
 -- given as the first argument, instead of a tupling function.
 zipWith :: (Char -> Char -> Char) -> Text -> Text -> Text
 zipWith f t1 t2 = unstream (S.zipWith f (stream t1) (stream t2))
+{-# INLINE [0] zipWith #-}
 
 -- | /O(n)/ Breaks a 'Text' up into a list of words, delimited by 'Char's
 -- representing white space.

File Data/Text/Fusion.hs

     ) where
 
 import Prelude (Bool(..), Char, Eq(..), Maybe(..), Monad(..), Int,
-                Num(..), Ord(..), String, ($), (++), (&&),
+                Num(..), Ord(..), ($), (&&),
                 fromIntegral, otherwise)
 import Data.Bits ((.&.), shiftR)
 import Data.Char (ord)
 -------------------------------------------------------------------------------
 -- ** Indexing streams
 
--- | /O(1)/ stream index (subscript) operator, starting from 0.
+-- | /O(n)/ stream index (subscript) operator, starting from 0.
 index :: Stream Char -> Int -> Char
-index (Stream next s0 _len) n0
-  | n0 < 0    = streamError "index" "Negative index"
-  | otherwise = loop_index n0 s0
-  where
-    loop_index !n !s = case next s of
-      Done                   -> streamError "index" "Index too large"
-      Skip    s'             -> loop_index  n    s'
-      Yield x s' | n == 0    -> x
-                 | otherwise -> loop_index (n-1) s'
+index = S.indexI
 {-# INLINE [0] index #-}
 
 -- | The 'findIndex' function takes a predicate and a stream and
       Yield x s' | a == x    -> loop (i+1) s'
                  | otherwise -> loop i s'
 {-# INLINE [0] count #-}
-
-streamError :: String -> String -> a
-streamError func msg = P.error $ "Data.Text.Fusion." ++ func ++ ": " ++ msg

File Data/Text/Fusion/Common.hs

 
     -- * Indexing
     , find
+    , indexI
 
     -- * Zipping and unzipping
     , zipWith
                                   | otherwise -> loop_find s'
 {-# INLINE [0] find #-}
 
+-- | /O(n)/ Stream index (subscript) operator, starting from 0.
+indexI :: Integral a => Stream Char -> a -> Char
+indexI (Stream next s0 _len) n0
+  | n0 < 0    = streamError "index" "Negative index"
+  | otherwise = loop_index n0 s0
+  where
+    loop_index !n !s = case next s of
+      Done                   -> streamError "index" "Index too large"
+      Skip    s'             -> loop_index  n    s'
+      Yield x s' | n == 0    -> x
+                 | otherwise -> loop_index (n-1) s'
+{-# INLINE [0] indexI #-}
+
 -- | /O(n)/ 'filter', applied to a predicate and a stream,
 -- returns a stream containing those characters that satisfy the
 -- predicate.

File Data/Text/Lazy.hs

     -- , findSubstring
     
     -- * Indexing
-    -- , index
+    , index
     -- , findIndex
     -- , findIndices
     -- , elemIndex
     -- , count
 
     -- * Zipping and unzipping
-    -- , zipWith
+    , zipWith
 
     -- -* Ordered text
     -- , sort
 partition p t = (filter p t, filter (not . p) t)
 {-# INLINE partition #-}
 
+-- | /O(n)/ 'Text' index (subscript) operator, starting from 0.
+index :: Text -> Int64 -> Char
+index t n = S.index (stream t) n
+{-# INLINE index #-}
+
+-- | /O(n)/ 'zipWith' generalises 'zip' by zipping with the function
+-- given as the first argument, instead of a tupling function.
+zipWith :: (Char -> Char -> Char) -> Text -> Text -> Text
+zipWith f t1 t2 = unstream (S.zipWith f (stream t1) (stream t2))
+{-# INLINE [0] zipWith #-}
+
 revChunks :: [T.Text] -> Text
 revChunks = L.foldl' (flip chunk) Empty
 

File Data/Text/Lazy/Fusion.hs

     , unstreamChunks
     , length
     , unfoldrN
+    , index
     ) where
 
 import Prelude hiding (length)
 unfoldrN :: Int64 -> (a -> Maybe (Char,a)) -> a -> Stream Char
 unfoldrN n = S.unfoldrNI n
 {-# INLINE [0] unfoldrN #-}
+
+-- | /O(n)/ stream index (subscript) operator, starting from 0.
+index :: Stream Char -> Int64 -> Char
+index = S.indexI
+{-# INLINE [0] index #-}

File tests/Properties.hs

 prop_TL_partition p    = L.partition p `eqP` (unpack2 . TL.partition p)
 
 prop_T_index x s       = x < L.length s && x >= 0 ==>
-                       (L.!!) s x == T.index (packT s) x
+                         (L.!!) s x == T.index (packT s) x
 prop_T_findIndex p     = L.findIndex p `eqP` T.findIndex p
 prop_T_findIndices p   = L.findIndices p`eqP` T.findIndices p
 prop_T_elemIndex c     = L.elemIndex c `eqP` T.elemIndex c
 prop_T_elemIndices c   = L.elemIndices c`eqP` T.elemIndices c
 prop_T_count c         = (L.length . L.elemIndices c) `eqP` T.count c
 prop_T_zipWith c s     = L.zipWith c s `eqP` (unpackT . T.zipWith c (packT s))
+prop_TL_zipWith c s    = L.zipWith c s `eqP` (unpackT . TL.zipWith c (packT s))
 
 -- Regression tests.
 prop_S_filter_eq s = S.filter p t == S.streamList (filter p s)
   ("prop_T_elemIndices", mytest prop_T_elemIndices),
   ("prop_T_count", mytest prop_T_count),
   ("prop_T_zipWith", mytest prop_T_zipWith),
+  ("prop_TL_zipWith", mytest prop_TL_zipWith),
 
   ("prop_S_filter_eq", mytest prop_S_filter_eq)
   ]