data RE a            -- regular expressions over an alphabet defined by 'a'
= Empty          -- empty regular expression
| Sym a          -- match the given symbol
| RE a :+: RE a  -- concatenation of two regular expressions
| RE a :|: RE a  -- choice between two regular expressions
| Rep (RE a)     -- zero or more repetitions of a regular expression
| Rep1 (RE a)    -- one or more repetitions of a regular expression
deriving (Show)