What is a higher-order function?
This is an episode of Thoughts on Functional Programming, a podcast by Eric Normand.
Higher-order functions are used a lot in functional programming. They are functions that take other functions as arguments or return functions as return values, or both. You'll probably be familiar with map, filter, and reduce, which are higher-order functions. In this episode, we go kind of deep on them.
Eric Normand: What is a higher-order function? By the end of this episode, you should be able to identify them, understand why they're useful, and have some higher-order functions to study and learn, if you don't already know them.
My name is Eric Normand, and I help people thrive with functional programming. Higher-order functions play a big role in functional programming. You'll hear the term a lot, and we're going to learn about what the term is. They're a powerful way to abstract out functionality.
Map takes a function and an array or a list, and it returns an array of the F to function applied to all the elements of the argument. Filter takes a function, a predicate function, and a list of elements. It keeps all the ones that return true when you call the predicate on it.
Then, Reduce takes a function, an initial value, and an array, and runs the function on the initial value and each of the elements in the array, iteratively, and then returns the value at the end. These are all functions that take a function as an argument. We'll call them first-order functions.
Where does the term come from? I don't know if there's a real origin, if this is the actual origin, but the way I like to think of it is there's the notion of the order of a polynomial. A polynomial in math is some equation that's like, 4x\^2+3x+2. You could have, 7x\^3+4x\^2+3x+2.
Those are polynomials, but the order of the polynomial is the biggest exponent on the x. A third-order polynomial is going to have a three, a second order polynomial is going to have a two in the exponent. I like to look at it like that. That a zero-order function is a function that takes values, non-functions. It just takes values and returns values.
A first-order function is going to take a function. A second-order function is going to take a function that takes a function. It starts to get pretty abstract and hard to work with, but that first-order level is useful.
Why would we do this? Well, if you look at the examples of Map, Filter, and Reduce, they are basically specific use cases of for loops or recursion, perhaps, if that's how you want to implement them, that are very useful and repeated a lot.
You could write the recursion yourself, or the for loop yourself, that transforms all the elements in a list and returns that new list with the new elements. You could do that, and every time you'd write the same for loop or the same recursion over and over again.
What Map does is it lets you not repeat that for loop and talk about what's different, and that's nice. It's way less error-prone to have the thing be...The looping is done for you. All you have to do is provide this function, and the function turns out to be the body of the for loop.
Whatever you were doing inside that for loop now, you just put it in a function and you pass it in. Same with Filter. You could write the loop that goes through each element and checks it to see if it's greater than 10. If it's greater than 10, it adds it to a list. If it's not greater than 10, it ignores it.
It loops through all the things. At the end, you'll have a list of all the things in the original list that are greater than 10. What Filter lets you do is abstract that away.
You say, "I do not need to care about the for loop anymore, there's a lot of errors that I could do in the for loop. Right now, I'm just going to pass the greater than 10 in as a function," and Filter will take care of the rest. Reduce is similar. This lets us build new abstractions that help us reduce that repeated code.
Map, Filter, and Reduce are pretty universal. You'll find them in a lot of languages, in the standard libraries. Because if you've got a general purpose language, these are general purpose tools, they work very well, like in any domain.
You could have some in your domain that wouldn't make sense to be put in a general purpose languages, standard library. You can find them and you can write them yourselves. That's why we had to learn higher-order functions.
If you're using higher-order functions, you should be able to find these abstractions that can be turned into functions, and adding new features should get easier over time, because you're increasing the number of abstractions that you have at your disposal.
Each time, you should be eliminating bugs, you should be making it easier to write, things like that.
Imagine a function, a very simple function, that takes an argument and then it returns a function that always returns that argument, no matter what arguments you pass it, it's constantly. You pass a three, it will return a function that always returns three, so it's constantly three.
Now, this function that always returns three is very easy to write. You can say function return three, and you've got that. As a little construct, it might be faster to say constantly three than to write out a whole function. Depends on how verbose your language is.
That's an example of a function that takes an argument, just a number, or whatever value, and it returns a function that always returns that value. That's not so useful, but sometimes it's exactly what you need. It's exactly what you need, but the [laughs] reason it's not useful is because it's so easy to write that function yourself. It makes a good example.
Imagine another function that takes a function and returns a function that returns the opposite of it. You pass in the function, "even," so, "isEven," which says, it returns true if the number is even and false if it's not. You pass in this function, "isEven," and it returns a function basically with "not" wrapped around it.
It's a new function, but it's calling "notIsEven," so that's odd. Now, of course, this is easy to write on your own. You can easily do that. When you build up a collection of these little combinators, is what they're called, little functions that return or transform functions, return new functions, you can compose them.
You can do a thing that composes constantly with a not, with whatever you want, do it three times. There's all sorts of things you could do to transform this thing so that you're operating at this higher level. Instead of writing out the code, you're doing higher-order transformations and stuff.
You don't want to get too abstract. Sometimes it's better to just write it out, but it's possible. When you get to the next level of thinking, that's where these things actually start to become very useful. I do want to say, I sometimes see this as related to what, in the object-oriented world, people call, dependency injection.
Dependency injection often, to me, looks like it's an object's constructor that takes objects as arguments. You're passing in behavior. It's like you're passing in a function. It's a similar idea to higher-order function that's kind of higher-order objects. Objects made of other objects that get their behavior from those other objects.
Instead of referring to the objects in the global space or constructing them themselves, they allow them to be passed in.
You need first class functions for this to work. You need to be able to pass functions as arguments and return them as return values. Some common ones that you might know — Map, Filter, and Reduce. I call these the three functional tools. They're your basic tool set for doing functional data transformation.
Higher-order functions help you build new abstractions. Notice, you don't need to have a lot of the constructs of your language. Like the syntactic constructs can be rewritten in terms of higher-order functions. That's something to try.
Try to write a conditional, like a function called, "If." I know you probably can't call it "If," you can call it, "myIf," that takes a Boolean and two functions, one for the then and one for the else. Give it a shot, see if you can do it.
You can also return a function. That is something that does come in handy, but we're not going to go too deep into that. I think it's related to dependency injection.
Do give that a shot. I'll give you a little assignment. Try to write a conditional function that takes a Boolean and two other functions and decides which function to run based on that Boolean's value.
All right. My name is Eric Normand. This has been my thoughts on functional programming. You can find this episode and all other episodes at lispcast.com/podcast.
You will find video recordings, audio, and text transcripts of everything there. You'll also find links to subscribe and how to follow me on social media, how to get in touch with me. Awesome. I appreciate you being here, and rock on.