# 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 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 = (.)`

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 redundant
```

Therefore,

`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 i`

where `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 4
```

We 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 4
```

So 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.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`

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"
```