Higher-order Functions and Binary Operations

note

This article can be regarded as a continuation of my blog post published months ago, as there is a good amount of set theory involved here as well.

Summation Function

Recursive Implementation

def sum(term, a, next, b):
    if a > b:
        return 0
    else:
        return term(a) + sum(term, next(a), next, b)

Iterative Implementation

def sum(term, a, next, b):
    result, curr_idx = 0, a
    while curr_idx <= b:
        result += term(curr_idx)
        curr_idx = next(curr_idx)
    return result

Product Function

Recursive Implementation

def product(term, a, next, b):
    if a > b:
        return 1
    else:
        return term(a) * product(term, next(a), next, b)

Iterative Implementation

def product(term, a, next, b):
    result, curr_idx = 1, a
    while curr_idx <= b:
        result *= term(curr_idx)
        curr_idx = next(curr_idx)
    return result

Relationship of sum and product with Set Theory

Let's outline some set-theoretic definitions of addition and multiplication operations (on the set of natural numbers $\mathbb{N}$, which includes $0$ here).

We define a sequence of functions $\langle f_m : m \in \mathbb{N }\rangle$ such that for a given $m \in \mathbb{N}$, $f_m : \mathbb{N} \to \mathbb{N}$ is the unique function such that $f_m(0)=m$ and for all $n \in \mathbb{N}$, $f_m(S(n))=S(f_m(n))$, as well as a sequence of functions $\langle g_m : m \in \mathbb{N} \rangle$ such that for a given $m \in \mathbb{N}$, $g_m : \mathbb{N} \to \mathbb{N}$ is the unique function such that $g_m(0)=0$ and for all $n \in \mathbb{N}$, $g_m(S(n)) = f_{g_m(n)}(m)$.¹

Both definitions above involve $S$, which is the successor function that does not have to be unique, and forms an integral part of the Peano's axioms that formalises the concept of natural numbers.

For $m,n \in \mathbb{N}$, the addition operation $+$ is then defined as $m + n = f_m(n)$ and multiplication operation $\cdot$ is defined as $m \cdot n = g_m(n)$.

Interestingly, the sum and product functions above can be said to bear some similarities to these set-theoretic definitions of summation and multiplication: the term function can be viewed as an auxiliary function $t : \mathbb{N} \to \mathbb{R}$ that sends some, if not all, natural numbers to some real numbers (i.e. the set of natural numbers are treated here as an index set), whereas the next function is analogous to the successor function $S$, though it may not be the standard one as in the Peano's axioms that generates all natural numbers.

In other words, one can say that the sum and product functions define the addition and multiplication operations on real numbers isomorphically based on the set-theoretic construction of these operations as described above.

Binary Operation Function

This is a further abstraction of the sum and product functions as above that represents (commutative) binary operations in general.

The base parameter here can then be regarded as the identity element of a binary operation.

Recursive Implementation

def fold(op, term, a, next, b, base):
    if a > b:
        return base
    else:
        return op(term(a), fold(op, term, next(a), next, b, base))

Iterative Implementation

def fold(op, term, a, next, b, base):
    current_idx, result = a, base
    while current_idx <= b:
        result = op(term(current_idx), result)
        current_idx = next(current_idx)
    return result

Application

Using fold, the sum and product functions can just be defined with a function call.

sum = lambda term, a, next, b: fold(lambda x, y: x + y, term, a, next, b, 0)
product = lambda term, a, next, b: fold(lambda x, y: x * y, term, a, next, b, 1)

Accumulate Function

This is another further abstraction of the sum and product functions as above that represents (right-to-left or fold right, thus possibly noncommutative) binary operations, e.g. matrix multiplication.

This function, which is called accumulate here, can be mathematically described like so, with $\oplus$ denoting the combiner function parameter

$$accumulate(\oplus, f, a, next, b) : (f(a_1) \oplus (f(a_2) \oplus ( \cdots \oplus (f(a_n) \oplus base)\cdots)))$$

This was featured as a tutorial question of a university programming methodology course I've previously taken.

The following code snippets are my solutions to the question.

Recursive Implementation

def accumulate(combiner, base, term, a, next, b):
    if a > b:
        return base
    else:
        return combiner(term(a), accumulate(combiner, base, term, next(a), next, b))

Iterative Implementation

def accumulate(combiner, null_value, term, a, next, b):
    if a > b:
        return null_value
    total = null_value
    current = a
    limit = b
    while current >= a:
        while current < limit:
            current = next(current)
        total = combiner(term(current), total)
        limit = current
        current = a
    return total

Application

Using accumulate, the sum and product functions can just be defined with a function call.

sum = lambda term, a, next, b: accumulate(lambda x, y: x + y, 0, term, a, next, b)
product = lambda term, a, next, b: accumulate(lambda x, y: x * y, 1, term, a, next, b)

The heavy use of HOFs and functional abstraction in code leads to the topic of functional programming, of which many resources are available online.

More Applications of accumulate and fold

We can also implement the greatest common divisor (GCD) and lowest common multiple (LCM) functions using the Euclidean algorithm for any number of integers using the accumulate or fold HOF, by utilising the associativity of both of the functions (i.e. the direction goes both leftwards and rightwards, which is why fold and accumulate can be used interchangeably here). The implementation below uses fold.

Note that the implementation of the LCM function below relies on the fact that for two integers $a$ and $b$, we have

$$\gcd(a,b) \cdot \mathrm{lcm}(a,b) = | a \cdot b |.$$

def gcd_euclidean(a, b):
    if abs(a) >= abs(b):
        first, second = abs(a), abs(b)
    elif abs(a) < abs(b):
        first, second = abs(b), abs(a)
    while second > 0:
        first, second = second, first % second
    return first

def lcm_euclidean(a, b):
    return (abs(a * b) // gcd_euclidean(a, b))

def gcd_euclidean_general(*terms):
    return fold(gcd_euclidean, lambda i: terms[i], 0, lambda i: i+1, len(terms)-1, terms[0])

def lcm_euclidean_general(*terms):
    return fold(lcm_euclidean, lambda i: terms[i], 0, lambda i: i+1, len(terms)-1, terms[0])

test_1 = (140, -224, -560, 324)
test_2 = (2, -7, 6)
print(gcd_euclidean_general(*test_1)) # 4
print(lcm_euclidean_general(*test_2)) # 42

Footnotes

1. These definitions are taken from the lecture notes of the Set Theory course conducted during the Fall 2022 semester by Dilip Raghavan in National University of Singapore. ↩