In order to use fmap with REs, we need to modify the structure of our algebraic data type to have a type parameter for the leaves of the RE type.

import Data.Char
import Data.Functor

data RE a = Epsilon | Ch a | Seq (RE a) (RE a) | Alt (RE a) (RE a) |
            Star (RE a) | Group (RE a) deriving Show

instance Functor RE where
    fmap f Epsilon = Epsilon
    fmap f (Ch x)  = Ch (f x)
    fmap f (Seq a b) = Seq (fmap f a) (fmap f b)
    fmap f (Alt a b) = Alt (fmap f a) (fmap f b)
    fmap f (Group a) = Group (fmap f a)

With this change we could use fmap to systematically transform the character classes of an RE.

For example, if we want to do capitalized search we can define the following function.

capitalize [] = []
capitalize (c:cs)
    | isLower c  = toUpper c : caseless cs
    | otherwise  = c : caseless cs

Then we can use it as follows.

*Main> fmap capitalize (Alt (Seq (Ch "ab") (Ch ";")) (Ch "Xyz"))
Alt (Seq (Ch "AB") (Ch ";")) (Ch "XYZ")