Arbitrary Parenthesization
Using only the B combinator
I recently wondered whether the B combinator alone is capable of producing any parenthesization. My intuition was that this should be the case, but I found more or less nothing solid or concise about it, let alone an explicit construction. I’m sure this floats around somewhere, but anyways: The goal of this post is to be discoverable. To be short and intuitive instead of a deep dive.
I certainly had fun figuring all of the following out, so consider not reading the solution if you enjoy a good puzzle!
Problem
Imagine a list of terms t1
, t2
, t3
, t4
, … and it is your job to write a function f
such that f t1 t2 t3 t4 …
results in those same terms, but with a specific parenthesization, e.g. t1 (t2 t3) t4
. Specifics:
- Imagine a functional/lambda world where the implicit parenthesization of
t1 t2 t3 t4
is(((t1 t2) t3) t4)
since function application is left associative. The example above is really((t1 (t2 t3)) t4)
. In this post, I always omit implicit parentheses to improve readability. f
must be constructed by using only function application and combinatorB
, defined asB x y z = x (y z)
. For instance, the example behavior above can be achieved by definingf = B
.
Solution
All we need to build arbitrary parenthesizations are the following three observations:
f = B
groups the 2nd and 3rd argument off
(see above).f = B f'
results in the same parenthesization asf'
, but shifted one to the right. For example,f = B B
groups the 3rd and 4th parameter off
.f = B f' f''
applies the parenthesization off'
, followed by the one off''
. For example,f = B B B
groups the 2nd until 4th parameter off
, becauseB t1 t2 t3 t4 = t1 (t2 t3) t4
andB t1 (t2 t3) t4 = t1 ((t2 t3) t4) = t1 (t2 t3 t4)
.
Arbitrary parenthesizations can be composed this way. Rule 3 can be used to enlarge a grouped region (move )
to the right). Rule 2 moves everything to the right. Rule three allows multiple groups to be introduced, whether explicitly nested or not. The following example demonstrates both.
Example
Let’s find f
with f t1 t2 t3 t4 t5 t6 = t1 (t2 t3) (t4 (t5 t6))
. There are three (non-implicit) parentheses, so we can decompose f = B (B f' f'') f'''
or f = B f' (B f'' f''')
and focus on finding f'
, f''
and f'''
.
Which one of these is responsible for which pair of parentheses is our choice, except that the grouping of t5
and t6
must happen prior to the grouping with t4
as there is no way to “break open” already parenthesized terms. Note also that the earlier groupings can influence later ones in terms of argument indices: If f'
groups t2
and t3
, then f''
sees (t2 t3)
as the 2nd argument, t4
as the 3rd, and so on.
Here I pick
f' t1 t2 t3 t4 t5 t6 = t1 t2 t3 t4 (t5 t6)
f'' t1 t2 t3 t4 t5 = t1 t2 t3 (t4 t5)
f''' t1 t2 t3 = t1 (t2 t3)
This is all just B
shifted right by 3, 2 and not at all, respectively:
f' = B (B (B B))
f'' = B (B B)
f''' = B
So f = B (B (B (B B))) (B (B (B B)) B)
. (Side note: This is not the smallest possible construction. For instance, choosing f’ = B
makes the other two components shorter due to mentioned argument grouping effect.)
Let’s put it to the test, one reduction step at a time. Terms participating in the next reduction are highlighted bold:
B (B (B (B B))) (B (B (B B)) B) t1 t2 t3 t4 t5 t6
B (B (B B)) (B (B (B B)) B t1) t2 t3 t4 t5 t6
B (B (B B)) (B (B B) (B t1)) t2 t3 t4 t5 t6
B (B B) (B (B B) (B t1) t2) t3 t4 t5 t6
B (B B) (B B (B t1 t2)) t3 t4 t5 t6
B B (B B (B t1 t2) t3) t4 t5 t6
B B (B (B t1 t2 t3)) t4 t5 t6
B B (B (t1 (t2 t3))) t4 t5 t6
B (B (t1 (t2 t3)) t4) t5 t6
B (t1 (t2 t3)) t4 (t5 t6)
t1 (t2 t3) (t4 (t5 t6))
Deconstruction and Minimalism
It is worth noting that observations 1 to 3 above are “complete” in the sense that we can also use them to deconstruct and interpret arbitrary B
-terms: They must either fall under one of the three cases or have the form B x y z ...
and hence be reducible. Repeated reduction of B
-terms terminates since each reduction reduces the total number of B
s by one. In other words, fully reduced B
-terms are recursively interpretable via case analysis.
Note also that this completeness implies that the parenthesization algorithm introduced here is capable of producing a term that uses the minimal number of B
s to achieve its goal. However, note that we did not provide a deterministic way to retrieve this minimal term; the order in which observations 1 to 3 are applied matters.
Conclusion
B is a one-point basis for arbitrary parenthesizations.
However, ironically, the “empty” parenthesization (identity function) is not expressible using any combination of Bs. That seems like an acceptable exception, since doing nothing can also be achieved by not applying any f
at all, i.e. by using zero Bs.