Recently, I have attempted to learn functional programming (FP). I have by no means mastered this approach but I thought it would be useful to discuss my experience up until now. That way I can take stock of what I have learned, consider where I can improve, and offer the reader some ideas on where to start.
Remember that I am still learning this material so there might be some errors in how I’ve described the material here. If in doubt double check.
Functional Programming is by no means a new idea, at least in academia it has been a widely discussed topic for decades. However, I think most would agree that it has been overshadowed by object-oriented programming (OOP) for some time. Having said that, in recent years there has been something of an upswing in its adoption. For instance, I believe React bears some influence from FP.
Indeed many languages that were not initially designed for functional programming do allow for it. You can code C++ in a functional way1 and JavaScript has a few libraries - such as Ramda and Lodash - that let you access functional features.
But you can also experience functional programming through languages that are designed specifically for FP.
Perhaps the well-known, although not necessarily used, language in this category is Haskell. I’ve not tried it out much myself, it seems popular among academics and has perhaps the most complete functional features. There are also some good learning resources: Learn You a Haskell for Great Good!.
Two choices with slightly less steep learning curves are:
I don’t really have much experience with Clojure, but I know that it has a very active community2. Scala, I’m more familiar with having used it already in a couple of projects. One nice feature of Scala is that you can write it either either a functional or OO way.
So having evaluated some language options, the next question is: “How do I write functional programmes?”
A good starting point is the concept of purity. Essentially this means that once a value has been assigned to a variable it can no longer change. This means there are no unexpected side effects in your code i.e. values changing in unexpected ways due to how the programme is structured.
This contrasts with typical object-oriented programming where variables can mutate. Essentially this means, that the variable is reassigned as the programme executes. For instance, the following Python code is written in an OO style. It counts the number of occurrences of ‘a’ in a string.
x
test_seq = "abracabra"
test_letter = "a"
def count_letter(val_seq, val_letter):
counter = 0
x = 0
while x < len(val_seq):
if val_seq[x] == val_letter:
counter += 1
x += 1
else:
x += 1
return counter
count_letter(test_seq, test_letter)This script mutates both the counter variable and x. It works by comparing the integer value of x with the length of the string val_seq. The programme will add a value of 1 to x until it equals the length of the string.
As this occurs, the value of x is compared with the index value of val_seq with the target value val_letter. Each time there is a match, the value of counter is increased by one and the value of x is increased by one. When there is no match x increases by a value of one only.
When the programme is complete i.e. the value of x is equal to the length of the string, the value of the counter is returned. This should be equivalent to the number of occurrences of the target value in the string.
This procedure of reassigning values to x and `counter’ is not permitted in a functional style since you are changing the original value. So how would you rewrite this simple programme without mutating the state?
In the interests of brevity, I will just show you a successful Scala implementation of the Python code now and discuss how it compares:
import scala.compiletime.ops.string
import scala.annotation.tailrec
val test_seq: String = "abracabra"
val test_letter: Char = 'a'
def stringToChars(str: String): List[Char] = {
@tailrec
def helper(s: String, acc: List[Char]): List[Char] = {
if (s.isEmpty) acc.reverse // We reverse at the end because prepending is more efficient than appending
else helper(s.tail, s.head :: acc)
}
helper(str, List())
}
val result = stringToChars(test_seq)
val occurrences: Int = result.count(_ == test_letter)
println(s"The character '$test_letter' appears $occurrences times.")
Immediately it’s obvious that this code is quite different from the Python version.
It’s also worth noting that it uses some tricks found in Scala, but these are broadly applicable to functional programming styles.
One thing I initially found challenging about reading Scala code is that typically variables include a type declaration. Type declaration is technically also a feature of Python, but I’ve not seen it used all that much.
With the Scala code, you may also note that the variables are defined with the term val. Prefixing a function with this term means you cannot reassign a val to a different value in the scope of the programme.
So we can’t index through the string as we did in the Python code. Instead, here we convert the string into a list of individual characters first. The interesting point here is that it is done via a feature called tail recursion.
This took me some time to get my head around, particularly the role of the accumulator in the code. I find it best to imagine what’s going on visually.
Initially, the function takes a string and returns a list of characters. Within the function another function (helper) takes a plus a list of characters, it will return a list of characters.
This function takes a string and splits it into a head element, the first element, and a tail, the remaining element.
Each time through the function adds splits the string into a head and tail until there is no character left. Meanwhile, the head element is prepended to the accumulator.
What I struggled with here was it seemed like the accumulator was being mutated each time, in a similar way to x and the counter in the Python code. However, that is not correct.
For one thing, the initial string remains the same even after the function runs and it’s not so much that the function takes an existing acc variable and changes it, but rather each time the function is recursively called it creates a head and tail. I suppose you might think of it as a clever card trick. A process is going on in front of us but we can’t observe it if the trick is working.
With this function in place, the code then creates a variable containing the list of characters: result. This brings us to another interesting feature that is present in many functional languages: pattern matching.
The variable occurrences contain this snippet of code (_ == test_letter). The underscore is what you might call a wildcard. Essentially anything passed into it will be compared with test_letter, which is a in this case. The method count then counts the number of characters that match the pattern.
And with that, we have a programme that replicates the Python code but is written in a functional style. In some ways, it might seem more verbose, and in this simple case, it might not make such a difference which style you choose. The advantages of FP become clearer in more complex programmes, where variables are passed around, which can result in unexpected mutations.
Really the examples given so far are just scratching the surface. There is a lot more you can do with functional programming. But we are starting to reach the edges of my understanding here. In closing, I’ll mention a few topics that I find quite interesting but don’t yet feel confident enough to give some concrete examples.
One potential application of functional programming is to manage the complexity of multi-threaded processing. This can be done in a much more straightforward manner than with object-oriented programming.
As I understand the concept, the idea of multi-threading is structuring a programme in such a way that elements of it are computed simultaneously. This can lead to improved performance.
With our coding example, one way you might think about writing a multithreaded version of the programme is to split the string into half and repeat this instruction on both halves and again on the quarters until ultimately we have single characters, which we can check against the target letter.
Admittedly using multithreading to more efficiently execute this programme is overkill. But in showing you how to use it in this simple example it becomes clear how you could use it in a more advanced one.
The challenge here is to ensure that the programme is truly multi-threaded. For instance, since Scala implements code from left to right, a programme might execute the recursion on only the left-most values to begin with and then move right. This is essentially linear.
The way I like to think about it is setting up a series of mouse traps, which is a linear operation, but this doesn’t matter because you can set them all off at once simultaneously.
Unfortunately, I’ve not yet been able to work out how to write this in Scala.
With FP you can approach testing from a different standpoint due to the imperative to purity.
Since we can be certain that a given input will produce a corresponding output, we use property base testing. This means rather than running a programme and observing the results, we can predefine conditions that will prove the programme is correct. A simple example might be something like the reverse of a reversed string should be the same string as the original value.
This is where things get even more out there. Category Theory3 is a branch of Mathematics that, as far as I can tell, essentially considers the relationship between mathematical elements. In a sense, it is attempting to describe what mathematics is at a fundamental level.
Curiously, certain topics in Category Theory, things such as monads, monoids, and functors become applicable to coding when we use FP. I’m still working on understanding what exactly these structures mean in the context of programming. But from what I can tell it is possible to apply these properties to programming and the results are quite useful.
For instance, I believe monads offer a way to manage state4.
I am definitely on board with learning more about FP, but I have encountered some sources that are sceptical towards certain aspects.
Of course functional programming might seem rather strange if you’re only fimiliar with OO technical, but this is not the kind of scepticism I mean. Instead, I refer people who take a more nuanced view. For instance, Sean Parent’s new Val language borrows certain elements from Functional Programming but has a way to allow mutation in some specific ways.
As for upcoming projects. At least in the short term, I’d like to do a bit more with hardware. So keep an eye out for an update on that.
Learning FP by William Samuel McDonald is licensed under CC BY 4.0