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 case-insensitive search we can define the following function.

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

Then we can use it as follows.

*Main> fmap caseless (Alt (Seq (Ch "ab") (Ch ";")) (Ch "XYZ"))
Alt (Seq (Ch "aAbB") (Ch ";")) (Ch "XxYyZz")