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:
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.
u' = solution (:) 'g' show 13The 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 = (.)The 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 redundantTherefore,
solution = b b -- equivalently, (.) (.)We can verify that this definition of solution makes u and 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 z, i.e.
exp' = y z a b c d e f g h iwhere 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 flip in y, we’ll see in the section below that we can arbitrarily permute the order of the terms that follow y.
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 solution2 and 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 4We now solve for a definition of complexSoln using only function application and the combinators b and 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 4So we can eliminate all the parentheses around our arguments to complexSoln thus:
complexSoln = b c (b (b b) (b b))We can verify that q == q':
ghci> q
0.15
ghci> q'
0.15If 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 4q[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 bsolution3 = b (b b b)An alternative to solution3 is
solution3' = b (b b) (b b)A derivation of solution3:
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 solution3':
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"