Higher Order Functions

In the first article of the series, we talked about functions in Python as first class citizens, which enables two things:

1. Functions can be passed as parameters to other functions
2. Functions can be returned from other functions.

We looked at the first point in the previous article, and we will look at the second one now.

This article builds on the two previous in the series, so if you haven't already read them, do so now.

Functions that return a function

Let us start with an example of a function that returns a function

def create_adder(n):
    def adder(x):
        return n + x
    return adder

In the example above, create_adder returns adder which is a function.

You call create_adder and pass in a number n. It will return a function object that takes a single input x and adds n to it

add_5 = create_adder(5)
add_5(10) # 15

inc = create_adder(1)
inc(7) # 8

dec = create_adder(-1)
dec(7) # 6

As you can see, we can use create_adder to create many different functions. add_5 will add 5 to any number you pass in, while inc and dec will increment and decrement respectively.

create_adder is called a factory function. The name comes from how a factory works: you can place an order for a certain configuration of, and a factory will then take that configuration and product an object. The same way, a factory function takes in some configuration parameters, creates an appropriate function object and returns the function object. By passing in different parameters, we can create differently configured functions.

Closures

Here is create_adder again. You might notice something odd when looking at this code

def create_adder(n):
    def adder(x):
        return n + x
    return adder

The parameter n is a local variable for create_adder. This means that while lines 2-4 are executing, the variable n is available. Once create_adder function returns then n is out of scope and destroyed.

inc = create_adder(1)
print(n) # error! no such variable
inc(5) # calculates n + 5

In the code above, line 2 will give an error because once create_adder has completed and returned, n does not exist. This is fine. But if we execute inc(5), it calculates n + x and returns 6. How is this inc function able to access n if that variable is out of scope by the time that line is executed??

The answer is closures. What is a closure? A closure of a function refers to the actual code of the function, plus access to the scopes that the function has access to when the function was created.

Here is create_adder again

def create_adder(n):
    def adder(x):
        return n + x
    return adder

The adder function is created on line 2. All the scopes that are available at this point (in this case, local scope of create_adder + global scope) will be put into the closure of adder. Thus, when adder is executed later on, it will have access to its closure and will be able to access the variable n via the closure.

Higher order functions

Now that we have looked at passing functions as parameters, and returning functions from other functions, we will combine these two concepts.

We are going to look at functions that take a function as a parameter. And they will return a function also.

Let us return to the create_adder function above

def create_adder(n):
    def adder(x):
        return n + x
    return adder

This function will take a parameter n and return a function. The returned function will take an input n and add x to it.

But what if, instead of adding, we want to do some other operation, eg: multiplying? Do we need to create a new function like this?

def create_multiplier(n):
   def multiplier(x):
       return n * x
   return multiplier

Hmm, this looks a lot like create_adder the only difference is line 3 where n + x is replaced by n * x.

How can we abstract this out? We already know the answer from the previous article. We can wrap the operation to be performed into a function and pass it in, while abstracting the common parts!

That insight brings us to this solution

def create_do_operation(fn, n):
    def do_operation(x):
        return fn(x, n)
    return do_operation

We can pass in any function as the first parameter, along with n

def add(a, b):
    return a + b
    
def mul(a, b):
    return a * b

inc = create_do_operation(add, 1)
inc(5) # 6
dec = create_do_operation(add, -1)
dec(5) # 4
dbl = create_do_operation(mul, 2)
dbl(5) # 10
half = create_do_operation(mul, 0.5)
half(5) # 2.5

Actually, python already has implementations of add and mul in the operator module, so we don't need to define it ourselves. We can just do

import operator

inc = create_do_operation(operator.add, 1)
inc(5) # 6

create_do_operation is a function that takes a function as a parameter, eg: add and returns another function as the result, in this case inc. Such functions which take a function as input and return a function as output are called higher order functions.

Regular functions take some input data and do some transformation and return some other data as output. Higher order functions take a function as input, do some transformation, and return some other function as output. In order words, these are functions that operate on functions, hence the term higher order functions

Currying

Let us think about what create_do_operation actually does. It takes in a function that requires two parameters (eg: add, mul etc). It also takes in n which is the first parameter for that function.

Then it returns a function that takes the second parameter x as input. Later on we can call this function passing in x and it will execute the original function and give the result.

The add function is a binary function. This means we need to pass it two parameters together, eg: add(2, 3). What create_do_operation allows us to do is to pass in one parameter now and the second parameter later.

add_2 = create_do_operation(operator.add, 2) # pass first parameter 2 now
...
add_2(3) # pass second parameter 3 later on and get result 5

This transformation of taking a function that requires certain number of arguments and transforming it into another function where we can pass some arguments now and the remaining later on is called currying. It is named after the mathematician Haskell Curry. (The programming language Haskell is also named after him).

A variation on this operation is called partial application. Applying a function is a term that means to pass in the parameters and get the result. Thus partial application means to only pass in part of the parameters, and pass the remaining ones later.

Actually, we don't need to write our own curry function like we did above. Python already comes with one in the standard library. It is called partial and is a part of the functools module. Here is how to use it

import functools
import operator

inc = functools.partial(operator.add, 1)
inc(5) # 6

The partial function is quite flexible. You can partially apply any number of parameters. If you have a function with three parameters, you can apply the first and second now, and pass in the third one later on. Check the documentation page for all the details.

partial is just one of the many higher order functions that are possible. Higher order functions are the bedrock of functional programming style.

A Practical Application

At this point you might be thinking that this is cool and all, but where exactly would we need to pass in one parameter now and another one later. Is this just a toy problem or does it actually have practical application??

What if I said that you have probably been using partial application every day in your python code, but you never realised it.

Let's take a look. Prepare to be surprised 😎

We start with a Person class with a name attribute and a greet method

class Person:
    def __init__(self, name):
        self.name = name
        
    def greet(self, greeting):
        return f"{greeting} {self.name}"

Nothing too complex here. We can now create a Person object and call greet

p = Person("Aparna")
p.greet("Hello") # Hello Aparna

Do you see something odd?

Our greet method is defined to take two parameters def greet(self, greeting). But when calling the method, we don't pass that first parameter, we just do p.greet("Hello")

What happened to self? You might have been told that python fills in the self parameter by itself. But how??

You are probably seeing where this is going. Yes, the self parameter is partially applied when the object is created. This is called binding the function to the object. That is why we don't need to pass the parameter when we make our call.

You can get a hint of this if we print out the function object in the class and object

>>> print(Person.greet)
<function Person.greet at 0x0000019363FB0EE0>
>>> print(p.greet)
<bound method Person.greet of <__main__.Person object at 0x0000019363F3A350>>

When we call the raw function directly, we need to explicitly pass in the self object. But when calling the bound function (where self has already been applied), we don't need to

>>> Person.greet("Hello") # Error, requires two parameters
>>> Person.greet(p, "Hello") # ok, "Hello Aparna"
>>> p.greet("Hello") # ok, bound function doesnt need self

Let us try to simulate what python is doing internally. We will start with a raw function greet, (note that greet is not part of any class), then manually bind it to the object.

import functools

def greet(self, greeting):
    return f"{greeting} {self.name}"
    
def createPerson(name):
    obj = object()
    # below is what the __init__ does
    obj.name = name 
    # apply obj as the first parameter
    obj.greet = functools.partial(greet, obj) 
    # Now obj.greet is the bound version of raw function greet
    return obj
    
p = createPerson("Aparna")
p.greet("Hello") # Hello Aparna

In other words, a method is nothing but a partially applied function🤯

An interesting titbit

What currying shows us is that a multi parameter function is nothing but a sequence of single parameter functions. In fact, the Haskell programming language does not support multi parameter functions at all. Every function is only a single parameter function.

This is the signature of add function in Haskell (arrow indicates function)

add :: Integer -> (Integer -> Integer)

This signature says that add is a function which takes one integer (this is the first param) and returns a function. The returned function takes one integer (this is the second param) and returns an integer (the sum).