4 ms·
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
by edwardkmett 13y ago
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