This is a GHC proposal augmenting our existing rewrite rule mechanism with lightweight higher order matching using template patterns, which provides a way to match complex terms which contain locally bound variables.
For example, consider the rule:
"concatMap" forall next f. concatMap (\x -> Stream next (f x)) = concatMap' next f
f xpart (which we call template pattern) only matched applications literally, like:
concatMap (\x -> Stream next ((\y -> y * 2 + y) x)
This proposal allows it to match the beta-equivalent expression:
concatMap (\x -> Stream next (x * 2 + x))
Which results in:
concatMap' next (\x -> x * 2 + x)
Please leave a comment if you can think of other real world applications of template patterns.
I would also appreciate suggestions for a better name than “template patterns”.