Often when performing transformations on complex data types, we only need to work on small fragments of the structure - in other words, we aim at specific reducible expressions, alterations, on our own.
A classic example is the elimination of double negation by the type of integer expressions:
data Exp = Plus Exp Exp | Mult Exp Exp | Negate Exp | Pure Int doubleNegSimpl :: Exp -> Exp doubleNegSimpl (Negate (Negate e)) = e ...
Even when describing this example, I would prefer not to write down the entire part ... It is completely mechanical - nothing more than an engine for continuing recursion throughout Exp .
This “engine” is a template that we intend to recycle.
To achieve this, Scrap Your Boilerplate offers a mechanism by which we can build "common crawls" on data types. These workarounds work precisely, not knowing anything about the specific data type in question. For this it is very rude, we have the concept of common annotated trees. They are larger than ADTs, so that all ADTs can be projected into annotated tree types:
section :: Generic a => a -> AnnotatedTree
and "valid" annotated trees can be projected back into some ADT brand
retract :: Generic a => AnnotatedTree -> Maybe a
In particular, I am introducing the Generic class to indicate the types that are defined by section and retract .
Using this general, annotated tree view of all data types, we can determine the traversal once and for all. In particular, we provide an interface (using the section and retract ) so that end users are never exposed to the AnnotatedTree type. Instead, it looks something like this:
everywhere' :: Generic a => (a -> a) -> (AnnotatedTree -> AnnotatedTree)
that in combination with the final and initial section and retract and the invariant that our annotated trees are always "valid", we have
everywhere :: Generic a => (a -> a) -> (a -> a) everywhere f a0 = fromJust . retract . everywhere' f . section
What does everywhere fa do? He is trying to apply the function f "everywhere" in ADT a . In other words, we now write a simplification of double negation as follows:
doubleNegSimpl :: Exp -> Exp doubleNegSimpl (Negate (Negate e)) = e doubleNegSimpl e = e
In other words, it acts as id whenever redex (Negate (Negate _)) not suitable. If we apply everywhere to this
simplify :: Exp -> Exp simplify = everywhere doubleNegSimpl
then double negatives will be eliminated "everywhere" through a general detour. The pattern ... disappeared.