Implementation of and and or that can bail out early
authorMax Bolingbroke <batterseapower@hotmail.com>
Sun, 8 Feb 2009 09:12:21 +0000 (09:12 +0000)
committerMax Bolingbroke <batterseapower@hotmail.com>
Sun, 8 Feb 2009 09:12:21 +0000 (09:12 +0000)
Data/Vector/Fusion/Stream.hs
Data/Vector/Fusion/Stream/Monadic.hs
Data/Vector/IVector.hs

index 22fdfde..661fe33 100644 (file)
@@ -45,6 +45,9 @@ module Data.Vector.Fusion.Stream (
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1,
 
+  -- * Specialised folds
+  and, or,
+
   -- * Unfolding
   unfoldr,
 
@@ -70,6 +73,7 @@ import Prelude hiding ( length, null,
                         filter, takeWhile, dropWhile,
                         elem, notElem,
                         foldl, foldl1, foldr, foldr1,
+                        and, or,
                         mapM_ )
 
 
@@ -290,6 +294,15 @@ foldr1 :: (a -> a -> a) -> Stream a -> a
 {-# INLINE foldr1 #-}
 foldr1 f = unId . M.foldr1 f
 
+-- Specialised folds
+-- -----------------
+
+and :: Stream Bool -> Bool
+and = unId . M.and
+
+or :: Stream Bool -> Bool
+or = unId . M.or
+
 -- Unfolding
 -- ---------
 
index c3fafe1..b149caa 100644 (file)
@@ -46,6 +46,9 @@ module Data.Vector.Fusion.Stream.Monadic (
   foldl', foldlM', foldl1', foldl1M',
   foldr, foldrM, foldr1, foldr1M,
 
+  -- * Specialised folds
+  and, or,
+
   -- * Unfolding
   unfoldr, unfoldrM,
 
@@ -66,7 +69,8 @@ import Prelude hiding ( length, null,
                         map, mapM, mapM_, zipWith,
                         filter, takeWhile, dropWhile,
                         elem, notElem,
-                        foldl, foldl1, foldr, foldr1 )
+                        foldl, foldl1, foldr, foldr1,
+                        and, or )
 import qualified Prelude
 
 -- | Result of taking a single step in a stream
@@ -624,6 +628,31 @@ foldr1M f (Stream step s _) = foldr1M_go0 s
                           Skip    s' -> foldr1M_go1 x s'
                           Done       -> return x
 
+-- Specialised folds
+-- -----------------
+
+and :: Monad m => Stream m Bool -> m Bool
+and (Stream step s _) = and_go s
+  where
+    and_go s = do
+                 r <- step s
+                 case r of
+                   Yield False _  -> return False
+                   Yield True  s' -> and_go s'
+                   Skip        s' -> and_go s'
+                   Done           -> return True
+
+or :: Monad m => Stream m Bool -> m Bool
+or (Stream step s _) = or_go s
+  where
+    or_go s = do
+                r <- step s
+                case r of
+                  Yield False s' -> or_go s'
+                  Yield True  _  -> return True
+                  Skip        s' -> or_go s'
+                  Done           -> return False
+
 -- Unfolding
 -- ---------
 
index 47066cc..0c9a59a 100644 (file)
@@ -496,11 +496,11 @@ foldr1 f = Stream.foldr1 f . stream
 
 and :: IVector v Bool => v Bool -> Bool
 {-# INLINE and #-}
-and = foldl' (&&) True
+and = Stream.and . stream
 
 or :: IVector v Bool => v Bool -> Bool
 {-# INLINE or #-}
-or = foldl' (||) False
+or = Stream.or . stream
 
 -- Enumeration
 -- -----------