data RE a where
Phi :: RE a -- empty language
Empty :: RE a -- empty word
L :: a -> RE a -- single letter taken from alphabet a
Choice :: RE a -> RE a -> RE a -- r1 + r2
Seq :: RE a -> RE a -> RE a -- (r1,r2)
Star :: RE a -> RE a -- r*
equality :: Eq a => RE a -> RE a -> Bool
intersect :: Eq a => RE a -> RE a -> RE a
contains :: Eq a => RE a -> RE a -> Bool
implemented via symbolic manipulation of regular expressions (no explicit finite automata construction) by adapting Antimirov's regular expression rewriting algorithm via partial derivatives.
The implementation is available via the Haskell platform hackage. Check out the regexpr-symbolic package.
The source code describes some of the technical details. You can also check out an earlier post which considers the specific case of intersection.