Higher order functions, what are they?

In mathematics and computer science, a higher-order function (also functional, functional form or functor; not to be confused with the functor concept in category theory) is a function that does at least one of the following:

1. takes one or more functions as arguments,

2. returns a function as its result.

That is the formal definition, but what really are they and why do we need them?

Sometimes, it is important to execute some kind of operation on the items of a dataset, but this particular operation is defined at execution time. Sometimes there is just no way to know what action we want to take except that we need to do something at some particular point, but it is completely unknown.

Let’s see an example.

let x = [1..100]

for each item in x doprint(item)

Here, we are printing the each number in the list x by calling the function print. What about if we need to do something else with each item? Do we need to implement all possible cases that we think we will use?

Let’s define a function that will be called for each number (item) in x.

let succ (x) -> x + 1

We have defined the successor function which basically gets a value and returns its successor. The domain of succ is the Int numbers and that can be inferred from the body of succ since we are adding 1 to the argument and we say that succ has type Int -> Int.

Now, let’s review the previous example.

let map (f, list) =for each item in list dof(item)

Here, map is a higher order function because it received a function f as an argument, which will be executed on each item from list. At the moment we define map we don’t need to know what will be the value of f, except that f as type Int -> Some. There is no way to infer the return value of f from the previous code, but we know it has to receive an Int.

Another example will be a function that returns another function. Let’s review it.

let plus2 (x) =let succ (y) = y + 1

succ (succ x)  

let r = plus2 (1)

In this case plus2 is a function of type Int -> Int -> Int or Int -> (Int -> Int). It basically takes an Int and returns a function that takes another Int and returns an Int. r will be equals 3 after evaluation.

Now that we have shown how these kinds of functions are, let’s see how modern programming languages define them.

In Scala we can define a map function of type (a -> b, List[a]) -> List[b] as follow:

def map[a,b](f: a => b, v: List[a]): List[b] = {for ( i <- v )yield f(i)}

val squares = map( (x: Int) => x * x, 1.to(100).toList )

For each i in v we apply the function f and return its value. The variable squares will have the squares values of the numbers from 1 to 100. Please note that we are defining the squared function at the moment we call map, so map doesn’t know anything about the function f. We can easily say:

def succ (x: Int): Int = x + 1

val successors = map(succ, 1.to(100).toList)

We just changed the function passed to map and we get a completed different result. This level of abstraction is what makes map, as a higher order function, very powerful.

Even programming languages that are not functional, such as C#, have added these abstractions so they can be flexible to many use cases.

In C# we need to implement a delegate in order to get the same functionality, but it brings the same value to the language. Because higher or functions are so important, the .NET Framework has some delegates already implemented, so let’s use them

List<b> map<a>(Func<a,b> f, List<a> list){foreach (a x in list){yield return f(x);}}

var successors = map(x => x + 1, someIntList);

We have achieved the same functionality of the map in Scala. The only different is that C# does not have higher order functions and it has to use the delegates constructs, yet we get the same functionality as result. Note that in C# there is no need to declare the type of the arguments of the succ function when we pass it to map, C# infers it!

In F# is where it gets very interesting because the language support to the functional programming (FP) paradigm. In F# we do:

let map f = function|[] ->[]|h::t -> (f h) @ (t |> map f)

let successors = [1..100] |> map (fun x -> x + 1)

Seems complicated, but it is in fact the same map we saw previously. The only additions are the functional programming style and the tail recursion, typical of functional programming languages. The pipe |> operator is just a language construct, we might say instead map f t or map (fun x -> x + 1) [1..100]. Note that the type inference system works quite nice in F#. We have not defined any types; however, map is inferred to receive a function and a list and returns a transformed list.

The function plus2 in F# will be as follow:

let plus2 x =let succ y = y + 1succ succ y

For some people, higher order functions are common in their lives. These functions are built in within many languages and frameworks; still, I have seen some confusion around them. Languages that do not support them need to find alternatives that sometimes are not easy to use and implement. The C language uses pointers to functions, C# uses delegates and others use objects as substitutes. On the other hand, there are those that support higher order function out of the box. Scala, Python, and F# are just a few examples.

Even though sometimes we use these functions without thinking much about them, we should be aware of how they are implemented so we can benefit even more from them. Those who are new to this programming construct we inherited from the lambda calculus should study them and get familiar around them since the trend of functional programming seems to be gaining some battles. Higher order functions are some of the pillars of the FP languages and that seems to be the future.

Hacker Noon is how hackers start their afternoons. We’re a part of the @AMIfamily. We are now accepting submissions and happy to discuss advertising &sponsorship opportunities.

To learn more, read our about page, like/message us on Facebook, or simply, tweet/DM @HackerNoon.

If you enjoyed this story, we recommend reading our latest tech stories and trending tech stories. Until next time, don’t take the realities of the world for granted!