[edwardkmett]

    import Control.Lens

and let us use two components from lens:

    rewriteOf :: Setter' a a -> (a -> Maybe a) -> a -> a

which can take a rewrite rule and apply it to any 'self-similar' setter recursively in a bottom up fashion until it ceases to apply and

    uniplate :: Data s => Traversal' a a

that says that if we have an instance for Haskell's built in generic programming framework 'Data', we can get a traversal of the immediate descendants.

Now

    rewriteOf uniplate $ \case 
      Neg (Lit a) -> Just $ Lit (-1)
      _ -> Nothing

will walk a syntax tree looking for negated literals starting recursively from the bottom of the tree, applying that rewrite rule on the right hand side until it no longer applies and fold it back up the tree. This works in a lazy setting where you can have potentially infinitely many targets and you didn't have to write any code to define the traversal.

The data type itself was just something like:

    data Term 
      = Var String 
      | Neg Term 
      | Lit Int 
      | App Term Term 
      | Abs String Term 
      deriving Data