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, Let’s take one step further with higher-order functions

Higher-order functions

The idea behind higher-order functions is that functions are values, hence functions can be passed around as we do with Integers, Strings, etc… Functions that accept other functions as arguments or return functions are called higher-order functions.
An example of a really common higher order function is map, its definition in Scala’s List class is:
[crayon-5beb39f263d9d343580207/]
The meaning of map is to apply a transformation to every element of the List and returning 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, that is, functions are first class functions. So when we refer to a programming language, we say that the language supports first class citizens but if we refer to a function, we say that the function is a first class function.
One of the convenient usages of higher-order functions is to create inline functions, which we call anonymous functions or function literals. One example using the previously defined map, could be this:
[crayon-5beb39f263dad349015825/]
As you can see, the function i => i + 1 is passed in as an argument of the map function.

Partial application

Partial application means that for a function that accepts a number of arguments, N, we can fix or bind some of its arguments that it takes to reduce the arity of the function. Consider these two functions:
[crayon-5beb39f263db3506525551/]
Notice that sumOfOne partially applies the function sum reducing its arity to 1. 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:
[crayon-5beb39f263db9182612118/]
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 can automatically curry a function using the curried function, an example of the previous version of sum:
[crayon-5beb39f263dbf769576188/]
This is a sample curry implementation:
[crayon-5beb39f263dc4470527982/]
What it does, is to receive a function with arity 2 and return a function with arity 1 that returns another function with arity 1, and finally that function calls the given function with the required parameters. Take some time to digest this, and if you have the chance, play around a little until you understand the concept. It 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:
[crayon-5beb39f263dca266423526/]
This time it takes a function with arity 1 and it returns a function with arity 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:

  • Currying: Ability to decompose a function with arity N (where N is > 1) in a chain of calls to smaller functions with arity 1
  • Partial application: Possibility to apply a function with a given set of arguments to reduce the original function arity. A requirement to do partial application is that the function is already curried so that we can apply arguments one by one

This is an example of how to apply currying to a binary function:
[crayon-5beb39f263dd0040920300/]
This is an example of how to partially apply a curried function:
[crayon-5beb39f263dd6650372035/]
There is a small difference, but is important to understand it.

References

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






Did you like this post? You can support my work and help me writting more useful posts:

BTC address: 3Az7sgCW4VaNqxmTpWcZvoFDDEkqJnv8ba