Commits

Bryan O'Sullivan  committed a664db1

Implement and test lazy scanr and reverse

  • Participants
  • Parent commits 903c2a7

Comments (0)

Files changed (3)

File Data/Text.hs

 
 -- | /O(n)/ 'scanr' is the right-to-left dual of 'scanl'.
 --
--- > scanr f v t == reverse (scanl (flip f) v t)
+-- > scanr f v == reverse . scanl (flip f) v . reverse
 scanr :: (Char -> Char -> Char) -> Char -> Text -> Text
 scanr f z = S.reverse . S.reverseScanr f z . reverseStream
 {-# INLINE scanr #-}

File Data/Text/Lazy.hs

     , intercalate
     , intersperse
     , transpose
-    -- , reverse
+    , reverse
 
     -- * Folds
     , foldl
     -- ** Scans
     , scanl
     , scanl1
-    -- , scanr
+    , scanr
     -- , scanr1
 
     -- ** Accumulating maps
                      (L.transpose (L.map unpack ts))
 -- TODO: make this fast
 
+-- | /O(n)/ 'reverse' @t@ returns the elements of @t@ in reverse order.
+reverse :: Text -> Text
+reverse = rev Empty
+  where rev a Empty        = a
+        rev a (Chunk t ts) = rev (Chunk (T.reverse t) a) ts
+
 -- | /O(n)/ 'foldl', applied to a binary operator, a starting value
 -- (typically the left-identity of the operator), and a 'Text',
 -- reduces the 'Text' using the binary operator, from left to right.
                 Just (t,ts) -> scanl f t ts
 {-# INLINE scanl1 #-}
 
+-- | /O(n)/ 'scanr' is the right-to-left dual of 'scanl'.
+--
+-- > scanr f v == reverse . scanl (flip f) v . reverse
+scanr :: (Char -> Char -> Char) -> Char -> Text -> Text
+scanr f v = reverse . scanl (flip f) v . reverse
+
 -- | /O(n)/ Like a combination of 'map' and 'foldl'. Applies a
 -- function to each element of a 'Text', passing an accumulating
 -- parameter from left to right, and returns a final 'Text'.

File tests/Properties.hs

 prop_T_transpose       = L.transpose `eq` (map unpackT . T.transpose . map T.pack)
 prop_TL_transpose      = L.transpose `eq` (map unpackT . TL.transpose . map TL.pack)
 prop_T_reverse         = L.reverse `eqP` (unpackT . T.reverse)
+prop_TL_reverse        = L.reverse `eqP` (unpackT . TL.reverse)
 prop_T_reverse_short n = L.reverse `eqP` (unpackT . S.reverse . shorten n . S.stream)
 
 prop_T_foldl f z       = L.foldl f z  `eqP`  (T.foldl f z)
 prop_T_scanl1 f        = L.scanl1 f    `eqP`  (unpackT . T.scanl1 f)
 prop_TL_scanl1 f       = L.scanl1 f    `eqP`  (unpackT . TL.scanl1 f)
 prop_T_scanr f z       = L.scanr f z   `eqP`  (unpackT . T.scanr f z)
+prop_TL_scanr f z      = L.scanr f z   `eqP`  (unpackT . TL.scanr f z)
 prop_T_scanr1 f        = L.scanr1 f    `eqP`  (unpackT . T.scanr1 f)
 
 prop_T_mapAccumL f z   = L.mapAccumL f z `eqP` (second unpackT . T.mapAccumL f z)
   ("prop_T_transpose", mytest prop_T_transpose),
   ("prop_TL_transpose", mytest prop_TL_transpose),
   ("prop_T_reverse", mytest prop_T_reverse),
+  ("prop_TL_reverse", mytest prop_TL_reverse),
   ("prop_T_reverse_short", mytest prop_T_reverse_short),
 
   ("prop_T_foldl", mytest prop_T_foldl),
   ("prop_T_scanl1", mytest prop_T_scanl1),
   ("prop_TL_scanl1", mytest prop_TL_scanl1),
   ("prop_T_scanr", mytest prop_T_scanr),
+  ("prop_TL_scanr", mytest prop_TL_scanr),
   ("prop_T_scanr1", mytest prop_T_scanr1),
 
   ("prop_T_mapAccumL", mytest prop_T_mapAccumL),