Lately my interest in functional programming has been growing and growing. The only thing I like more than learning is teaching, so I decided to start a blog series on FP. I thought long and hard about the best place to start (lambda calculus, mathematical functions, algebra basics, etc.) and ultimately I decided to think back to what originally got me interested in functional programming and start from there. I am excited to get to the deeper and “cooler” stuff, but I thought it would be fun to revisit my history with FP and kick off this series with what started it all (for me): higher-order functions!
Ok, enough back-story. Lets get to the technical stuff.
What is a higher-order function? Simply, it is a function that either takes another function in as one of its arguments, or returns a function as a result (or both). A great example from calculus would be the integral and derivative operators. When you differentiate or integrate, you are applying the derivative or integral “operator” to some other function. If we use more of a programming vocabulary, we might say you pass the function you want to derive to the derivative function, and it will return that function’s derivative (another function). If you haven’t studied calculus, don’t worry, we will look at some non-math examples.
Lets start with a simple text cipher. Today I’m feeling Python for my language of choice.
This is a simple Caesar Cipher. We shift each character over some amount according to a key. Shifting “abcd” by the key 7 results in “hijk”. Shifting “a” by 1 would give us “b”. The modulus 126 is for wrapping around the 127 ascii values. Since ascii starts at 0, we don’t want to go over 126. The if statements are just so we only mess with printable characters. Check out an ascii table if you aren’t familiar.
So we have this cool encrypt function we are using to encrypt text. It nice and all, but Caesar ciphers are a little boring. Lets create another encrypt function!
This is a simple XOR cipher. It takes in a string as a key and XORs each character we are encrypting with the corresponding character from the key. Once again we can get back the original by applying the encryption again. This time instead of using the negative of the key (to shift backwards in the Caesar cipher), we just use the exact same key again. Read more about XOR encryption if you are interested in how this works.
Where are the higher-order functions? Now that we have 2 different (but similar!) functions, we can abstract out the common pieces, and pass in the differing pieces as a function. Lets see it in action.
Now we have a function called “encrypt” that takes in a string and a key as before, but now it additionally takes in a function. This 3rd parameter, the function, is what defines the encryption algorithm to use. Read over the body of the function, and you will see it essentially just loops over the string and applies the encryption algorithm (the 3rd parameter) to each letter in the string, passing in the ascii value, the index we are on, and the key passed to encrypt.
Next we have our 2 encryption algorithms. In both cases, I pretty much just copy/pasted out the important chunk of code from our earlier versions of these functions. They each take in a character code, an index, and a key. All they do is apply their algorithm on that letter and return the new letter. Simple!
Hopefully you see the power of this abstraction technique. We were able to factor out common code and create a more general function. Think about how easy it would be to create a new encryption function. All we would need to do is write a function that obeys the interface of:
And then we could call it like this:
Pretty powerful! The more you start using these the more you will see opportunities to DRY up your code and create powerful more general functions.
Lastly lets take a look at the other kind of higher-order function: a function that returns another function. We can build off of our encryption functions for simplicity.
“encrypt_factory” is the interesting thing here. It not only takes a function as an argument, but it returns a function as well. Notice how we supply encrypt_factory with the encryption algorithm, and it gives us a new function that we can call. This is convenient because now we don’t have to call encrypt and pass an encryption function every time. Now we just pass in the encryption function once to encrypt_factory, and it spits out a custom made encryption function based on the algorithm we handed it. Don’t worry about it if the one-liner with the lambda and the list comprehension is hard to understand. It is essentially doing what we were doing before: looping over a string and calling the encryption function on each character code. Except this time we are returning the function itself (hence the lambda).
Functional programming is more than an academic framework for mathematically-based software construction. It is also a toolkit of abstractions and concepts that can be pulled out and used in almost any language. So even if you don’t buy the whole FP thing, you should at least start using some of the abstractions (such as higher-order functions!) if you aren’t already.
To wrap things up, we saw how to factor out repeated code using higher-order functions, how higher-order functions can create more general and reusable functions, and how you can use higher-order functions as factories to generate new functions.