The B₁ and ϕ₁ Combinators

Conor Hoekstra · February 3, 2023

APL   C++   Combinatory Logic   Haskell   Python

On the most recent episode of ArrayCast, we interviewed Michael Higginson about his path to the the array languages Q and APL. He was the most recent winner of the Dyalog APL Contest (in the professional category). During the podcast, he mentioned two beautiful solutions to two of the Phase 1 problems in the contest that, although never mentioned, were beautiful examples of using combinators.

The B₁ Combinator

Problem 2: Attack of the Mutations

This problem asks you to identify the number of different values (compared elementwise) for two equally lengthed strings. In Python, it might look something like this:

def num_different(s1: str, s2: str):
    n = 0
    for a, b in zip(s1, s2):
        if a != b:
            n += 1
    return n

⬆️ Run this Code

However, if you have watched my ITM anti-pattern talk or one of my Python talks, you will know I dislike this kind of Python code. I would prefer something more like this:

def num_different(s1: str, s2: str):
    return sum(a != b for a, b in zip(s1, s2))

⬆️ Run this Code

If you don’t like implicity converting booleans to integers, you can also do something like:

def num_different(s1: str, s2: str):
    return sum(1 for a, b in zip(s1, s2) if a != b)

⬆️ Run this Code

Or if you C++, you can make use of transform_reduce:

auto num_different(std::string_view s1, std::string_view s2) {
    return std::transform_reduce(
        s1.begin(), s1.end(), s2.begin(), 0, 
        std::plus{}, 
        std::not_equal_to{});
}

⬆️ Run this Code

Whichever solution you prefer, hopefully the idea behind the problem is clear.

However, in APL, the solution is the following:

image

This is an example of a “2-train” in APL. The +/ reads plus reduce, in other words sum. The ≠ reads (hopefully obviously) not equal. So together, +/≠ reads sum not equal, which is a pretty good description of what we are doing. The tricky (and beautiful) part of this solution is what a “2-train” is in APL. In our case where we will be passing 2 arguments to this function (s1 and s2), it is the B₁ combinator. The B₁ combinator has the following evaluation (assuming our two arguments are s1 and s2):

image

We pass both arguments to the binary function ≠ (note that binary functions are always infix in APL). We then take the result of this operation and pass it to the unary function, in our case +/. Tracing the example of using the two strings cats and city, we get:

image

⬆️ Run this Code

The B₁ combinator is a beautiful thing and is one of my favorite combinators. It was nicknamed the Blackbird by Raymond Smullyan. It implictly exists in the C++ solution. Whenever you use the std::transform_reduce algorithm, you provide two binary operations. The first will be combined with std::reduce to form a reduction. The reduction takes place after zipping the two sequences together using the second binary operation. If you squint hard, you can see the relationship between the APL and C++ soluiton.

It might is easier to see relationship between APL and C++ by looking at an in-between language, Haskell (for the Haskell uninitiated, /= is not equal)

import Data.Composition (.:) -- The B₁ Combinator

transformReduce reduceOp zipOp = foldl1 reduceOp .: zipWith zipOp
numDiffs = transformReduce (+) (/=)

numDiffs "cats" "city" -- 2

Absolutely beautiful. Now, the Haskell expert will know that this doesn’t actually work. That is because (/=) returns a boolean and you can’t sum booleans. So the working Haskell solution is actually:

transformReduce reduceOp zipOp = foldl1 reduceOp .: zipWith zipOp
numDiffs = transformReduce (+) (fromEnum .: (/=))

numDiffs "cats" "city" -- 2

⬆️ Run this Code

Would you look at that! Another use of the B₁ combinator. We need to convert the boolen to an integer, aka apply fromEnum (which does that conversion) after applying the (/=) binary operation, aka - the B₁ Combinator! So amazing!

And just to satisfy the Haskell programmer that is thinking in their head “that function wouldn’t be called transformReduce in Haskell” and “those argument names are too long” (which I agree), here you are:

zipFold f g = foldl1 f .: zipWith g
numDiffs = zipFold (+) (fromEnum .: (/=))

numDiffs "cats" "city" -- 2

⬆️ Run this Code

I haven’t mentioned this till now, but in APL, they don’t refer to combinators as combinators. If it is function juxtaposition they are called trains, otherwise it is an operator. The two argument 2-train in APL is called atop, but there is also an atop operator: ⍤. So the following two are equivalent:

image

This is also highlighted in my ARRAY 2022 paper Combinatory Logic and Combinators in Array Languages. The relevant excerpt from that paper highlights the B₁ Combinator in J and BQN as well, two other array languages.

image

The ϕ₁ Combinator

Problem 3: Uniquely Qualified

This problem is: given two lists, what elements only show up in one of the lists (not both). A basic solution in Python might look like the following:

def only_in_one_list(a, b):
    res = []
    for x in a:
        if x not in b:
            res.append(x)
    for x in b:
        if x not in a:
            res.append(x)
    return res

⬆️ Run this Code

However, this solution once again violates my least favorite anti-pattern, ITM. A better and much more idiomatic Python solution is the following:

def only_in_one_list(a, b):
    both = set(a) & set(b)
    return [x for x in a + b if x not in both]

⬆️ Run this Code

However, the solution in APL is the following:

image

This is an example of a “3-train” in APL. The ∪ reads union, the ~ reads without, and the ∩ reads intersection. So together, ∪~∩ reads union without intersection, which once again is a pretty good (if not amazing) description of what we are doing. And once again, the tricky (and beautiful) part of this solution is what a “3-train” is in APL. In our case where we will be passing 2 arguments to this function (a and b), it is the ϕ₁ combinator. The ϕ₁ combinator has the following evaluation (assuming are two arguments are a and b):

image

We pass both arguments to the binary functions ∪ and ∩. We then take the results of these operation and pass it to the middle binary function, in our case ~. Tracing the example of using the two lists 1 2 3 4 and 3 4 5 6, we get:

image

⬆️ Run this Code

Although the ϕ combinator was given a nickname by Raymond Smullyan (the Phoenix), the ϕ₁ combinator wasn’t given a nickname … until recently that is. It was nicked the Pheasant in my aforementioned paper on combinators in array langauges.

In APL, 3-trains are called “forks.” Spefically, this is a dyadic fork because we are passing it two arguments. The Table 16 is the relevant table from my paper but it isn’t super interesting as every array language (APL, BQN & J) call it the same thing.

image

What is the point?

As Michael mentions in the ArrayCast podcast:

“It is like a line from a haiku…
there is something poetic about it…
it is very beautiful.”

This was in reference to the APL 3-train solution to Problem 3. However, it isn’t all about aesthetics.

I assert that combinators provide a greater opportunity for linear collection oriented programming, which is my favorite programming paradigm. Furthermore, I assert that in an collection oriented programming libraries such as:

Standard Libraries

Third Party Libraries

combinators can increase the opportunity for stream fusion and potentially index fusion as well. How far you could get with a library versus how far you could get with a compiler and new programming language is a question I hope to answer in the future.

Feel free to leave a comment on the GitHub discussion or the Reddit thread.

Twitter, Facebook