A new breed of patterns
I like to code up little snippets in Haskell to play around with interesting concepts. Sometimes I invent notation that must appear forcing to most, but let's introduce it anyway...
How I use ViewPatterns, for fun and profit
When writing evaluators, I like to use view patterns to evaluate subtrees already on the LHS (pattern side). Let's introduce a mini-language (also called Hutton's razor) that can only add:
data AST = Lit Integer | Plus AST AST deriving Show
The evaluator is maximally simple, as it only needs to care about two sole cases:
eval :: AST -> Integer
eval (Lit res) = res
eval (Plus l r) = eval l + eval r
There is a train of thought that cares about termination and logical consistency and thus requires that in the definition of eval (Plus l r) the function to be defined can only be applied to structurally strictly smaller arguments (these are the hypotheses). We adhere to this rule above, but for more complicated functions it is possible to introduce bugs when not being super careful.
So why not resort to view patterns, and ban the eval from the RHS altogether?
eval (Plus (eval -> l) (eval -> r)) = l + r
This way of putting it makes it totally clear that eval is always applied to parts of the syntax tree.
Result patterns?
But let's return to the base case (Lit). We are forced to come up with a new binding (res), just to have something in our hands that we can return? Sounds like redundancy. So for the purpose of this post I'll come up with a result pattern (=), which can appear on the LHS only once and it's presence there will rule out the RHS:
eval (Lit =)
No more arbitrary names!
View lambdas, anyone?
Okay, so let's turn up the heat a bit more. A continuation-passing interpreter is a tail recursive way to evaluate the AST:
cps :: forall k. AST -> (Integer -> k) -> k
cps (Lit n) k = k n
cps (Plus l r) k = cps l (\l -> cps r (\r -> k $ l + r))
For the purpose of this exercise you can consider the type k to be unit (), and the continuation (value k) a consumer of intermediate results. We recognise the same usage pattern as in eval: subtrees are immediately (and linearly) passed to the function to be defined. So let's rewrite it with view patterns:
cps (Plus (cps -> l) (cps -> r)) k = l (\l -> r (\r -> k $ l + r))
But now we face the same redundancy issue, that the view patterns bind identifiers that are somehow repetitive, as they are applied to lambdas immediately. Can we come up with a notation for a view pattern that applies on a lambda and extends its scope to the rest of the patterns and to the RHS? Consider
cps (Plus (cps -> \l) (cps -> \r)) k = k (l + r)
It takes some time to see the charm here, as it is wormholing a lambda-bound identifier to the RHS, but it is unbeatably concise. And we can combine it with the result pattern idea too:
cps (Plus (cps -> \l) (cps -> \r)) (($ l + r) -> =)
At this point however the readability is suffering.
Outro
Note that the view lambdas are strange beasts, not only because they wrap the result (RHS or = pattern), but also the identity holds: \p ≡ (id -> \p), but since all the ids don't change anything, they can be stripped anyway. I wonder where I shall encounter more such view lambdas in the wild...
