Lab 10: Higher-Order Functions (HOF)¶

During my time being part of the IT5001 teaching team, this part always feels like going through a chapter in a math textbook. The problems presented in the consequent midterm and finals components demonstrate how powerful they can be, but in my opinion (and perhaps this is shared by a lot of IT5001 students, past and present) it demonstrates how convoluted they can be.

We deal with anonymous functions here, but to truly appreciate it there's a need to understand how they work first before even going into the application of such concepts. There will be no lab activity this time, but I will also include one where we get a short preview of something close to the next lab (i.e., map, filter and reduce). Instead, there will be a very small problem set for you to practice with (realistically I do not see this being used in such a complex manner).

Getting Started¶

A lot of the theory here was outsourced from existing online resources, since dwelling on the technicalities and definitions of it all is not really what the prof I am working with does, and I learnt the trick to understanding lambda expressions and appreciating the small moments in when they are helpful without thoroughly going through the inspiration that spawned this programming language feature I had not seen before. This is something you will see in functional programming, in which some types of software development (e.g., JavaScript frameworks like React.js and Next.js) are carried out.

We will start by running through what higher-order functions are before introducing anonymous functions (i.e., lambda expressions).

What are Higher-Order Functions?¶

Put simply, when a programming language supports higher-order functions, we say that such functions in said programming language have the ability to do these three things:

be able to receive functions as parameters for a function call as input
be able to return functions from another function as output
assign functions as values to variables

Essentially, this means that functions can be treated the same as primitive data types like integers, Boolean values, and floats. You can see this capability in functions like map(), filter() and reduce(). To illustrate a very simple version of the map() function, let's look at the following example.

def my_map(f, lst):
    # f: a function parameter to be applied onto each item in lst
    new_lst = []  # to be returned

    for item in lst:
        new_list.append(f(item))

    return new_lst

Here, my_map() takes in 2 parameters; one of them is a function f and the other a list lst. This function performs f() onto each element in lst and adds each output into a result list to be returned (i.e., new_lst).

Suppose this list were to receive a simple function that multiplies the input 3 times, and a list of strings or integers. It would look something like as follows:

def my_map(f, lst):
    # f: a function parameter to be applied onto each item in lst
    new_lst = []  # to be returned

    for item in lst:
        new_list.append(f(item))

    return new_lst


def multiply(x):
    # multiplies value of parameter x three times
    return x * 3


L = ['a', 'bc', 4]
print(my_map(multiply, L))  # ['aaa', 'bcbcbc', 12]

Now let's assume that we want this multiplication function be a little more dynamic (and encapsulated).

def my_map(n, lst):
    # n: an integer parameter that dictates how many times each element in lst is multiplied by
    def multiply(x):
        # multiplies value of parameter x three times
        return x * n

    new_lst = []  # to be returned

    for item in lst:
        new_lst.append(f(item))

    return new_lst


L = ['a', 'bc', 4]
print(my_map(3, L))  # ['aaa', 'bcbcbc', 12]
print(my_map(4, L))  # ['aaaa', 'bcbcbcbc', 16]

We now see the function multiply() from earlier be local only to my_map().

Strictly speaking, multiply() does not exist in the global scope, and it is only accessible and exists inside my_map().
Also, instead of taking in a function parameter, my_map() takes in an integer parameter n which becomes part of the local multiply() function.

By doing such, we dynamically assign the number of times each element in lst is multiplied by in my_map(). What we have seen here is how functions can be passed in like primitive values to a function call, and to a somewhat lesser extent, how local functions can exist within the scope of an outer function.

Now, let's zone in on multiply(). Suppose we want to create a similar function, but instead of returning the value of an expression, it prepares a function as output instead.

def mult_func(n):
    def multiply(x):
        return x * n

    return multiply

From experience, I have seen this before in JavaScript or TypeScript, especially if you dabble with frameworks like React.js and Next.js. Let's break this down:

mult_func() takes in integer parameter n as input, and returns a function as output.
The output function is multiply(), whose state is determined by what the value of n is. For example,
- if n = 2, the local function multiply() returns the value of x * 2.
- if n = 3, the local function multiply() returns the value of x * 3.

Let's see how mult_func() can be used:

Python Shell

>>> mult_func(2)(2)
6
>>> mult_func(3)(2)
8
>>> mult_func(4)(6)
24
>>> mult_func(4)
<function mult_func.<locals>.multiply at 0x1083fe2a0>

Note the first three entered function calls. The first pair of round parentheses after "mult_func" represents the parameters passed into the function mult_func(). For each of mult_func(2), mult_func(3) and mult_func(4) here, all of them result in a function that's slightly different from each other. Namely, they all take in parameter x, but return the result of expressions x * 2, x * 3 and x * 4 respectively. You will not see this explicitly though, just calling mult_func(2), mult_func(3), etc. will give a standard response containing the location in memory in which this function resides (refer to the last output in the earlier Python shell). With this, we see how functions can be output values for other functions.

Lambda Expressions¶

With the most recent mult_func() example, let's say the local multiply() function is regarded like a throwaway function. That is, you expect to use this once or it is not significant enough to be kept in a variable. We can make this function anonymous by using lambda expressions. Here's how it will look like using them to be assigned to a variable and without:

Assign to VariableDo Not Assign to VariableLambda Expressions only

def mult_func(n):
    multiply = lambda x: x * n
    return multiply

def mult_func(n):
    return lambda x: x * n

mult_func = lambda n: lambda x: x * n

Additionally, here's what happens if we pass in lambda expressions as the first parameter value (i.e., f) in our my_map() function from much earlier.

def my_map(f, lst):
    # f: a function parameter to be applied onto each item in lst
    new_lst = []  # to be returned

    for item in lst:
        new_lst.append(f(item))

    return new_lst


L = ['a', 'bc', 4]
print(my_map(lambda x: x*3, L))  # ['aaa', 'bcbcbc', 12]
print(my_map(lambda x: x*4, L))  # ['aaaa', 'bcbcbcbc', 16]

L2 = [(1, 2), (3, 4), (5, 6)]
print(my_map(lambda x: x[0]*x[1]+1, L2)) # [3, 13, 31]

At this point, you may be confused as to what each parts of the lambda expression is. Let's backtrack here with a very simple lambda expression:

lambda a, b: a + b

Function parameters are stated after the lambda keyword and before the colon :. Like regular functions, you can have any number of parameters in a lambda expression (no parameters is okay).
The returned value for this "function" is the expression that comes after the colon :. Unlike some functions, lambda expressions only return the result of evaluating one expression, which could be a simple arithmetic expression to calling other complex function(s) to evaluate an expression. This part cannot be empty.

When calling a lambda expression, the set of parameter values to be passed in are segregated in a next pair of round parentheses. Here is an example of calling this simple lambda expression by passing in values for parameters a and b:

Python Shell

>>> (lambda a, b: a + b)(1, 2)
3

The same rule with functions apply here - if a lambda expression has n parameters, n parameter values are expected when calling said lambda expression.

The Math Behind It¶

If you'd like to know more about it, you can refer to this comprehensive breakdown on lambda calculus right HERE.

Optional: It's Easier with One Trick Only¶

In class, I often say that since lambda expressions are anonymous functions (i.e., functions without given names), they are like babies with unnamed potential. When encountering long expressions with use of multiple lambda expressions, sometimes giving them names can help with visualizing what is going on.

Suppose we have a long expression like as follows:

(lambda p, q: lambda r: p(q + r))(lambda x: x**2, 5)(13)

The full working to obtain this result is like as such:

(lambda p, q: lambda r: p(q + r))(lambda x: x**2, 5)(13)
= (lambda r: (lambda x: x**2)(5 + r))(13)
= (lambda x: x**2)(5 + 13)
= (lambda x: x**2)(18)
= 324

From my time teaching this to students, I see that it's pretty complicated and overwhelming on first glance. However, this trick involves giving identifier names to each lambda expression (it works in the same spirit of rewriting parts of a complex math problem into different variables; in a line of working somewhere in a complex math problem you may choose to do something like: "Let \(x = x*3-x+1\).").

We will use up to 3 substitutions here (there's no hard rule on how many times you use this substitution method throughout your working).

Substitution 1¶

Right here, let's give the first lambda expression (lambda p, q: lambda r: p(q + r)) an identifier name f:

f = lambda p, q: lambda r: p(q + r)

# Equivalent function form
def f(p, q):
    return lambda r: p(q + r)

By using this substitution for name f, our full working looks like as follows:

# it is clear now that we are passing "lambda x: x**2" into p and `5` into q
f(lambda x: x**2, 5)(13)
= (lambda r: (lambda x: x**2)(5 + r))(13)
= (lambda x: x**2)(5 + 13)
= (lambda x: x**2)(18)
= 324

Substitution 2¶

We can also substitute lambda x: x**2 with the name g:

g = lambda x: x**2

# Equivalent function form
def g(x):
    return x**2

By using this substitution for name g, our full working looks like as follows:

# it is clear now that we are passing "function g" into p and `5` into q
f(g, 5)(13)
= (lambda r: g(5 + r))(13)
= g(5 + 13)
= g(18)   # 18**2
= 324

Right here, I think it's easier to visualize what you are working with and breeze through the problem set.

Substitution 3¶

Optionally, we can also substitute the resulting lambda expression returned from f in this instance with variable name h:

h = lambda r: g(5 + r)

# Equivalent function form
def h(r):
    return g(5 + r)   # which then evaluates (5 + r)**2

By using this substitution for name h, our full working looks like as follows:

f(g, 5)(13)
= h(13)
= g(5 + 13)
= g(18)   # 18**2
= 324

One could say up to 2 substitutions in this case is enough, but go at it in your own pace. If at any point you are able to do this mentally without needing substitution, you can reduce or completely eliminate the need to use this trick to make evaluating such expressions easier.

Problem Set¶

Problem 1¶

Rewrite the following functions as lambda expressions. Truncate them with list comprehension or helper functions (as lambda expressions) if necessary.

Function 1
def f(x): 
    return x + 1

Solution for Function 1

f = lambda x: x + 1

Function 2
def my_fn(x):
    if x < 18:
        return 18
    return x

Solution for Function 2

my_fn = lambda x: 18 if x < 18 else x

Function 3
def f(x):
    def g(x):
        return -x if x < 0 else x
    return g(x) ** 2

Solution for Function 3

f = lambda x: (lambda y: -y if y < 0 else y)(x) ** 2

Function 4
def my_filter(fn, lst):
    result = []
    for elem in lst:
        if fn(elem):
            result.append(elem)
    return result

Solution for Function 4

my_filter = lambda fn, lst: [elem for elem in lst if fn(elem)]

Function 5: Approximate sine function, using Taylor series
from math import factorial


def my_sin(x, n):
    total = 0
    for i in range(n):
        total += (-1)**(i) / factorial(2*i+1) * x**(2i+1)
    return total

Assume that the formula for the approximate sine function is as follows:

\[ \sin x = \sum_{i=0}^{n-1} {\frac{(-1)^n}{(2n+1)!}x^{2n+1}} = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \cdots \text{ for all }x \]

Solution for Function 5

my_sin = lambda x, n: sum((-1)**(i) / factorial(2*i+1) * x**(2i+1) for i in range(n))

Problem 2¶

Evaluate the result of the following expressions.