Equality, containment and intersection among regular expressions via symbolic manipulation

Three standard regular expression operations

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*
 deriving Eq

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.