What the F# is functional programming?

I occasionally slip the term functional programming into conversation, because it brings back warm, fuzzy feelings from when I was young and into new age ideas. But from people who don’t know what functional programming is, this invariably produces a response like: “I have functions in my code, so aren’t I already doing functional programming?”

Well, no. So, I have to explain that — despite the name — functional programming doesn’t refer to programming with what-most-people-think-of-as-functions. The style of programming where your code is divided into multiple functions, procedures, methods or whatever-you-want-to-call-thems is usually referred to as procedural programming, or structured programming.

But then, having explained that functional programming is not what they think it is, I’m faced with the problem of explaining what it is. At this point, things can get confusing, because if someone’s unfamiliar with functional programming, they’re unlikely to be familiar with the fancy terms that are used to explain what functional programming is. I’m thinking terms like first-class function, pure function, higher-order function and — everyone’s favourite — the lambda calculus. If your eyes have glazed over, then you understand the problem.

Attempting to explain these concepts can be hard work, but fortunately ideas from functional programming have begun to leak into mainstream programming languages, and this provides a much easier vehicle for explaining the basics. To demonstrate this, let’s look at an example in my least favourite language, python:

numbers = [1, 2, 3, 4, 5]
squared_numbers = list(map(lambda x: x * x, numbers))
print(squared_numbers)  # Output: [1, 4, 9, 16, 25]

This code tells python to (a) create a function which takes one argument, which it’s going to multiply by itself, and then (b) apply this function to each element of a list. This causes it to generate the square of each number in the list.

The term lambda is lifted outright from functional programming, and creates an anonymous (i.e. un-named) function that can be treated like any other value. So, for instance, it can be stored in a variable, or — as in this example — passed to another function as an argument. In functional programming parlance, this is known as a first-class function, since it has the same first-class status as all the other bits-and-pieces you pass around in your code.

The term map also comes from functional programming. This is an example of something known as a higher-order function. That is, a function that takes another function as an argument, and then does something using it. In the case of map, it takes a function and applies it to each element of a list. One of the nice things about functional programming is that you can apply higher-order functions to other higher-order functions, and this provides an easy way to build up more complex behaviour. For example:

numbers = [1, 2, 3, 4, 5]
even_squared_numbers = list(filter(lambda x: x % 2 == 0, map(lambda x: x * x, numbers)))
print(even_squared_numbers)  # Output: [4, 16]

Here, the output of the previous map function becomes the input to filter, which is another higher-order function which uses the function in its first argument to decide which elements to keep from the list provided as its second argument. So, in this case, the composition of filter and map is used to produce a list of even squared numbers.

But things are looking rather messy now, and this in part reflects the fact that python is not a “proper” functional programming language. So, let’s consider what this same program would look like in Haskell, which is the most widely used¹ pure² functional programming language:

numbers = [1, 2, 3, 4, 5]

-- Define functions for filtering and squaring
isEven :: Int -> Bool
isEven x = x `mod` 2 == 0

square :: Int -> Int
square x = x * x

-- Use map to apply both functions sequentially
even_squared_numbers = filter isEven map square numbers

-- Print the result
main = putStrLn ("Even squared numbers: " ++ show even_squared_numbers)

Mmm, much neater, and you can see how these sequential function applications build up an expression (filter isEven map square) that is almost human readable. And this is one of the goals of functional programming: to make programs more descriptive and less prescriptive. That is, there’s much less emphasis on how things should be implemented at a low level, and much more emphasis on what the program is doing at a high level. For this reason, functional programming languages are also referred to as declarative languages: they declare what a program should do, not how it should do it.

This declarative approach to programming also has benefits in terms of efficiency. In particular, when you use a higher-order function like map, you don’t really care about how it implements its behaviour. Internally, map could be implemented as a simple for loop, which iterates through each element of the list and applies the function to each one in turn. Or alternatively, the function could be applied to each of the elements in parallel, farming each of these off to a separate processor in a cluster. Because you haven’t specified one or the other, the language itself can decide which is more relevant — if you only have one processor, use a for loop; if you have lots of processors, parallelise it and potentially speed things up.

And this has become particularly relevant to deep learning. Deep neural networks are basically structures in which large quantities of numbers are being pumped in parallel from the inputs to the outputs, and then back again³. Traditionally, this might have been implemented by for loops, but nowadays it’s much more common to use something called vectorization, which is basically a higher-order function approach similar to map. This means that matrix operations (the bread and butter of deep learning) can easily be executed in parallel on hardware devices such as GPUs and TPUs, without the programmer having to directly specify this. That is, the programmer just says what they want done, and the run-time environment is then free to do whatever is most efficient to achieve this.

But the fun doesn’t stop there, and pure functional programming languages such as Haskell have a host of other nice features, including the fact that their code is much easier to reason about, and therefore much easier to prove error-free. They also let you leverage type systems in interesting ways, which is something I touched upon in reverting to types.

Oh, and F# is the name of Microsoft’s functional programming language, in case you were wondering about the title of this post. Not one of Microsoft’s most successful .NET languages, but check out this advocacy site if you want to know more. It’s a good way into functional programming for anyone already invested in the .NET ecosystem.

1. At least according to the latest RedMonk rankings. Not that there’s much competition amongst pure functional languages. Some other well-known languages which are largely functional are Scala, OCaml and Clojure.

2. The term pure means that functions don’t have side effects, which is not the case in all functional programming languages. However, I’m not going to go down this particular rabbit hole.

3. At least during training.