Regular expression which has no restrictions on the elements. Therefore we can have Monad instance, i.e. have a regexp where characters are regexps themselves.

Because there are no optimisations, it's better to work over small alphabets. On the other hand, we can work over infinite alphabets, if we only use small amount of symbols!

>>> putPretty $ string [True, False]
^10$

>>> let re  = string [True, False, True]
>>> let re' = re >>= \b -> if b then char () else star (char ())
>>> putPretty re'
^..*.$

Empty regex. Doesn't accept anything.

>>> putPretty (empty :: M Bool)
^[]$

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

Empty string. Note: different than empty.

>>> putPretty (eps :: M Bool)
^$

>>> putPretty (mempty :: M Bool)
^$

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

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

Note: we know little about c.

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

Any character. Note: different than dot!

>>> putPretty (anyChar :: M Bool)
^[01]$

Concatenate regular expressions.

Union of regular expressions.

Lattice laws don't hold structurally:

Kleene star.

Literal string.

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

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

>>> putPretty $ string [False, True]
^01$

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' $ unions ["xyz", "abc"]
^yz$

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

Generate random strings of the language M c describes.

>>> let example = traverse_ print . take 3 . generate 42
>>> example "abc"
"abc"
"abc"
"abc"

>>> example $ star $ unions ["a", "b"]
""
"aaababaaab"
"a"

xx >>> example empty

expensive-prop> all (match r) $ take 10 $ generate 42 (r :: M Bool)

Convert to Kleene

>>> let re = charRange 'a' 'z'
>>> putPretty re
^[abcdefghijklmnopqrstuvwxyz]$

>>> putPretty (toKleene re :: RE Char)
^[a-z]$

Whether M is (structurally) equal to empty.

Whether M is (structurally) equal to eps.