The Power of Function Composition — to Find If an Array Is Special

I originally posted an extended version of this post on my blog.

Passing the result of a function to another isn't the only way to compose two functions.

From math classes, we're used to composing two functions like this compose(f, g) = x => f(g(x)). But it turns out there are more ways.

That's my main takeaway from the talk "The Power of Function Composition" by Conor Hoekstra at NDC Conference 2024. YouTube recording here, in case you want to watch.

The talk shows how to find if an array is special using languages like Python, Haskell, and other obscure and esoteric ones to show function composition.

These are the lessons I learned, translating some code examples to C#.

A simple solution to find if an array is special

Let's find if an array is special.

An array is special if every pair of consecutive elements contains two numbers with different parity. For example, [4,3,1,6] isn't special. It has three pairs: 4,3, 3,1, and 1,6. The second pair has two odd numbers, which makes our array "not special."

Here's the LeetCode problem if you want to try it yourself.

And here's my solution before using any of the new concepts from the talk,

IEnumerable<(int First, int Second)> Pairs(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        yield return (array[i], array[i + 1]);
    }
    // Or simply:
    // return array.Zip(array.Skip(1));
}

bool HasDifferentParity((int First, int Second) pair)
    => pair.First % 2 != pair.Second % 2;

bool IsSpecial(int[] array)
    => Pairs(array).All(HasDifferentParity);

IsSpecial([1, 2, 3, 4]) // true
IsSpecial([4, 3, 1, 6]) // false

It uses Pairs() to generate the pairs of consecutive elements, HasDifferentParity() to find if both numbers in a pair are even or odd, and All() from LINQ. Nothing fancy!

Apart from the "usual" composition, there are other ways of composing functions

Here are some of them, in pseudo-code:

def i(x) = x
def k(x, y) = x
def ki(x, y) = y

def s(f, g) = \x => f(x, g(x))
def b(f, g) = \x => f(g(x)) // 👈

def c(f) = \x, y => f(y, x)
def w(f) = \x => f(x, x)

def d(f, g) = \x, y => f(x, g(y))
def b1(f, g) = \x, y => f(g(x, y))
def psi(f, g) = \x, y => f(g(x), g(y)) // 👈
def phi(f, g, h) = \x => g(f(x), h(x))

Let's take a close look at two of them.

b is the composition we all know. It passes the result of the second function to the first one. And psi passes two values to the second function and then calls the first one with both results.

Let's find if an array is special again, but composing functions

Let's revisit IsSpecial() but using "psi" this time,

IEnumerable<(int First, int Second)> Pairs(int[] array)
    => array.Zip(array.Skip(1));

bool IsEven(int x) => x % 2 == 0;
bool NotEqual(bool x, bool y) => x != y;

// A more general signature would be:
// Func<T1,T1,T3> Psi<T1, T2, T3>(Func<T2,T2,T3> f, Func<T1,T2> g)
// But to make things easier:
Func<int, int, bool> Psi(Func<bool, bool, bool> f, Func<int, bool> g)
//                  👆👆
    => (x, y) => f(g(x), g(y));

var hasDifferentParity = Psi(NotEqual, IsEven); // 👈
bool IsSpecial(int[] array)
    => Pairs(array).All(pair => hasDifferentParity(pair.First, pair.Second));

// or
bool IsSpecial(int[] array)
    => Pairs(array).All(pair => Psi(NotEqual, IsEven)(pair.First, pair.Second));
    //                         👆👆

IsSpecial([1, 2, 3, 4]) // true
IsSpecial([1, 2, 4, 3]) // false

Instead of HasDifferentParity(), it uses Psi(NotEqual, IsEven).

And again, here's the pseudo-code of psi: psi(f, g) = \x, y => f(g(x), g(y)).

Psi(NotEqual, IsEven) receives two integers, calls IsEven with each of them, and passes both results to NotEqual.

Et voilà! That's a new way of composition.

This is one of the talks to replay multiple times if you want to grasp its concepts, since they're not that common. Also, it covers the same example in other less known languages that I don't even remember their names.

Since probably you won't use those obscure languages—I won't, learn the composition part of the talk. It's mind blowing.

Refactor your coding career with my free 7-day email course. In just 7 emails, you'll get 10+ years of career lessons to avoid costly career mistakes.