I see people talking about Scrap Your Boilerplate and generic programming in Haskell. What do these terms mean? When would I want to use Scrap Your Boilerplate, and how do I use it?
Often when making transformations on complex data types, we only need to affect small pieces of the structure---in other words, we're targeting specific reducible expressions, redexes, alone.
The classic example is double-negation elimination over a 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 in describing this example, I'd prefer not to write out the entirety of the ... part. It is completely mechanical---nothing more than the engine for continuing the recursion throughout the entirety of the Exp.
This "engine" is the boilerplate we intend to scrap.
To achieve this, Scrap Your Boilerplate suggests a mechanism by which we can construct "generic traversals" over data types. These traversals operate exactly correctly without knowing anything at all about the specific data type in question. To do this, very roughly, we have a notion of generic annotated trees. These are larger than ADTs in such a way that all ADTs can be projected into the type of annotated trees:
section :: Generic a => a -> AnnotatedTree
and "valid" annotated trees can be projected back into some brand of ADT
retract :: Generic a => AnnotatedTree -> Maybe a
Notably, I'm introducing the Generic typeclass to indicate types which have section and retract defined.
Using this generic, annotated tree representation of all data types, we can define a traversal once and for all. In particular, we provide an interface (using section and retract strategically) so that end users are never exposed to the AnnotatedTree type. Instead, it looks a bit like:
everywhere' :: Generic a => (a -> a) -> (AnnotatedTree -> AnnotatedTree)
such that, combined with final and initial section and retracts 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 f a do? It tries to apply the function f "everywhere" in the ADT a. In other words, we now write our double negation simplification as follows
doubleNegSimpl :: Exp -> Exp
doubleNegSimpl (Negate (Negate e)) = e
doubleNegSimpl e = e
In other words, it acts as id whenever the redex (Negate (Negate _)) fails to match. If we apply everywhere to this
simplify :: Exp -> Exp
simplify = everywhere doubleNegSimpl
then double negations will be eliminated "everywhere" via a generic traversal. The ... boilerplate is gone.