weighted-regexp 0.1.1.0 → 0.2.0.0

raw patch · 12 files changed

+440/−79 lines, 12 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGES.markdown +85/−0
• README.markdown +256/−0
• src/Data/Semiring.hs +5/−24
• src/Text/RegExp.hs +4/−4
• src/Text/RegExp/Data.hs +8/−5
• src/Text/RegExp/Matching.hs +39/−12
• src/Text/RegExp/Matching/LeftLong.hs +1/−1
• src/Text/RegExp/Matching/Leftmost.hs +1/−1
• src/Text/RegExp/Matching/Longest.hs +2/−2
• src/criterion.lhs +2/−2
• src/quickcheck.lhs +34/−27
• weighted-regexp.cabal +3/−1

@@ -0,0 +1,85 @@+% Changelog for `weighted-regexp`++# 0.2.0.0++## More general types for matching functions++The functions `fullMatch` and `partialMatch` now both have the type++    Weight a b w => RegExp a -> [b] -> w++whereas previously the signatures have been:++    fullMatch    :: Semiring w         => RegExp c -> [c] -> w+    partialMatch :: Weight c (Int,c) w => RegExp c -> [c] -> w++The change allows users to provide custom symbol weights in full+matchings and to do partial matchings with arbitrary symbols weights+instead of having to use only characters and their positions.++This generalization leads to a slight performance penalty in small+examples but has a negligible effect when matching large inputs.++## Renamed `accept` to `acceptFull`, added `acceptPartial`++Based on the more general `partialMatch` function, the function+`acceptPartial` was added for the `Bool` semiring. The `accept`+function has been appropriately renamed.++## Strict numeric semiring++The lazy definition of arithmetic operations for the `Numeric`+semiring has been dropped in favour of the more efficient+standard implementation. As a consequence, `matchingCount` no+longer works with infinite regular expressions.++## SPECIALIZE pragmas prevent memory leak++The generalization of the matching functions leads to a memory+leak that can be avoided by specializing them for concrete+semirings. Corresponding pragmas have been added for `Bool` and+for `Numeric` types but not for the more complex semirings defined+in the extra matching modules. It is unclear what is the best way+to specialize them too because the pragma must be placed in the+module where the matching functions are defined but, there, not+all semirings are in scope.++## Fixed mistake in Criterion benchmarks++In the group of partial matchings, the benchmark for `Bool`+accidentally used full matching. It now uses partial matching which,+unsurprisingly, is slower.++# 0.1.1.0++## added `noMatch`++`Text.RegExp` now provides a combinator++    noMatch :: RegExp c++which is an identity of `alt`. With this combinator, regular+expressions form a semiring with++    zero  = noMatch+    one   = eps+    (.+.) = alt+    (.*.) = seq_++A corresponding `Semiring` instance is not defined due to the lack of+an appropriate `Eq` instance.++## added `perm`++`Text.RegExp` now provides a combinator++    perm :: [RegExp c] -> RegExp c++that matches the given regular expressions in sequence. Each+expression must be matched exactly once but in arbitrary order. For+example, the regular expression++    perm (map char "abc")++is equivalent to `abc|acb|bca|bac|cba|cab` and represented as+`a(bc|cb)|b(ca|ac)|c(ba|ab)`.

@@ -0,0 +1,256 @@+% Weighted RegExp Matching++Efficient regular expression matching can be beautifully+simple. Revisiting ideas from theoretical computer science, it can be+implemented with linear worst-case time and space bounds in the purely+functional programming language [Haskell].++[Haskell]: http://hackage.haskell.org/platform/+[semirings]: http://en.wikipedia.org/wiki/Semiring++# Background++Since Plato wrote about philosophy in the form of [dialogues], authors+have used this literary form to convey their ideas. The 15th+[International Conference on Functional Programming][ICFP] features an+article on Regular Expressions written as a play, [A Play on Regular+Expressions][paper], which is meant to be [elegant, instructive, and+fun][Pearl]. The play discusses an efficient, purely functional+algorithm for matching regular expressions. By generalizing from+Booleans to arbitrary [semirings], this algorithm implements various+matching policies for weighted regular expressions.++[dialogues]: http://en.wikipedia.org/wiki/Socratic_dialogue+[ICFP]: http://www.icfpconference.org/icfp2010/+[Pearl]: http://web.cecs.pdx.edu/~apt/icfp09_cfp.html#pearls+[paper]: regexp-play.pdf++# Installation++An implementation of the ideas discussed in the Play on Regular+Expressions is available as a Haskell library. It is implemented in+pure Haskell rather than as a binding to an external library so you do+not need to install an external regular expression library to use it.++<table><tr><td>++<a href="http://hackage.haskell.org/platform">+<img src="http://hackage.haskell.org/platform/icons/button-100.png" />+</a>++</td><td>++However, you need Haskell in order to use this library. By installing+the [Haskell Platform][Haskell] you get a Haskell compiler with an+interactive environment as well as the package manager `cabal-install`+and various pre-installed packages.++</td></tr><tr><td>++<img src="http://hackage.haskell.org/images/Cabal-light.png"+     alt="Cabal" width="195" height="71" />++</td><td>++You can install the `weighted-regexp` library by typing the following+into a terminal:++    bash# cabal update+    bash# cabal install weighted-regexp++</td></tr></table>++This will install the current version. Differences between versions+are listed in the [changelog].++[changelog]: http://sebfisch.github.com/haskell-regexp/CHANGES.html++# Correctness++The matching algorithm computes the same result as a simple inductive+specification (given in the [Play on Regular Expressions][paper]) but+is [more efficient](#performance) than a direct translation of this+specification into Haskell. Although the ideas behind the algorithm+are not new but based on proven results from theoretical computer+science, there is no correctness proof for the equivalence of the+Haskell implementation of the algorithm with its specification. The+equivalence is therefore confirmed by testing.++It is difficult (and tedious) to write tests manually that cover all+interesting apsects of regular expression matching. Therefore,+[QuickCheck] is used to generate tests automatically and [Haskell+Program Coverage (HPC)][HPC] is used to monitor test coverage.++[QuickCheck]: http://www.cse.chalmers.se/~rjmh/QuickCheck/+[HPC]: http://www.haskell.org/ghc/docs/latest/html/users_guide/hpc.html++You can install the `weighted-regexp` library along with a test+program as follows:++    bash# cabal install weighted-regexp -fQuickCheck++Using the `QuickCheck` flag results in an additional program that you+can use to test the implementation. The program tests ++  * the algebraic laws of semirings for all defined semirings, and++  * the equivalence of the matching algorithm with the specification+    both for full and partial matchings.++For testing the equivalence, QuickCheck generates random regular+expressions and compares the result of the matching algorithm with the+result of its specification on random words. Moreover, the program+tests++  * the parser that provides common syntactic sugar like bounded+    repetitions and character classes,++  * the use of the library to recognize non-regular languages using+    infinite regular expressions, and++  * a combinator for parsing permutation sequences, that is, sequences+    of regular expressions in arbitrary order.++For a more detailed description of the tested properties consider the+[source code][quickcheck.lhs] of the test program. In order to+generate an HPC report you need to download the sources of the+`weighted-regexp` package. But you may as well consult the+[pregenerated coverage report][coverage] instead of generating one+yourself.++[quickcheck.lhs]: http://github.com/sebfisch/haskell-regexp/blob/master/src/quickcheck.lhs+[coverage]: http://sebfisch.github.com/haskell-regexp/quickcheck/hpc_index.html++# Performance++The matching algorithm provided by this library is usually slower than+other libraries like [pcre] but has a better asymptotic+complexity. There are no corner cases for which matching takes forever+or eats all available memory. More specifically, the worst-case run+time for matching a word against a regular expression is linearly+bounded by the length of the word and the size of the regular+expression. It is in *O(nm)* if *n* is the length of the word and *m*+the size of the expression. The memory requirements are independent of+the length of the word and linear in the size of the regular+expression, that is, in *O(m)*. Therefore, this library provides+similar asymptotic complexity guarantees as Google's [re2].++[pcre]: http://www.pcre.org/+[re2]: http://code.google.com/p/re2/++Here are timings that have been obtained (on a MacBook) with the+current version of the library.++       input               regexp            run time     memory+------------------- --------------------- -------------- --------+ 100 MB of a's       `.*`                  8s (12 MB/s)    1 MB+ 5000 a's            `(a?){5000}a{5000}`   13s             5 MB+ ~2M a's and b's     `.*a.{20}a.*`         3.6s            1 MB++The first example measures the search speed for a simple regular+expression with a long string. There is room for improvement. No time+has been invested yet to improve the performance of the library with+regard to constant factors.++The second example demonstrates the good asymptotic complexity of the+algorithm. Unlike a backtracking implementation like [pcre] the+library finishes in reasonable time. However, the memory requirements+are higher than usual and on closer inspection one can see that almost+10 of 13 seconds are spent during garbage collection. This example+uses a large regular expression which leads to a lot of garbage in the+matching algorithm.++The third example pushes automata based approaches to the limit+because the deterministic finite automaton that corresponds to the+regular expression is exponentially large. The input has been chosen+to not match the expression but is otherwise random and probably+explores many different states of the automaton. The matching+algorithm produces states on the fly and discards them, hence, it is+fast in this example, in fact, faster than re2[^cpp]. ++[^cpp]: The following C++ program uses the [re2] library and needs+*4.5s* to match `.*a.{20}a.*` against a string of ~2M random a's ad+b's:++    <script src="http://gist.github.com/488543.js?file=re2.cpp"></script>++    Unlike the Haskell program, this program keeps the whole input,+    that is, the result of `getline`, in memory. Can [re2] match input+    on the fly?++The benchmarks above all use large input and two of them are+specifically designed as corner cases of typical matching+algorithms. The run time of matching more common regular expressions+against short input has been measured using [Criterion] in order to+get statistically robust results.++[Criterion]: http://www.serpentine.com/blog/2009/09/29/criterion-a-new-benchmarking-library-for-haskell/++You can install the `weighted-regexp` package with the `Criterion` flag to generate a program that executes the benchmarks described below:++    bash# cabal install weighted-regexp -fCriterion++You can call `criterion-re --help` to see how to use the generated+program. It tests three different examples:++  * a unique full match with a regular expression for phone numbers,++  * an ambiguous full match with a regular expression for sequences of+    HTML elements, and++  * a partial match with a regular expression for protein sequences in+    RNA.++For a more detailed explanation consider the [source+code][criterion.lhs] of the benchmark program.++[criterion.lhs]: http://github.com/sebfisch/haskell-regexp/blob/master/src/criterion.lhs++       matching  acceptance  #matchings  leftmost     longest  leftmost longest+--------------- ----------- ----------- ---------- ---------- -----------------+ unique full       [4.0 us]   [4.6 us]+ ambiguous full   [11.7 us]   [13.1 us]+ partial          [21.2 us]              [74.2 us]  [68.0 us]         [73.8 us]++Click on the numbers for a more detailed distribution of run times.++[4.0 us]:  http://sebfisch.github.com/haskell-regexp/criterion/full-accept-phone-densities-800x600.png+[4.6 us]: http://sebfisch.github.com/haskell-regexp/criterion/full-count-phone-densities-800x600.png+[11.7 us]: http://sebfisch.github.com/haskell-regexp/criterion/full-accept-html-densities-800x600.png+[13.1 us]: http://sebfisch.github.com/haskell-regexp/criterion/full-count-html-densities-800x600.png+[21.2 us]: http://sebfisch.github.com/haskell-regexp/criterion/partial-accept-rna-densities-800x600.png+[74.2 us]: http://sebfisch.github.com/haskell-regexp/criterion/partial-leftmost-rna-densities-800x600.png+[68.0 us]: http://sebfisch.github.com/haskell-regexp/criterion/partial-longest-rna-densities-800x600.png+[73.8 us]: http://sebfisch.github.com/haskell-regexp/criterion/partial-leftlong-rna-densities-800x600.png++# Collaboration++<table><tr><td>++<a href="http://github.com">+<img src="https://github.com/images/modules/header/logo.png" />+</a>++</td><td>++The source code of this library is on [github]. You can collaborate by+using it in your projects, report bugs and ask for new features in the+[issue tracker], or provide patches that implement pending issues.++</td></tr></table>++[github]: http://github.com/sebfisch/haskell-regexp+[issue tracker]: http://github.com/sebfisch/haskell-regexp/issues++The algorithm discussed in the [Play on Regular Expressions][paper]+has been implemented in different languages. In a series of two+[blog][blog] [posts][posts], Carl Friedrich Bolz describes a Python+implementation that uses a Just In Time (JIT) compiler to achieve+impressive performance. He compares his version with corresponding C+++and Java programs.++[blog]: http://morepypy.blogspot.com/2010/05/efficient-and-elegant-regular.html+[posts]: http://morepypy.blogspot.com/2010/06/jit-for-regular-expression-matching.html++For questions and feedback email [Sebastian+Fischer](mailto:mail@sebfisch.de).

@@ -1,3 +1,5 @@+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+ -- |  -- Module      : Data.Semiring -- Copyright   : Thomas Wilke, Frank Huch, Sebastian Fischer@@ -74,32 +76,11 @@ -- Every numeric type that satisfies the semiring laws (as all -- predefined numeric types do) is a semiring. -- -data Numeric a = Numeric { getNumeric :: a }- deriving Eq+newtype Numeric a = Numeric { getNumeric :: a }+ deriving (Eq,Num) -instance (Num a, Show a) => Show (Numeric a) where+instance Show a => Show (Numeric a) where   show = show . getNumeric--lift :: Num a => (a -> a) -> Numeric a -> Numeric a-lift f = Numeric . f . getNumeric--lift2 :: Num a => (a -> a -> a) -> Numeric a -> Numeric a -> Numeric a-lift2 f x y = Numeric (f (getNumeric x) (getNumeric y))--instance Num a => Num (Numeric a) where-  fromInteger = Numeric . fromInteger-  signum      = lift signum-  abs         = lift abs--  0 + x = x-  x + 0 = x-  x + y = lift2 (+) x y--  0 * _ = 0-  _ * 0 = 0-  1 * x = x-  x * 1 = x-  x * y = lift2 (*) x y  instance Num a => Semiring (Numeric a) where   zero = 0; one = 1; (.+.) = (+); (.*.) = (*)

@@ -43,7 +43,7 @@    -- * Matching -  (=~), accept, matchingCount, fullMatch, partialMatch+  (=~), acceptFull, acceptPartial, matchingCount, fullMatch, partialMatch    ) where @@ -106,7 +106,7 @@ -- has the same meaning as --  -- @--- abc|acb|bcc|bac|cba|cab+-- abc|acb|bca|bac|cba|cab -- @ --  -- and is represented as@@ -124,9 +124,9 @@   go (p:ps) qs = (p `seq_` perm (ps ++ qs)) `alt` go ps (p:qs)  -- | --- Alias for 'accept' specialized for Strings. Useful in combination+-- Alias for 'acceptFull' specialized for Strings. Useful in combination -- with the 'IsString' instance for 'RegExp' 'Char' --  (=~) :: RegExp Char -> String -> Bool-(=~) = accept+(=~) = acceptFull 

@@ -15,7 +15,7 @@ data RegW w c = RegW { active :: !Bool,                        empty  :: !w,                         final_ :: !w, -                       reg    :: Reg w c }+                       reg    :: !(Reg w c) }  final :: Semiring w => RegW w c -> w final r = if active r then final_ r else zero@@ -29,11 +29,14 @@ class Semiring w => Weight a b w where   symWeight :: (a -> w) -> b -> w -instance Weight c (Int,c) Bool where-  symWeight p = p . snd+defaultSymWeight :: (a -> w) -> a -> w+defaultSymWeight = id -instance Num a => Weight c (Int,c) (Numeric a) where-  symWeight p = p . snd+instance Weight c c Bool where+  symWeight = defaultSymWeight++instance Num a => Weight c c (Numeric a) where+  symWeight = defaultSymWeight  weighted :: Weight a b w => RegW w a -> RegW w b weighted (RegW a e f r) =

@@ -7,41 +7,68 @@  -- | -- Checks whether a regular expression matches the given word. For--- example, @accept (fromString \"b|abc\") \"b\"@ yields @True@+-- example, @acceptFull (fromString \"b|abc\") \"b\"@ yields @True@ -- because the first alternative of @b|abc@ matches the string -- @\"b\"@. -- -accept :: RegExp c -> [c] -> Bool-accept r = fullMatch r+acceptFull :: RegExp c -> [c] -> Bool+acceptFull r = fullMatch r  -- |+-- Checks whether a regular expression matches a subword of the given+-- word. For example, @acceptPartial (fromString \"b\") \"abc\"@+-- yields @True@ because @\"abc\"@ contains the substring @\"b\"@.+-- +acceptPartial :: RegExp c -> [c] -> Bool+acceptPartial r = partialMatch r++-- | -- Computes in how many ways a word can be matched against a regular -- expression. --  matchingCount :: Num a => RegExp c -> [c] -> a matchingCount r = getNumeric . fullMatch r +{-# SPECIALIZE matchingCount :: RegExp c -> [c] -> Int #-}+ -- | -- Matches a regular expression against a word computing a weight in -- an arbitrary semiring. -- -fullMatch :: Semiring w => RegExp c -> [c] -> w-fullMatch (RegExp r) = matchW r+-- The symbols can have associated weights associated by the+-- 'symWeight' function of the 'Weight' class. This function also+-- allows to adjust the type of the used alphabet such that, for+-- example, positional information can be taken into account by+-- 'zip'ping the word with positions.+-- +fullMatch :: Weight a b w => RegExp a -> [b] -> w+fullMatch (RegExp r) = matchW (weighted r) +{-# SPECIALIZE fullMatch :: RegExp c -> [c] -> Bool #-}+{-# SPECIALIZE fullMatch :: RegExp c -> [c] -> Numeric Int #-}+{-# SPECIALIZE fullMatch :: Num a => RegExp c -> [c] -> Numeric a #-}+ -- | -- Matches a regular expression against substrings of a word computing--- a weight in an arbitrary semiring. The 'symWeight' function of--- 'Weight's is used to report positional information about the--- matching part of the word to the semiring.+-- a weight in an arbitrary semiring. Similar to 'fullMatch' the+-- 'Weight' class is used to associate weights to the symbols of the+-- regular expression. -- -partialMatch :: Weight c (Int,c) w => RegExp c -> [c] -> w-partialMatch (RegExp r) =-  matchW (arb `seqW` weighted r `seqW` arb) . zip [(0::Int)..]- where arb = repW (symW "." (const one))+partialMatch :: Weight a b w => RegExp a -> [b] -> w+partialMatch (RegExp r) = matchW (arb `seqW` weighted r `seqW` arb)+ where RegExp arb = rep anySym +{-# SPECIALIZE partialMatch :: RegExp c -> [c] -> Bool #-}+{-# SPECIALIZE partialMatch :: RegExp c -> [c] -> Numeric Int #-}+{-# SPECIALIZE partialMatch :: Num a => RegExp c -> [c] -> Numeric a #-}+ matchW :: Semiring w => RegW w c -> [c] -> w matchW r []     = empty r matchW r (c:cs) = final (foldl (shiftW zero) (shiftW one r c) cs)++{-# SPECIALIZE matchW :: RegW Bool c -> [c] -> Bool #-}+{-# SPECIALIZE matchW :: RegW (Numeric Int) c -> [c] -> Numeric Int #-}+{-# SPECIALIZE matchW :: Num a => RegW (Numeric a) c -> [c] -> Numeric a #-}  shiftW :: Semiring w => w -> RegW w c -> c -> RegW w c shiftW w r c | active r || w /= zero = shift w (reg r) c

@@ -48,7 +48,7 @@ -- matching its position is zero. --  matching :: RegExp c -> [c] -> Maybe Matching-matching r = getLeftLong . partialMatch r+matching r = getLeftLong . partialMatch r . zip [(0::Int)..]  -- |  -- Semiring used for leftmost longest matching.

@@ -43,7 +43,7 @@ -- its position is zero. --  matching :: RegExp c -> [c] -> Maybe Matching-matching r = getLeftmost . partialMatch r+matching r = getLeftmost . partialMatch r . zip [(0::Int)..]  -- | Semiring used for leftmost matching. -- 

@@ -69,5 +69,5 @@   x          .*.  One        =  x   Longest a  .*.  Longest b  =  Longest (a+b) -instance Weight c (Int,c) Longest where-  symWeight p (_,c) = p c .*. Longest 1+instance Weight c c Longest where+  symWeight p c = p c .*. Longest 1

@@ -22,7 +22,7 @@ >         ] >       ] >     | (mode, call) <-->       [ ("accept", whnf . accept)+>       [ ("accept", whnf . acceptFull) >       , ("count" , whnf . (matchingCount :: RegExp Char -> String -> Int)) >       ] >     ]@@ -34,7 +34,7 @@ >         ] >       ] >     | (mode, call) <-->       [ ("accept"  , whnf . accept)+>       [ ("accept"  , whnf . acceptPartial) >       , ("leftmost", whnf . Leftmost.matching) >       , ("longest" , whnf . Longest.matching) >       , ("leftlong", whnf . LeftLong.matching)

@@ -47,17 +47,14 @@ >     runChecks "semiring laws (Longest)" (semiring'laws :: Checks Longest) >     runChecks "semiring laws (LeftLong)" semiring'laws'LeftLong >     runTests (pad "full match") options $->       checks (full'match'spec :: Checks Bool) ++->       checks (full'match'spec :: Checks (Numeric Int)) ++->       checks (full'match'spec :: Checks Leftmost) ++->       checks (full'match'spec :: Checks Longest) ++->       checks (full'match'spec :: Checks LeftLong)+>       checks (full'match'spec acceptFull id :: Checks Bool) +++>       checks (full'match'spec matchingCount getNumeric+>               :: Checks (Numeric Int)) >     runTests (pad "partial match") options $->       checks (partial'match'spec partialMatch id :: Checks Bool) ++->       checks (partial'match'spec partialMatch id :: Checks (Numeric Int)) ++->       checks (partial'match'spec Leftmost.matching getLeftmost) +++>       checks (partial'match'spec acceptPartial id :: Checks Bool) +++>       checks (indexed'match'spec Leftmost.matching getLeftmost) ++ >       checks (partial'match'spec Longest.matching getLongest) ++->       checks (partial'match'spec LeftLong.matching getLeftLong)+>       checks (indexed'match'spec LeftLong.matching getLeftLong) >     runTests (pad "parse printed regexp") options [run parse'printed] >     runChecks "lazy infinite regexps" infinite'regexp'checks >     runTests "permutation parsing" options [run perm'parser'check]@@ -171,15 +168,24 @@ check it, we compare it with a executable specification which is correct by definition: -> full'match'spec :: (Show s, Semiring s) => Checks s-> full'match'spec = match'spec fullMatchSpec fullMatch id+> full'match'spec :: (Show a, Weight Char Char s)+>                 => (RegExp Char -> String -> a)+>                 -> (s -> a)+>                 -> Checks s+> full'match'spec = match'spec fullMatchSpec >-> partial'match'spec :: (Show a, Weight Char (Int,Char) s)+> partial'match'spec :: (Show a, Weight Char Char s) >                    => (RegExp Char -> String -> a) >                    -> (s -> a) >                    -> Checks s > partial'match'spec = match'spec partialMatchSpec >+> indexed'match'spec :: (Show a, Weight Char (Int,Char) s)+>                    => (RegExp Char -> String -> a)+>                    -> (s -> a)+>                    -> Checks s+> indexed'match'spec = match'spec (\r -> partialMatchSpec r . zip [(0::Int)..])+> > match'spec :: (Show a, Semiring s) >            => (RegExp Char -> String -> s) >            -> (RegExp Char -> String -> a)@@ -188,13 +194,15 @@ > match'spec spec convmatch conv = >   Checks [run (check'match'spec spec convmatch conv)] >+ > check'match'spec :: (Show a, Semiring s) >                  => (RegExp Char -> String -> s) >                  -> (RegExp Char -> String -> a) >                  -> (s -> a)->                  -> RegExp Char -> String -> Property+>                  -> RegExp Char -> String -> Bool > check'match'spec spec convmatch conv r s =->   length s < 7 ==> show (convmatch r s) == show (conv (spec r s))+>   show (convmatch r s') == show (conv (spec r s'))+>  where s' = take 5 s  To make this work, we need an `Arbitrary` instance for regular expressions.@@ -205,11 +213,11 @@ > regexp :: Int -> Gen (RegExp Char) > regexp 0 = frequency [ (1, return eps) >                      , (4, char `fmap` simpleChar) ]-> regexp n = frequency [ (1, regexp 0)->                      , (3, alt  `fmap` subexp `ap` subexp)->                      , (6, seq_ `fmap` subexp `ap` subexp)->                      , (3, rep  `fmap` regexp (n-1))->                      , (7, fromString `fmap` parsedRegExp n) ]+> regexp n = frequency [ (3, regexp 0)+>                      , (1, alt  `fmap` subexp `ap` subexp)+>                      , (2, seq_ `fmap` subexp `ap` subexp)+>                      , (1, rep  `fmap` regexp (n-1))+>                      , (2, fromString `fmap` parsedRegExp n) ] >  where subexp = regexp (n `div` 2) > > simpleChar :: Gen Char@@ -251,8 +259,8 @@ the structure of a regular expression. It uses exhaustive search to find all possibilities to match a regexp against a word. -> fullMatchSpec :: Semiring s => RegExp c -> [c] -> s-> fullMatchSpec (RegExp r) = matchSpec (reg r)+> fullMatchSpec :: Weight a b s => RegExp a -> [b] -> s+> fullMatchSpec (RegExp r) = matchSpec (reg (weighted r)) > > matchSpec :: Semiring s => Reg s c -> [c] -> s > matchSpec Eps        u  =  if null u then one else zero@@ -278,10 +286,10 @@  We can perform a similar test for partial instead of full matches. -> partialMatchSpec :: Weight c (Int,c) s => RegExp c -> [c] -> s+> partialMatchSpec :: Weight a b s => RegExp a -> [b] -> s > partialMatchSpec (RegExp r) =->   matchSpec (reg (arb `seqW` weighted r `seqW` arb)) . zip [(0::Int)..]->  where arb = repW (symW "." (const one))+>   matchSpec (reg (arb `seqW` weighted r `seqW` arb))+>  where RegExp arb = rep anySym  As a check for the parser, we check whether the representation generated by the `Show` instance of regular expressions can be parsed@@ -314,8 +322,7 @@ characters, we use numbers instead of characters.  > context'sensitive :: [Int] -> Bool-> context'sensitive s =->   fromBool (isInAnBnCn s) == (matchingCount anbncn s :: Numeric Int)+> context'sensitive s = isInAnBnCn s == acceptFull anbncn s > > isInAnBnCn :: [Int] -> Bool > isInAnBnCn s = all (==1) xs && all (==2) ys && all (==3) zs@@ -333,7 +340,7 @@ expressions in sequence, each occurring once in any order.  > perm'parser'check :: String -> Bool-> perm'parser'check cs = all (accept (perm (map char s))) (permutations s)+> perm'parser'check cs = all (acceptFull (perm (map char s))) (permutations s) >  where s = take 5 cs  We restrict the test to at most 5! (that is five factorial)

@@ -1,5 +1,5 @@ Name:          weighted-regexp-Version:       0.1.1.0+Version:       0.2.0.0 Cabal-Version: >= 1.6 Synopsis:      Weighted Regular Expression Matcher Description:@@ -16,6 +16,8 @@ Homepage:      http://sebfisch.github.com/haskell-regexp Build-Type:    Simple Stability:     experimental++Extra-Source-Files:     README.markdown CHANGES.markdown  Library   Build-Tools:          happy >= 1.17