Bryan O'Sullivan avatar Bryan O'Sullivan committed e795aa8

Replace isPrefix implementation with streamed version

Comments (0)

Files changed (3)

 {-# INLINE unwords #-}
 
 isPrefixOf :: Text -> Text -> Bool
-isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) = alen <= blen && loop 0 0
-    where loop !i !j | i >= alen = True
-                     | c == e    = loop (i+d) (j+f)
-                     | otherwise = False
-                     where (c,d) = iter a i
-                           (e,f) = iter b j
+isPrefixOf a@(Text _ _ alen) b@(Text _ _ blen) =
+    alen <= blen && S.isPrefixOf (stream a) (stream b)
 {-# INLINE [1] isPrefixOf #-}
 
+{-# RULES
+"TEXT isPrefixOf -> fused" [~1] forall s t.
+    isPrefixOf s t = S.isPrefixOf (stream s) (stream t)
+"TEXT isPrefixOf -> unfused" [1] forall s t.
+    S.isPrefixOf (stream s) (stream t) = isPrefixOf s t
+  #-}
+
 errorEmptyList :: String -> a
 errorEmptyList fun = error ("Data.Text." ++ fun ++ ": empty list")

Data/Text/Fusion.hs

     , takeWhile
     , dropWhile
 
+    -- * Predicates
+    , isPrefixOf
+
     -- * Searching
     , elem
     , filter
       Yield x s' -> Yield x (S2 :!: s')
 {-# INLINE [0] dropWhile #-}
 
+isPrefixOf :: (Eq a) => Stream a -> Stream a -> Bool
+isPrefixOf (Stream next1 s1 _) (Stream next2 s2 _) = loop (next1 s1) (next2 s2)
+    where
+      loop Done      _ = True
+      loop _    Done = False
+      loop (Skip s1')     (Skip s2')     = loop (next1 s1') (next2 s2')
+      loop (Skip s1')     x2             = loop (next1 s1') x2
+      loop x1             (Skip s2')     = loop x1          (next2 s2')
+      loop (Yield x1 s1') (Yield x2 s2') = x1 == x2 &&
+                                           loop (next1 s1') (next2 s2')
+{-# INLINE [0] isPrefixOf #-}
+{-# SPECIALISE isPrefixOf :: Stream Char -> Stream Char -> Bool #-}
+
 -- ----------------------------------------------------------------------------
 -- * Searching
 
                                        Yield b sb' -> Yield (f a b) (sa' :!: sb' :!: Nothing)
 {-# INLINE [0] zipWith #-}
 
+
 errorEmptyList :: String -> a
 errorEmptyList fun = error ("Data.Text.Fusion." ++ fun ++ ": empty list")

tests/Properties.hs

 prop_unwords         = L.unwords     `eq`  (unpack . T.unwords . map pack)
 
 prop_isPrefixOf s    = L.isPrefixOf s`eqP` T.isPrefixOf (pack s)
+prop_isPrefixOfS s    = L.isPrefixOf s`eqP` (S.isPrefixOf (stream $ pack s) . stream)
 
 prop_elem c          = L.elem c      `eqP` T.elem c
 prop_filter p        = L.filter p    `eqP` (unpack . T.filter p)
   ("prop_unwords", mytest prop_unwords),
 
   ("prop_isPrefixOf", mytest prop_isPrefixOf),
+  ("prop_isPrefixOfS", mytest prop_isPrefixOfS),
 
   ("prop_elem", mytest prop_elem),
   ("prop_filter", mytest prop_filter),
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.