packages feed

regex-applicative 0.1.4 → 0.1.5

raw patch · 10 files changed

+378/−264 lines, 10 filesdep −vectordep ~base

Dependencies removed: vector

Dependency ranges changed: base

Files

CHANGES.md view
@@ -1,6 +1,12 @@ Changes ======= +0.1.5+-----+* Expose Object interface+* Allow matching prefixes rather than the whole string+* Add non-greedy repetitions+ 0.1.4 ----- * Completely rewrite the engine. Now it's faster and runs in constant space.
Text/Regex/Applicative.hs view
@@ -18,9 +18,16 @@     , anySym     , string     , reFoldl+    , Greediness(..)+    , few+    , match     , (=~)+    , findFirstPrefix+    , findLongestPrefix+    , findShortestPrefix     , module Control.Applicative     )     where+import Text.Regex.Applicative.Types import Text.Regex.Applicative.Interface import Control.Applicative
Text/Regex/Applicative/Compile.hs view
@@ -4,7 +4,7 @@  import Text.Regex.Applicative.Types -compile :: forall a s r . Regexp s ThreadId a -> (a -> [Thread s r]) -> [Thread s r]+compile :: forall a s r . RE s a -> (a -> [Thread s r]) -> [Thread s r] compile e k = compile2 e k k  -- The whole point of this module is this function, compile2, which needs to be@@ -18,7 +18,7 @@ -- -- compile2 function takes two continuations: one when the match is empty and -- one when the match is non-empty. See the "Rep" case for the reason.-compile2 :: forall a s r . Regexp s ThreadId a -> (a -> [Thread s r]) -> (a -> [Thread s r]) -> [Thread s r]+compile2 :: forall a s r . RE s a -> (a -> [Thread s r]) -> (a -> [Thread s r]) -> [Thread s r] compile2 e =     case e of         Eps -> \ke _kn -> ke $ error "empty"@@ -36,9 +36,15 @@             \ke kn -> a1 ke kn ++ a2 ke kn         Fmap f (compile2 -> a) -> \ke kn -> a (ke . f) (kn . f)         -- This is actually the point where we use the difference between-        -- continuations. For the inner regexp the empty continuation is a+        -- continuations. For the inner RE the empty continuation is a         -- "failing" one in order to avoid non-termination.-        Rep f b (compile2 -> a) ->-            let threads b ke kn =-                    a (\_ -> []) (\v -> let b' = f b v in threads b' kn kn) ++ ke b+        Rep g f b (compile2 -> a) ->+            let combine continue stop =+                    case g of+                        Greedy -> continue ++ stop+                        NonGreedy -> stop ++ continue+                threads b ke kn =+                    combine+                        (a (\_ -> []) (\v -> let b' = f b v in threads b' kn kn))+                        (ke b)             in threads b
− Text/Regex/Applicative/Implementation.hs 
@@ -1,72 +0,0 @@-{-# LANGUAGE GADTs, TypeFamilies, ViewPatterns, PatternGuards #-}-module Text.Regex.Applicative.Implementation (match, Regexp(..)) where-import Prelude-import Control.Applicative hiding (empty)-import Control.Monad.State hiding (foldM)-import Text.Regex.Applicative.StateQueue-import Control.Monad.ST-import Text.Regex.Applicative.Types-import Text.Regex.Applicative.Compile--fresh :: (MonadState m, StateType m ~ ThreadId) => m ThreadId-fresh = do-    i <- get-    put $! i+1-    return i--renumber :: Regexp s i a -> (Regexp s ThreadId a, ThreadId)-renumber e = flip runState 1 $ compile e-  where-    compile :: Regexp s i a -> State ThreadId (Regexp s ThreadId a)-    compile e =-        case e of-            Eps -> return Eps-            Symbol _ p -> Symbol <$> fresh <*> pure p-            Alt a1 a2 -> Alt <$> compile a1 <*> compile a2-            App a1 a2 -> App <$> compile a1 <*> compile a2-            Fmap f a -> Fmap f <$> compile a-            Rep f b a -> Rep f b <$> compile a---threadId :: Thread s a -> ThreadId-threadId Accept {} = 0-threadId Thread { threadId_ = i } = i---run :: StateQueue st (Thread s r)-    -> StateQueue st (Thread s r)-    -> [s] -> ST st (Maybe r)-run queue _ [] = fold f Nothing queue-    where f a@Just{} _ _ = return a-          f Nothing  _ x | Accept r <- x = return $ Just r-                         | otherwise = return Nothing-run queue newQueue (s:ss) = do-    let accum q _ t =-            case t of-                Accept {} -> return q-                Thread _ c ->-                    foldM (\q x -> tryInsert x q) q $ c s-    newQueue <- fold accum newQueue queue-    let veryNewQueue = clear queue-    run newQueue veryNewQueue ss--tryInsert :: Thread s r -> StateQueue st (Thread s r) -> ST st (StateQueue st (Thread s r))-tryInsert t@(threadId -> ThreadId i) queue = do-    alreadyPresent <- member i queue-    if alreadyPresent-        then return queue-        else insert i t queue--match :: Regexp s a r -> [s] -> Maybe r-match r s = runST $ do-    let (rr, ThreadId numStates) = renumber r-    q1 <- empty numStates-    q2 <- empty numStates-    let threads = compile rr (\x -> [Accept x])-    q1 <- foldM (\q t -> tryInsert t q) q1 threads-    run q1 q2 s---- This turns out to be much faster than the standard foldM,--- because of inlining.-foldM :: Monad m => (a -> b -> m a) -> a -> [b] -> m a-foldM f a l = foldr (\x k a -> f a x >>= k) return l $ a
Text/Regex/Applicative/Interface.hs view
@@ -1,67 +1,44 @@-{-# LANGUAGE Rank2Types, FlexibleInstances, TypeFamilies #-}+{-# LANGUAGE Rank2Types, FlexibleInstances, TypeFamilies, TupleSections #-}+{-# OPTIONS_GHC -fno-warn-orphans #-} module Text.Regex.Applicative.Interface where import Control.Applicative hiding (empty) import qualified Control.Applicative import Data.Traversable import Data.String-import Text.Regex.Applicative.Implementation---- | Type of regular expressions that recognize symbols of type @s@ and--- produce a result of type @a@.------ Regular expressions can be built using 'Functor', 'Applicative' and--- 'Alternative' instances in the following natural way:------ * @f@ '<$>' @ra@ matches iff @ra@ matches, and its return value is the result--- of applying @f@ to the return value of @ra@.------ * 'pure' @x@ matches the empty string (i.e. it does not consume any symbols),--- and its return value is @x@------ * @rf@ '<*>' @ra@ matches a string iff it is a concatenation of two--- strings: one matched by @rf@ and the other matched by @ra@. The return value--- is @f a@, where @f@ and @a@ are the return values of @rf@ and @ra@--- respectively.------ * @ra@ '<|>' @rb@ matches a string which is accepted by either @ra@ or @rb@.--- It is left-biased, so if both can match, the result of @ra@ is used.------ * 'Control.Applicative.empty' is a regular expression which does not match any string.------ * 'many' @ra@ matches concatenation of zero or more strings matched by @ra@--- and returns the list of @ra@'s return values on those strings.-newtype RE s a = RE (forall i . Regexp s i a)+import Data.Maybe+import Text.Regex.Applicative.Types+import Text.Regex.Applicative.Object  instance Functor (RE s) where-    fmap f (RE x) = RE $ Fmap f x+    fmap f x = Fmap f x  instance Applicative (RE s) where-    pure x = const x <$> RE Eps-    (RE a1) <*> (RE a2) = RE $ App a1 a2+    pure x = const x <$> Eps+    a1 <*> a2 = App a1 a2  instance Alternative (RE s) where-    (RE a1) <|> (RE a2) = RE $ Alt a1 a2-    empty = RE Eps-    many (RE a) = reverse <$> RE (Rep (flip (:)) [] a)+    a1 <|> a2 = Alt a1 a2+    empty = Eps+    many a = reverse <$> Rep Greedy (flip (:)) [] a  instance (char ~ Char, string ~ String) => IsString (RE char string) where     fromString = string --- | Matches and returns a single symbol which satisfies the predicate+-- | Match and return a single symbol which satisfies the predicate psym :: (s -> Bool) -> RE s s-psym p = RE $ Symbol (error "Not numbered symbol") p+psym p = Symbol (error "Not numbered symbol") p --- | Matches and returns the given symbol+-- | Match and return the given symbol sym :: Eq s => s -> RE s s sym s = psym (s ==) --- | Matches and returns any single symbol+-- | Match and return any single symbol anySym :: RE s s anySym = psym (const True) --- | Matches and returns the given sequence of symbols.+-- | Match and return the given sequence of symbols. ----- Note that you there is an 'IsString' instance for regular expression, so+-- Note that there is an 'IsString' instance for regular expression, so -- if you enable the @OverloadedStrings@ language extension, you can write -- @string \"foo\"@ simply as @\"foo\"@. --@@ -76,12 +53,122 @@ string :: Eq a => [a] -> RE a [a] string = traverse sym --- | Greedily matches zero or more symbols, which are combined using the given--- folding function-reFoldl :: (b -> a -> b) -> b -> RE s a -> RE s b-reFoldl f b (RE a) = RE $ Rep f b a+-- | Match zero or more instances of the given expression, which are combined using+-- the given folding function.+--+-- 'Greediness' argument controls whether this regular expression should match+-- as many as possible ('Greedy') or as few as possible ('NonGreedy') instances+-- of the underlying expression.+reFoldl :: Greediness -> (b -> a -> b) -> b -> RE s a -> RE s b+reFoldl g f b a = Rep g f b a --- | Attempts to match a string of symbols against the regular expression+-- | Match zero or more instances of the given expression, but as+-- few of them as possible (i.e. /non-greedily/). A greedy equivalent of 'few'+-- is 'many'.+--+-- Examples:+--+-- >Text.Regex.Applicative> findFirstPrefix (few anySym  <* "b") "ababab"+-- >Just ("a","abab")+-- >Text.Regex.Applicative> findFirstPrefix (many anySym  <* "b") "ababab"+-- >Just ("ababa","")+few :: RE s a -> RE s [a]+few a = reverse <$> Rep NonGreedy (flip (:)) [] a++-- | @s =~ a = match a s@ (=~) :: [s] -> RE s a -> Maybe a-s =~ (RE a) = match a s+s =~ a = match a s infix 2 =~++-- | Attempt to match a string of symbols against the regular expression.+-- Note that the whole string (not just some part of it) should be matched.+--+-- Examples:+--+-- >Text.Regex.Applicative> match (sym 'a' <|> sym 'b') "a"+-- >Just 'a'+-- >Text.Regex.Applicative> match (sym 'a' <|> sym 'b') "ab"+-- >Nothing+--+match :: RE s a -> [s] -> Maybe a+match re str =+    listToMaybe $+    results $+    foldl (flip step) (compile re) str++-- | Find a string prefix which is matched by the regular expression.+--+-- Of all matching prefixes, pick one using left bias (prefer the left part of+-- '<|>' to the right part) and greediness.+--+-- This is the match which a backtracking engine (such as Perl's one) would find+-- first.+--+-- If match is found, the rest of the input is also returned.+--+-- Examples:+--+-- >Text.Regex.Applicative> findFirstPrefix ("a" <|> "ab") "abc"+-- >Just ("a","bc")+-- >Text.Regex.Applicative> findFirstPrefix ("ab" <|> "a") "abc"+-- >Just ("ab","c")+-- >Text.Regex.Applicative> findFirstPrefix "bc" "abc"+-- >Nothing+findFirstPrefix :: RE s a -> [s] -> Maybe (a, [s])+findFirstPrefix re str = go (compile re) str Nothing+    where+    walk obj [] = (obj, Nothing)+    walk obj (t:ts) =+        case getResult t of+            Just r -> (obj, Just r)+            Nothing -> walk (addThread t obj) ts++    go obj str resOld =+        case walk emptyObject $ threads obj of+            (obj', resThis) ->+                let res = ((,str) <$> resThis) <|> resOld+                in+                    case str of+                        [] -> res+                        _ | failed obj' -> res+                        (s:ss) -> go (step s obj') ss res++-- | Find the longest string prefix which is matched by the regular expression.+--+-- Submatches are still determined using left bias and greediness, so this is+-- different from POSIX semantics.+--+-- If match is found, the rest of the input is also returned.+--+-- Examples:+--+-- >Text.Regex.Applicative Data.Char> let keyword = "if"+-- >Text.Regex.Applicative Data.Char> let identifier = many $ psym isAlpha+-- >Text.Regex.Applicative Data.Char> let lexeme = (Left <$> keyword) <|> (Right <$> identifier)+-- >Text.Regex.Applicative Data.Char> findLongestPrefix lexeme "if foo"+-- >Just (Left "if"," foo")+-- >Text.Regex.Applicative Data.Char> findLongestPrefix lexeme "iffoo"+-- >Just (Right "iffoo","")+findLongestPrefix :: RE s a -> [s] -> Maybe (a, [s])+findLongestPrefix re str = go (compile re) str Nothing+    where+    go obj str resOld =+        let res = (fmap (,str) $ listToMaybe $ results obj) <|> resOld+        in+            case str of+                [] -> res+                _ | failed obj -> res+                (s:ss) -> go (step s obj) ss res++-- | Find the shortest prefix (analogous to 'findLongestPrefix')+findShortestPrefix :: RE s a -> [s] -> Maybe (a, [s])+findShortestPrefix re str = go (compile re) str+    where+    go obj str =+        case results obj of+            r : _ -> Just (r, str)+            [] ->+                case str of+                    [] -> Nothing+                    _ | failed obj -> Nothing+                    s:ss -> go (step s obj) ss
+ Text/Regex/Applicative/Object.hs view
@@ -0,0 +1,134 @@+--------------------------------------------------------------------+-- |+-- Module    : Text.Regex.Applicative.Object+-- Copyright : (c) Roman Cheplyaka+-- License   : MIT+--+-- Maintainer: Roman Cheplyaka <roma@ro-che.info>+-- Stability : experimental+--+-- This is a low-level interface to the regex engine.+--------------------------------------------------------------------+{-# LANGUAGE TypeFamilies, GADTs #-}+module Text.Regex.Applicative.Object+    ( ReObject+    , compile+    , emptyObject+    , Thread+    , threads+    , failed+    , isResult+    , getResult+    , results+    , ThreadId+    , threadId+    , step+    , stepThread+    , fromThreads+    , addThread+    ) where++import Text.Regex.Applicative.Types+import qualified Text.Regex.Applicative.StateQueue as SQ+import qualified Text.Regex.Applicative.Compile as Compile+import Data.Maybe+import Control.Monad.State+import Control.Applicative hiding (empty)++-- | The state of the engine is represented as a \"regex object\" of type+-- @'ReObject' s r@, where @s@ is the type of symbols and @r@ is the+-- result type (as in the 'RE' type). Think of 'ReObject' as a collection of+-- 'Thread's ordered by priority. E.g. threads generated by the left part of+-- '<|>' come before the threads generated by the right part.+newtype ReObject s r = ReObject (SQ.StateQueue (Thread s r))++-- | List of all threads of an object. Each non-result thread has a unique id.+threads :: ReObject s r -> [Thread s r]+threads (ReObject sq) = SQ.getElements sq++-- | Create an object from a list of threads. It is recommended that all+-- threads come from the same 'ReObject', unless you know what you're doing.+-- However, it should be safe to filter out or rearrange threads.+fromThreads :: [Thread s r] -> ReObject s r+fromThreads ts = foldl (flip addThread) emptyObject ts++-- | Check whether a thread is a result thread+isResult :: Thread s r -> Bool+isResult Accept {} = True+isResult _ = False++-- | Return the result of a result thread, or 'Nothing' if it's not a result+-- thread+getResult :: Thread s r -> Maybe r+getResult (Accept r) = Just r+getResult _ = Nothing++-- | Check if the object has no threads. In that case it never will+-- produce any new threads as a result of 'step'.+failed :: ReObject s r -> Bool+failed obj = null $ threads obj++-- | Empty object (with no threads)+emptyObject :: ReObject s r+emptyObject = ReObject $ SQ.empty++-- | Extract the result values from all the result threads of an object+results :: ReObject s r -> [r]+results obj =+    mapMaybe getResult $ threads obj++-- | Feed a symbol into a regex object+step :: s -> ReObject s r -> ReObject s r+step s (ReObject sq) =+    let accum q t =+            case t of+                Accept {} -> q+                Thread _ c ->+                    foldl (\q x -> addThread x q) q $ c s+        newQueue = SQ.fold accum emptyObject sq+    in newQueue++-- | Feed a symbol into a non-result thread. It is an error to call 'stepThread'+-- on a result thread.+stepThread :: s -> Thread s r -> [Thread s r]+stepThread s t =+    case t of+        Thread _ c -> c s+        Accept {} -> error "stepThread on a result"++-- | Add a thread to an object. The new thread will have lower priority than the+-- threads which are already in the object.+--+-- If a (non-result) thread with the same id already exists in the object, the+-- object is not changed.+addThread :: Thread s r -> ReObject s r -> ReObject s r+addThread t (ReObject q) =+    case t of+        Accept {} -> ReObject $ SQ.insert t q+        Thread { threadId_ = ThreadId i } -> ReObject $ SQ.insertUnique i t q++-- | Compile a regular expression into a regular expression object+compile :: RE s r -> ReObject s r+compile =+    fromThreads .+    flip Compile.compile (\x -> [Accept x]) .+    renumber++renumber :: RE s a -> RE s a+renumber e = flip evalState 1 $ go e+  where+    go :: RE s a -> State ThreadId (RE s a)+    go e =+        case e of+            Eps -> return Eps+            Symbol _ p -> Symbol <$> fresh <*> pure p+            Alt a1 a2 -> Alt <$> go a1 <*> go a2+            App a1 a2 -> App <$> go a1 <*> go a2+            Fmap f a -> Fmap f <$> go a+            Rep g f b a -> Rep g f b <$> go a++fresh :: (MonadState m, StateType m ~ ThreadId) => m ThreadId+fresh = do+    i <- get+    put $! i+1+    return i
− Text/Regex/Applicative/Reference.hs 
@@ -1,73 +0,0 @@------------------------------------------------------------------------ |--- Module    : Text.Regex.Applicative.Reference--- Copyright : (c) Roman Cheplyaka--- License   : MIT------ Maintainer: Roman Cheplyaka <roma@ro-che.info>--- Stability : experimental------ Reference implementation (using backtracking)-----------------------------------------------------------------------{-# LANGUAGE GADTs #-}-module Text.Regex.Applicative.Reference (reference) where-import Prelude hiding (getChar)-import Text.Regex.Applicative.Implementation-import Text.Regex.Applicative.Interface-import Control.Applicative-import Control.Monad----- A simple parsing monad-newtype P s a = P { unP :: [s] -> [(a, [s])] }--instance Monad (P s) where-    return x = P $ \s -> [(x, s)]-    (P a) >>= k = P $ \s ->-        a s >>= \(x,s) -> unP (k x) s--instance Functor (P s) where-    fmap = liftM--instance Applicative (P s) where-    (<*>) = ap-    pure = return--instance Alternative (P s) where-    empty = P $ const []-    P a1 <|> P a2 = P $ \s ->-        a1 s ++ a2 s--getChar :: P s s-getChar = P $ \s ->-    case s of-        [] -> []-        c:cs -> [(c,cs)]--re2monad :: Regexp s r a -> P s a-re2monad r =-    case r of-        Eps -> return $ error "eps"-        Symbol _ p -> do-            c <- getChar-            if p c then return c else empty-        Alt a1 a2 -> re2monad a1 <|> re2monad a2-        App a1 a2 -> re2monad a1 <*> re2monad a2-        Fmap f a -> fmap f $ re2monad a-        Rep f b a -> rep b-            where-            am = re2monad a-            rep b = (do a <- am; rep $ f b a) <|> return b--runP :: P s a -> [s] -> Maybe a-runP m s = case filter (null . snd) $ unP m s of-    (r, _) : _ -> Just r-    _ -> Nothing---- | 'reference' @r@ @s@ should give the same results as @s@ '=~' @r@.------ However, this is not very efficient implementation and is supposed to be--- used for testing only.-reference :: RE s a -> [s] -> Maybe a-reference (RE r) s = runP (re2monad r) s
Text/Regex/Applicative/StateQueue.hs view
@@ -3,63 +3,49 @@     ( StateQueue     , empty     , insert-    , member+    , insertUnique     , fold-    , clear+    , getElements     ) where  import Prelude hiding (read, lookup, replicate)-import Data.Vector.Mutable hiding (clear)-import Control.Monad-import Control.Monad.ST+import qualified Data.IntSet as IntSet -data IndexedValue a = IndexedValue-    { ixKey :: !Int-    , _ixValue :: !a+data StateQueue a = StateQueue+    { elements :: [a]+    , ids :: IntSet.IntSet     } -data StateQueue s a = StateQueue-    { dense :: !(MVector s (IndexedValue a))-    , sparseToDense :: !(MVector s Int)-    , size :: !Int-    }+getElements :: StateQueue a -> [a]+getElements = reverse . elements  {-# INLINE empty #-}-empty :: Int -> ST st (StateQueue st a)-empty maxSize = do-    d <- replicate maxSize (IndexedValue 0 $ error "SQ: Uninitialized value")-    s2d <- replicate maxSize 0-    return StateQueue-        { dense = d-        , sparseToDense = s2d-        , size = 0-        }+empty :: StateQueue a+empty = StateQueue+    { elements = []+    , ids = IntSet.empty+    }  {-# INLINE insert #-}-insert-    :: Int -> a -> StateQueue st a-    -> ST st (StateQueue st a)-insert i v sq@StateQueue { size = size } = do-    write (sparseToDense sq) i size-    write (dense sq) size (IndexedValue i v)-    return $ sq { size = size + 1 }+insertUnique+    :: Int+    -> a+    -> StateQueue a+    -> StateQueue a+insertUnique i v sq@StateQueue {..} =+    if i `IntSet.member` ids+        then sq+        else sq { elements = v : elements+                , ids = IntSet.insert i ids+                } -{-# INLINE member #-}-member-    :: Int -> StateQueue st a -> ST st Bool-member i StateQueue {..} = {-# SCC "member" #-} do-    di <- read sparseToDense i-    if (di >= size) then return False else do-    IndexedValue { ixKey = dvKey } <- read dense di-    return $ dvKey == i+insert+    :: a+    -> StateQueue a+    -> StateQueue a+insert v sq =+    sq { elements = v : elements sq }  {-# INLINE fold #-}-fold :: (a -> Int -> x -> ST st a) -> a -> StateQueue st x -> ST st a-fold f acc0 sq = foldM step acc0 [0 .. size sq - 1]-  where-    step acc n = do-        IndexedValue i v <- read (dense sq) n-        f acc i v--{-# INLINE clear #-}-clear sq = sq { size = 0 }+fold :: (a -> x -> a) -> a -> StateQueue x -> a+fold f acc0 sq = foldl f acc0 (reverse $ elements sq)
Text/Regex/Applicative/Types.hs view
@@ -3,24 +3,59 @@ module Text.Regex.Applicative.Types where  newtype ThreadId = ThreadId Int-    deriving (Show, Eq, Ord, Num)+    deriving (Show, Eq, Ord, Num, Real, Enum, Integral) -data Thread s a+-- | A thread either is a result or corresponds to a symbol in the regular+-- expression, which is expected by that thread.+data Thread s r     = Thread         { threadId_ :: ThreadId-        , _threadCont :: s -> [Thread s a]+        , _threadCont :: s -> [Thread s r]         }-    | Accept a+    | Accept r -data Regexp s i a where-    Eps :: Regexp s i a-    Symbol :: i -> (s -> Bool) -> Regexp s i s-    Alt :: Regexp s i a -> Regexp s i a -> Regexp s i a-    App :: Regexp s i (a -> b) -> Regexp s i a -> Regexp s i b-    Fmap :: (a -> b) -> Regexp s i a -> Regexp s i b-    Rep :: (b -> a -> b) -- folding function (like in foldl)+-- | Returns thread identifier. This will be 'Just' for ordinary threads and+-- 'Nothing' for results.+threadId :: Thread s r -> Maybe ThreadId+threadId Thread { threadId_ = i } = Just i+threadId _ = Nothing++data Greediness = Greedy | NonGreedy+    deriving (Show, Read, Eq, Ord, Enum)++-- | Type of regular expressions that recognize symbols of type @s@ and+-- produce a result of type @a@.+--+-- Regular expressions can be built using 'Functor', 'Applicative' and+-- 'Alternative' instances in the following natural way:+--+-- * @f@ '<$>' @ra@ matches iff @ra@ matches, and its return value is the result+-- of applying @f@ to the return value of @ra@.+--+-- * 'pure' @x@ matches the empty string (i.e. it does not consume any symbols),+-- and its return value is @x@+--+-- * @rf@ '<*>' @ra@ matches a string iff it is a concatenation of two+-- strings: one matched by @rf@ and the other matched by @ra@. The return value+-- is @f a@, where @f@ and @a@ are the return values of @rf@ and @ra@+-- respectively.+--+-- * @ra@ '<|>' @rb@ matches a string which is accepted by either @ra@ or @rb@.+-- It is left-biased, so if both can match, the result of @ra@ is used.+--+-- * 'Control.Applicative.empty' is a regular expression which does not match any string.+--+-- * 'many' @ra@ matches concatenation of zero or more strings matched by @ra@+-- and returns the list of @ra@'s return values on those strings.+data RE s a where+    Eps :: RE s a+    Symbol :: ThreadId -> (s -> Bool) -> RE s s+    Alt :: RE s a -> RE s a -> RE s a+    App :: RE s (a -> b) -> RE s a -> RE s b+    Fmap :: (a -> b) -> RE s a -> RE s b+    Rep :: Greediness    -- repetition may be greedy or not+        -> (b -> a -> b) -- folding function (like in foldl)         -> b             -- the value for zero matches, and also the initial value                          -- for the folding function-        -> Regexp s i a-        -> Regexp s i b-+        -> RE s a+        -> RE s b
regex-applicative.cabal view
@@ -9,7 +9,7 @@ -- standards guiding when and how versions should be incremented.  -- DO NOT FORGET TO UPDATE THE GIT TAG BELOW!!!-Version:             0.1.4+Version:             0.1.5  -- A short (one-line) description of the package. Synopsis:            Regex-based parsing with applicative interface@@ -56,23 +56,21 @@ Source-repository this   type:     git   location: git://github.com/feuerbach/regex-applicative.git-  tag:      v0.1.4+  tag:      v0.1.5  Library   -- Packages needed in order to build this package.-  Build-depends:       base >= 4.2 && < 4.4,+  Build-depends:       base >= 4.2 && < 4.5,                        containers >= 0.3 && < 0.5,-                       monads-tf == 0.1.*,-                       vector == 0.7.*+                       monads-tf == 0.1.*     -- Modules exported by the library.   Exposed-modules:     Text.Regex.Applicative-                       Text.Regex.Applicative.Reference+                       Text.Regex.Applicative.Object      -- Modules not exported by this package.   Other-modules:       Text.Regex.Applicative.Interface-                       Text.Regex.Applicative.Implementation                        Text.Regex.Applicative.Types                        Text.Regex.Applicative.Compile                        Text.Regex.Applicative.StateQueue