Scrapping the boilerplate of doing variable substitution in an expression

Question

Suppose we have the following data structure, whose values represent expressions on some language:

data BExpr = Stop
           | Guard Expr BExpr
           | Choice BExpr BExpr
           | Parallel BExpr BExpr
           | Disable BExpr BExpr
           -- ... and so on.
           | Act Expr


data Expr = Var String | Val Int

I would like to define a function substBExpr that substitutes variable names by their integer values in a BExpr. This can be done as follows:

subst :: Map String Int -> Expr -> Expr
subst substMap e@(Var name) = maybe e Val $ Map.lookup name substMap
subst _  v@(Val _)          = v

substBExpr :: Map String Int -> BExpr -> BExpr
substBExpr _ Stop                     =  Stop
substBExpr substMap (Guard gExp be)   = Guard gExp' be'
    where gExp' = subst substMap gExp
          be' = substBExpr substMap be
substBExpr substMap (Choice be0 be1)  = Choice be0' be1'
    where be0' = substBExpr substMap be0
          be1' = substBExpr substMap be1
substBExpr substMap (Parallel be0 be1) = Parallel be0' be1'
    where be0' = substBExpr substMap be0
          be1' = substBExpr substMap be1
substBExpr substMap (Disable be0 be1) = Disable be0' be1'
    where be0' = substBExpr substMap be0
          be1' = substBExpr substMap be1
substBExpr substMap (Act aExp)        = Act aExp'
    where aExp' = subst substMap aExp

The problem is that this requires a lot of boilerplate, which I would like to avoid.

I can think of two solutions right now. The first solution is adding a type parameter to BExpr so that I can derive automatically an instance of Functor for it:

data GBExpr e = GStop
              | GGuard e (GBExpr e)
              | GChoice (GBExpr e) (GBExpr e)
              | GParallel (GBExpr e) (GBExpr e)
              | GDisable (GBExpr e) (GBExpr e)
              -- ... and so on.
              | GAct e
              deriving (Show, Functor)

type BExpr2 = GBExpr Expr

substBExpr2 :: Map String Int -> BExpr2 -> BExpr2
substBExpr2 substMap = (subst substMap <$>)

While this works, it is not viable if Bexpr cannot be changed to incorporate a type parameter.

The second solution is using gfoldl:

substT :: (Typeable a) => Map String Int -> a -> a
substT substMap = mkT (subst substMap)

substExprs :: (Data a) => Map String Int -> a -> a
substExprs substMap a = runIdentity $ gfoldl step return (substT substMap a)
    where
      step :: Data d => Identity (d -> b) -> d -> Identity b
      step cdb d = cdb <*> pure (substExprs substMap d)

Which involves some boilerplate of its own (but I don't know of any function that traverses a structure, and applies a function to values inside the structure only if they can be casted to a particular type).

Is there a superior alternative to this "scrap-your-boilerplate" problem? (I could imagine it might be some solution that involves lenses, but I'm not that familiar with optics...).