Search functions
authorRoman Leshchinskiy <rl@cse.unsw.edu.au>
Sat, 12 Jul 2008 04:16:28 +0000 (04:16 +0000)
committerRoman Leshchinskiy <rl@cse.unsw.edu.au>
Sat, 12 Jul 2008 04:16:28 +0000 (04:16 +0000)
Data/Vector/IVector.hs
Data/Vector/Stream.hs

index d3b4c2f..01e2378 100644 (file)
@@ -32,6 +32,9 @@ module Data.Vector.IVector (
   -- * Filtering
   filter, takeWhile, dropWhile,
 
   -- * Filtering
   filter, takeWhile, dropWhile,
 
+  -- * Searching
+  elem, notElem, find, findIndex,
+
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1,
 
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1,
 
@@ -63,6 +66,7 @@ import Prelude hiding ( length,
                         init, tail, take, drop,
                         map, zipWith,
                         filter, takeWhile, dropWhile,
                         init, tail, take, drop,
                         map, zipWith,
                         filter, takeWhile, dropWhile,
+                        elem, notElem,
                         foldl, foldl1, foldr, foldr1 )
 
 -- | Class of immutable vectors. Just like with 'MVector', the type of the
                         foldl, foldl1, foldr, foldr1 )
 
 -- | Class of immutable vectors. Just like with 'MVector', the type of the
@@ -221,6 +225,33 @@ dropWhile :: IVector v a => (a -> Bool) -> v a -> v a
 {-# INLINE dropWhile #-}
 dropWhile f = unstream . Stream.dropWhile f . stream
 
 {-# INLINE dropWhile #-}
 dropWhile f = unstream . Stream.dropWhile f . stream
 
+-- Searching
+-- ---------
+
+infix 4 `elem`
+-- | Check whether the vector contains an element
+elem :: (IVector v a, Eq a) => a -> v a -> Bool
+{-# INLINE elem #-}
+elem x = Stream.elem x . stream
+
+infix 4 `notElem`
+-- | Inverse of `elem`
+notElem :: (IVector v a, Eq a) => a -> v a -> Bool
+{-# INLINE notElem #-}
+notElem x = Stream.notElem x . stream
+
+-- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
+-- such element exists.
+find :: IVector v a => (a -> Bool) -> v a -> Maybe a
+{-# INLINE find #-}
+find f = Stream.find f . stream
+
+-- | Yield 'Just' the index of the first element matching the predicate or
+-- 'Nothing' if no such element exists.
+findIndex :: IVector v a => (a -> Bool) -> v a -> Maybe Int
+{-# INLINE findIndex #-}
+findIndex f = Stream.findIndex f . stream
+
 -- Folding
 -- -------
 
 -- Folding
 -- -------
 
index 6980de7..cd77330 100644 (file)
@@ -39,6 +39,9 @@ module Data.Vector.Stream (
   -- * Filtering
   filter, takeWhile, dropWhile,
 
   -- * Filtering
   filter, takeWhile, dropWhile,
 
+  -- * Searching
+  elem, notElem, find, findIndex,
+
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1,
 
   -- * Folding
   foldl, foldl1, foldl', foldl1', foldr, foldr1,
 
@@ -60,6 +63,7 @@ import Prelude hiding ( length, null,
                         init, tail, take, drop,
                         map, zipWith,
                         filter, takeWhile, dropWhile,
                         init, tail, take, drop,
                         map, zipWith,
                         filter, takeWhile, dropWhile,
+                        elem, notElem,
                         foldl, foldl1, foldr, foldr1,
                         mapM_ )
 
                         foldl, foldl1, foldr, foldr1,
                         mapM_ )
 
@@ -355,6 +359,51 @@ dropWhile f (Stream step s n) = Stream step' (DropWhile_Drop s) (toMax n)
                                  Skip    s' -> Skip    (DropWhile_Next    s')
                                  Done       -> Done
 
                                  Skip    s' -> Skip    (DropWhile_Next    s')
                                  Done       -> Done
 
+-- Searching
+-- ---------
+
+infix 4 `elem`
+-- | Check whether the 'Stream' contains an element
+elem :: Eq a => a -> Stream a -> Bool
+{-# INLINE_STREAM elem #-}
+elem x (Stream step s _) = elem_loop s
+  where
+    elem_loop s = case step s of
+                    Yield y s' | x == y    -> True
+                               | otherwise -> elem_loop s'
+                    Skip    s'             -> elem_loop s'
+                    Done                   -> False
+
+infix 4 `notElem`
+-- | Inverse of `elem`
+notElem :: Eq a => a -> Stream a -> Bool
+{-# INLINE notElem #-}
+notElem x = not . elem x
+
+-- | Yield 'Just' the first element matching the predicate or 'Nothing' if no
+-- such element exists.
+find :: (a -> Bool) -> Stream a -> Maybe a
+{-# INLINE_STREAM find #-}
+find f (Stream step s _) = find_loop s
+  where
+    find_loop s = case step s of
+                    Yield x s' | f x       -> Just x
+                               | otherwise -> find_loop s'
+                    Skip    s'             -> find_loop s'
+                    Done                   -> Nothing
+
+-- | Yield 'Just' the index of the first element matching the predicate or
+-- 'Nothing' if no such element exists.
+findIndex :: (a -> Bool) -> Stream a -> Maybe Int
+{-# INLINE_STREAM findIndex #-}
+findIndex f (Stream step s _) = findIndex_loop s 0
+  where
+    findIndex_loop s i = case step s of
+                           Yield x s' | f x       -> Just i
+                                      | otherwise -> findIndex_loop s' (i+1)
+                           Skip    s'             -> findIndex_loop s' i
+                           Done                   -> Nothing
+
 -- Folding
 -- -------
 
 -- Folding
 -- -------