Regular expression

Constructors are exposed, but you should use smart constructors in this module to construct RE.

The Eq and Ord instances are structural. The Kleene etc constructors do "weak normalisation", so for values constructed using those operations Eq witnesses "weak equivalence". See equivalent for regular-expression equivalence.

Structure is exposed in Kleene.RE module but consider constructors as half-internal. There are soft-invariants, but violating them shouldn't break anything in the package. (e.g. transitionMap will eventually terminate, but may create more redundant states if starting regexp is not "weakly normalised").

Empty regex. Doesn't accept anything.

>>> putPretty (empty :: RE Char)
^[]$

>>> putPretty (bottom :: RE Char)
^[]$

match (empty :: RE Char) (s :: String) === False

Empty string. Note: different than empty.

>>> putPretty eps
^$

>>> putPretty (mempty :: RE Char)
^$

match (eps :: RE Char) s === null (s :: String)

>>> putPretty (char 'x')
^x$

>>> putPretty $ charRange 'a' 'z'
^[a-z]$

Any character. Note: different than dot!

>>> putPretty anyChar
^[^]$

Concatenate regular expressions.

(asREChar r <> s) <> t === r <> (s <> t)

asREChar r <> empty === empty

empty <> asREChar r === empty

asREChar r <> eps === r

eps <> asREChar r === r

Union of regular expressions.

asREChar r \/ r === r

asREChar r \/ s === s \/ r

(asREChar r \/ s) \/ t === r \/ (s \/ t)

empty \/ asREChar r === r

asREChar r \/ empty === r

everything \/ asREChar r === everything

asREChar r \/ everything === everything

Kleene star.

star (star r) === star (asREChar r)

star eps     === asREChar eps

star empty   === asREChar eps

star anyChar === asREChar everything

star (r      \/ eps) === star (asREChar r)

star (char c \/ eps) === star (asREChar (char c))

star (empty  \/ eps) === asREChar eps

Literal string.

>>> putPretty ("foobar" :: RE Char)
^foobar$

>>> putPretty ("(.)" :: RE Char)
^\(\.\)$

We say that a regular expression r is nullable if the language it defines contains the empty string.

>>> nullable eps
True

>>> nullable (star "x")
True

>>> nullable "foo"
False

Intuitively, the derivative of a language \(\mathcal{L} \subset \Sigma^\star\) with respect to a symbol \(a \in \Sigma\) is the language that includes only those suffixes of strings with a leading symbol \(a\) in \(\mathcal{L}\).

>>> putPretty $ derivate 'f' "foobar"
^oobar$

>>> putPretty $ derivate 'x' $ "xyz" \/ "abc"
^yz$

>>> putPretty $ derivate 'x' $ star "xyz"
^yz(xyz)*$

Transition map. Used to construct DFA.

>>> void $ Map.traverseWithKey (\k v -> putStrLn $ pretty k ++ " : " ++ SF.showSF (fmap pretty v)) $ transitionMap ("ab" :: RE Char)
^[]$ : \_ -> "^[]$"
^b$ : \x -> if
    | x <= 'a'  -> "^[]$"
    | x <= 'b'  -> "^$"
    | otherwise -> "^[]$"
^$ : \_ -> "^[]$"
^ab$ : \x -> if
    | x <= '`'  -> "^[]$"
    | x <= 'a'  -> "^b$"
    | otherwise -> "^[]$"

Leading character sets of regular expression.

>>> leadingChars "foo"
fromSeparators "ef"

>>> leadingChars (star "b" <> star "e")
fromSeparators "abde"

>>> leadingChars (charRange 'b' 'z')
fromSeparators "az"

Whether two regexps are equivalent.

equivalent re1 re2 = forall s. match re1 s === match re1 s

>>> let re1 = star "a" <> "a"
>>> let re2 = "a" <> star "a"

These are different regular expressions, even we perform some normalisation-on-construction:

>>> re1 == re2
False

They are however equivalent:

>>> equivalent re1 re2
True

The algorithm works by executing states on "product" regexp, and checking whether all resulting states are both accepting or rejecting.

re1 == re2 ==> equivalent re1 re2

More examples

>>> let example re1 re2 = putPretty re1 >> putPretty re2 >> return (equivalent re1 re2)
>>> example re1 re2
^a*a$
^aa*$
True

>>> example (star "aa") (star "aaa")
^(aa)*$
^(aaa)*$
False

>>> example (star "aa" <> star "aaa") (star "aaa" <> star "aa")
^(aa)*(aaa)*$
^(aaa)*(aa)*$
True

>>> example (star ("a" \/ "b")) (star $ star "a" <> star "b")
^[a-b]*$
^(a*b*)*$
True

Generate random strings of the language RE c describes.

>>> let example = traverse_ print . take 3 . generate (curry QC.choose) 42
>>> example "abc"
"abc"
"abc"
"abc"

>>> example $ star $ "a" \/ "b"
"aaaaba"
"bbba"
"abbbbaaaa"

>>> example empty

all (match r) $ take 10 $ generate (curry QC.choose) 42 (r :: RE Char)

Whether RE is (structurally) equal to empty.

isEmpty r === all (not . nullable) (Map.keys $ transitionMap $ asREChar r)

Not only we can decide whether RE is nullable, we can also remove the empty string:

>>> putPretty $ nullableProof eps
^[]$

>>> putPretty $ nullableProof $ star "x"
^xx*$

>>> putPretty $ nullableProof "foo"
Nothing

nullableProof is consistent with nullable:

isJust (nullableProof r) === nullable (asREChar r)

The returned regular expression is not nullable:

maybe True (not . nullable) $ nullableProof $ asREChar r

If we union with empty regex, we get a equivalent regular expression we started with:

maybe r (eps \/) (nullableProof r) `equivalent` (asREChar r)