Eliminating explicit parentheses with a handy combinator
This is a literate Haskell post about a trick I picked up in Raymond Smullyan’s “To Mock a Mockingbird”, a fantastic introduction to combinator logic.
Let’s start with a simple demonstration. Consider the expression for
u = (:) 'g' (show 13)
u evaluates to:
ghci> u "g13"
Using only function application and the non-infix compose function, I’d like to write a point-free function
solution such that the
u' defined below evaluates to the same value as
u' = solution (:) 'g' show 13
The body of
u' differs from
u in that
show 13 is no longer surrounded by parentheses and a function
solution is being applied to the cons function.
We solve for
u' by working backwards while thinking about the implicit parentheses we usually leave out when working with curried functions. We also use a synonym for
(.) so we’re not overwhelmed by parentheses.
b = (.)
B combinator in combinator logic is defined
B x y z = x (y z) and serves the same purpose as the compose operator in Haskell. The mechanical transformation we use in this post can eliminate parentheses not implied by left-associative function application by using the definition of
B to carry out the transformation
x (y z) => B x y z. By prefixing an expression with
B, we’re able to eliminate a pair of parentheses! We solve
u2 = ((:) 'g') (show 13) -- `u` with some clarifying parentheses u3 = ((b ((:) 'g')) show) 13 -- liberating `13` from parentheses -- not implied by left-assoc. u4 = ((((b b) (:)) 'g') show) 13 -- liberating `'g'` from parentheses -- not implied by left-assoc. u5 = b b (:) 'g' show 13 -- `u4` without the parentheses which -- left-associativity make redundant
solution = b b -- equivalently, (.) (.)
We can verify that this definition of
u' evaluate to identical values.
ghci> u' "g13"
More generally, this mechanical procedure can transform an arbitrary, properly typed expression with explicit parentheses, e.g.
exp = z (a b) (c (d e) f) (g h i)
to a form entirely devoid of explicit parentheses by applying single function
y to the first term
exp' = y z a b c d e f g h i
y consists exclusively of applications of the non-infix compose function
(.). With all the parentheses implied by left-associative function application,
exp' looks like this:
exp' = ((((((((((y z) a) b) c) d) e) f) g) h) i)
If we also allow the use of
y, we’ll see in the section below that we can arbitrarily permute the order of the terms that follow
Exercises: To test your understanding of this mechanical elimination of explicit parentheses, use only function application and
b (compose) to discover point-free expressions for
solution3 such that
v == v' and
w == w'.
v = length ((:) 1 [4,2]) v' = solution2 length (:) 1 [4,2] w = (++) "elab" ((:) 'o' "rate") w' = solution3 (++) "elab" (:) 'o' "rate"
ghci> v 3 ghci> w "elaborate"
A more complicated example
C from combinator logic, defined as
C x y z = x z y, plays a role similar to
flip and will augment our mechanical procedure with the ability to carry out the transformation
x z y => C x y z. Prepending
C to an expression of three terms exchanges the positions of the last two.
Consider this expression for
q and a few renamed combinators
c = flip divide = (/) mult = (*) q = divide 3 (mult 5 4) -- equivalent to `3 / (5 * 4)` q' = complexSoln divide mult 3 5 4
We now solve for a definition of
complexSoln using only function application and the combinators
c such that
q == q'.
In the comments next to the first few lines, I’ll show all the parentheses explicitly, except the outer-most pair.
q2 = divide 3 (mult 5 4) -- (divide 3) ((mult 5) 4) q3 = b (divide 3) (mult 5) 4 -- ((b (divide 3)) (mult 5)) 4 q4 = b (b (divide 3)) mult 5 4 -- (((b (b (divide 3))) mult) 5) 4 q5 = b (b b divide 3) mult 5 4 q6 = b b (b b divide) 3 mult 5 4 q7 = b (b b) (b b) divide 3 mult 5 4 q8 = c (b (b b) (b b) divide) mult 3 5 4 q9 = b c (b (b b) (b b)) divide mult 3 5 4
So we can eliminate all the parentheses around our arguments to
complexSoln = b c (b (b b) (b b))
We can verify that
ghci> q 0.15 ghci> q' 0.15
If we try to eliminate all the parentheses with just these combinators, our blog post will start to look like a page from “A New Kind of Science”.
q10 = b (b c) (b (b b)) (b b) divide mult 3 5 4 q11 = b (b (b c) (b (b b))) b b divide mult 3 5 4 q12 = b b (b (b c)) (b (b b)) b b divide mult 3 5 4 q13 = b (b b (b (b c))) b (b b) b b divide mult 3 5 4 q14 = b b (b (b b (b (b c)))) b b b b b divide mult 3 5 4 q15 = b (b b) b (b b (b (b c))) b b b b b divide mult 3 5 4 q16 = b (b (b b) b) (b b) (b (b c)) b b b b b divide mult 3 5 4 q17 = b (b (b (b b) b) (b b)) b (b c) b b b b b divide mult 3 5 4 q18 = b (b (b (b (b b) b) (b b)) b) b c b b b b b divide mult 3 5 4
q[1-18] all evaluate to the same thing but we’ll never be free of all the parentheses just using
b. Using this procedure, we foist the need to use explicit parentheses on the solution functions we prepend to the original expressions.
Solution to exercises posed in the first section
solution2 = b b b
solution3 = b (b b b)
An alternative to
solution3' = b (b b) (b b)
A derivation of
w = (++) "elab" ((:) 'o' "rate") w = b ((++) "elab") ((:) 'o') "rate" w = b (b ((++) "elab")) (:) 'o' "rate" w = b b b ((++) "elab") (:) 'o' "rate" w = b (b b b) (++) "elab" (:) 'o' "rate"
A derivation of
w = (++) "elab" ((:) 'o' "rate") w = b ((++) "elab") ((:) 'o') "rate" w = b b (b b (++)) "elab" (:) 'o' "rate" w = b (b b) (b b) (++) "elab" (:) 'o' "rate"