Functional programming notes: Higher order functions

  3 mins read

In the previous post we defined functions and function composition. Now that we know how function composition works, we can take a look to the next concept, higher order functions (HOF):

Higher order functions

The idea behind higher order functions is that functions are values, hence functions can be assigned to variables as we do with Integers, Strings, etc… Functions that accept another functions as an argument or return functions are called higher order functions.

An example of a really common higher order function is map. For ex. the definition of map in Scala’s List class is:

def map[B](f: A => B): List[B]

The meaning of map is to apply a transformation to every element of the List and it returns a new List with all the new transformed elements.

If a language supports higher order functions, we say that the functions in that language are treated as first class citizens or that the functions are first class functions. Those terms mean the same as higher order functions but we use it differently for the language itself or the function that accept those functions as arguments.

One of the convenient usages of Higher order functions is to create inline functions. We call that, anonymous function or function literals. One example using the previously defined map, could be this:

List(1).map((i) => i + 1)

As you can see, the function (i) => i + 1 is passed in as an argument of the map function.

Partial application

Following the idea of higher order functions we can partially apply a function. This means that for a function that accepts a number of arguments N, we can fix or bind some of the arguments that it takes to reduce the arity of the function. So for example, consider this two functions:

def sum(a: Int, b: Int) = a + b
def sumOfOneWith(a: Int) = sum(1, a)

Notice that sumOfOne partially applies the function sum reducing its arity. This is super useful and if you take a look on the internet you will see some people using this technique as a replacement for dependency injection.

Currying

Currying is a technique that allows us to decompose a function with arity N (where N is > 1) in a chain of calls to smaller functions with arity 1. Let’s see an example:

def sumCurried = (a: Int) => (b: Int) => a + b
sumCurried(1)(1) == 2

Now sumCurried returns a function which returns another function and that last one calculates the result. Doing that we reduced the arity of sum to 1 expressing it as a smaller function. Scala automatically can curry a function using the curried function, an example of the previous version of sum:

sum _ curried

This is a sample curry implmementation:

def curry[A, B, C](f: (A, B) => C): A => (B => C) = a => b => f(a, b)

What it does, is to receive a function with arity 2 and it returns a function with arity 1 that returns another function with arity 1 and finally that function calls the given function with the needed parameters. Take some time to digest this, and if you have the chance, play around a little until you understand the concept, is a powerful technique but it takes some time to fully understand it.

We can as well, uncurry a function. It is the same concept but all the way around, so we take a function with less arity and we convert it to another with a higher arity. The dual of the previous function is:

def uncurry[A, B, C](f: A => (B => C)): (A, B) => C = (a, b) => f(a)(b)

This time it takes a function with arity 1 and it returns a function with airty 2 that finally applies those arguments to the original one.

Currying VS partial application

So, what is the difference between curry and partial application? As we stated before:

  • Partial application: Possibility to apply a function with a given set of arguments to reduce the original function arity.
  • Currying: Ability to decompose a function with arity N (where N is > 1) in a chain of calls to smaller functions with arity 1.

There is a small difference, but is important to understand the difference.

References

This books inspired me; I’ve been working with those for a while and are worth it:




Written by:

Christian Panadero Martinez