Everywhere you turn in the programming world you see many of the same ideas: languages like Java, JavaScript, Python, C#, and C++, which make up the majority of programming jobs, all revolve around the central idea of Object-Oriented Programming (OOP). While we have OOP to thank for many of the technological advancements that the world has received in the past couple decades, it's easy to forget that there are other paradigms of programming out there that let us think in completely different ways. Functional programming is just one of these less common paradigms, but many of the ideas that it brings can completely change your views on how to write good code.
Programming languages are generally divided into a spectrum of two sides: declarative and imperative languages. The difference between these is generally described as such: declarative languages tell the computer what to do, while imperative languages tell the computer how to do it. Obviously, no languages completely fits into one side of this spectrum, but traditional Object-Oriented languages are generally considered to be more imperative than functional languages (though Ruby, for example, is much more declarative than Java or C++). One of the big ideas that separates functional languages from Object-Oriented languages on this spectrum is the idea of state: while the state of a variable can generally change in Object-Oriented code, functional code attempts to eliminate this wherever possible. One of the main goals of this is to reduce the amount of thinking required to process instructions. For example, in the code below, it can get quite hard to trace through it in your head:
This code is rather simple, but it's clear to see where a beginner could get confused (Why do we need i--? Why is it i-- instead of --i? and so forth). Even things like whether to use i < nums.size() or i <= nums.size() aren't always clear. Either way, as code gets longer, the imperative solution can often become much harder to follow. Functional programming tries to provide the opposite:
Apart from cutting down on the amount of code used, this example has another advantage. Rather than forcing you to think around state (has i been decremented yet?), you think about the "flow" of the program; the declarative nature of this code is given thanks to the elimination of state, which means that we no longer need to be particular about the order things happen in. This example is, in essence, the idea behind functional code: remove state from the program, rewrite common patterns into descriptive functions, and chain functions together to achieve the effect of changing states.
The best way to get started with functional programming is probably by learning a functional programming language, as any code you write will adhere to the patterns used in the standard libraries. While you can try writing functional Java or Python, it's much easier to try this in a language that already has the tools there to help you. In this post, I will cover the basics of functional programming using OCaml, a language that attempts to balance OOP and functional programming concepts to give the best of both worlds.
Basic Syntax
Let's start with a quick OCaml crash course. OCaml lets us use a couple basic types of data:
() (* unit - kind of like void, but you have to explicitly return () *)
true (* bool *)
-12 (* int *)
43.06 (* float *)
'a' (* char *)
"hi" (* string *)
In the above example, you can also see the syntax for comments. One cool thing about OCaml is that you can nest comments arbitrarily, so commenting out an existing comment will not result in a syntax error as it would in C-like languages.
It's usually useful to give a name to our data, so let's look at an example of that:
let myFavoriteNumber = 7 in
myFavoriteNumber * 2
The weird in keyword you see above declares the scope we are working with: everything after the in takes previous declarations as its scope. The exception to this rule is that the in is not required when outside of expressions; to put this in different terms, the first level of let declarations can basically leave out in. Here are some examples that can hopefully clear this up:
let x = 6 in (* `in` is allowed here, but not required *)
let m =
let y = x * x in (* `in` is required here *)
let z = y - (2 * x) in
z / y
OCaml is a functional language, so functions are treated as first-class data. One way of making this idea clear is that functions are declared with the same syntax as any other kind of data:
let double = fun x -> 2 * x
let addTwoNumbers x y = (* This shorthand lets you leave out the `fun`and `->` *)
x + y
You've probably noticed that the parameters of addTwoNumbers are laid out in a weird way. Because function calls are so common in functional languages, OCaml lets you write the arguments to a function by simply putting a space (no need for parentheses or commas). For example, to call the functions above we can use double 2 and addTwoNumbers 7 3 respectively. You might've also noticed that there's no return keyword. Unlike more imperative languages, OCaml simply returns the last value used in a function, because returning data is not a step in a list of instructions anymore.
When a function is recursive, we need to be up-front about it. To do this we can replace let with let rec like so:
let rec factorial n =
if n = 0 then 1 else n * factorial (n - 1)
Just to make sure that you understand what is going on here through the strange syntax, the algorithm above can be described like so:
Onto A Real Example
One place where functional programming excels is in list processing. Functional programming was pioneered by LISP (the LISt Processing language), and this influence remains clear today. For our first real example, we will write a function to count the length of a list.
OCaml lets us define lists with a simple syntax: [1; 2; 3; 4; 5]. However, this form is merely the shorthand of the "proper" syntax for lists, which makes clear the fact that these are linked lists. As a reminder, a linked list is defined as a data structure made up of nodes that hold a value and point to the next node in the list. In Java, this would look like so:
public class LinkedIntList {
int value;
LinkedIntList next;
public LinkedList(int value, LinkedIntList next) {
this.value = value;
this.next = next;
}
}
The OCaml linked list [1; 2] would then be defined as new LinkedIntList(1, newLinkedIntList(2, null));. However, OCaml also contains the syntax that shows this connection, which would rewrite the list [1; 2] as 1 :: 2 :: []. Here, the [] means the empty list (like null) and :: is the list constructor (like new LinkedIntList(...)). With this in mind, we can write now write our length function:
let rec length theList =
match theList with (* Pattern matching! *)
| [] -> 0 (* If the list is empty, its length is 0 *)
| head :: tail -> 1 + length tail (* If the list has elements, its length is equal to 1 + the length of the tail *)
This is our first example of pattern matching, so it might be weird to adjust to. Pattern matching is pretty much the most useful part of OCaml, and once you get accustomed to pattern matching you're going to miss it in every other language. The match ... with syntax is basically a switch/case on steroids: rather than checking whether the value is equal to each case, it checks whether the value matches each case. A "match" is kind of strange to think about at first, but believe me, the idea is quite intuitive.
Basically, matching lets us look at how something was constructed without giving all the details away. Since 1 :: [] is constructed with ::, it matches the patterns head :: tail, x :: [], and 1 :: tail. Notice the fact that each time this is introducing new variables (like head, tail, and x) to represent matched values; this is the idea used by the above length function. To show a simpler case, we can rewrite our previous factorial function with pattern matching syntax:
let rec factorial n =
match n with
| 0 -> 1
| n -> n * factorial (n - 1)
To bring this idea full-circle, let's take a look at how we might write the filter() function from Java in OCaml. This function is already quite popular in OCaml and exists in the standard library, but surprisingly the way it's defined is actually super simple:
let rec filter theFunction theList =
match theList with
| [] -> [] (* Nothing left to filter through *)
| head :: tail ->
if theFunction head then (* If the function we're filtering with returns true... *)
head :: filter theFunction theList (* Keep the current item and filter through the rest of the list *)
else (* Otherwise... *)
filter theFunction theList (* Skip the current value *)
This is an example of what's called a "higher-order function". The simple definition of a higher-order function is just a function that either returns another function or takes another function as an argument. The fact that we can take a function as an argument shouldn't seem groundbreaking, but this is a rather recent feature in most mainstream languages (and one that's not used as often as it should be).
Anyways, let's go ahead and translate our original Java example from the beginning of this article:
let isOdd n =
n mod 2 = 1 in
let nums = [1; 2; 3; 4; 5; 6; 7; 8] in
filter isOdd nums
However, we can even simplify this further, thanks to "anonymous functions" (functions that are never named or explicitly bound to a variable):
let nums = [1; 2; 3; 4; 5; 6; 7; 8] in
filter (fun n -> n mod 2 = 1) nums
This example should look strikingly similar to the Java code before. However, unlike in Java, most OCaml code looks a lot like this. While OCaml has for loops and lets you change the state of a variable, these features are only used as required. Instead, higher-order functions are encouraged and recursion is quite common. While these features don't fix everything, they're often nice ways to simplify writing algorithms (whether in OCaml or even your favorite OOP language). Especially with the power of pattern matching, functional-style code can become extremely concise as well as very easy to follow.
Moving on...
So now that you've taken a quick look at how things work in the functional world, you are hopefully intrigued by this style of programming and may want to learn more about it. If you're interested in learning more about OCaml, I highly recommend either checking out Real World OCaml or the Official OCaml Tutorial.
If you're already writing code in traditional object-oriented languages, I would recommend you either give Scala a try (if you prefer the JVM/Java) or F# (if you prefer C#/.NET). Both of these languages support huge amounts of libraries (including the ones you already work with!) and are very simple to transition into because they allow for both functional and object-oriented programming.
Finally, if you'd like to stick with your current language, I highly suggest looking for a book/tutorial on functional programming in that language. One great book I've read is Functional Programming in C#. This was the book that really inspired me to get into functional programming, and ever since reading it I feel as if my programming skills have improved exponentially.
If you don't understand the whole buzz with functional programming or have some questions about this post, I'd love to hear your responses. If you've already tried functional programming in the past, what were your thoughts on it?
In my understanding, OOP paradigms are inclusive of Imperative, Functional and Procedural methodologies. Behaviors of OOP objects can be coded in a way that alter the state or do not alter the state of the invoking program.
What I mean to say is that you appear to be describing OOP as something opposed to functional programming when it really is not. The OOP environment can contain procedural (state changing) and functional (non mutable state) concepts. And you do say this, but you do so with the implication that functional programming is somehow opposed to OOP.
A good example of Functional Programming in an OOP environment is F# which is a functional language purposefully encased in an OOP environment. I think (IMHO) that a better illustration of differences between programming paradigms would be procedural vs functional. :D.
Here's a link to a thesis on F# OOP programming: http://www.idt.mdh.se/kurser/DVA201/slides/oo.pdf
The rest of your thesis is on the money. Thank you for the treatise on Functional programming.
Yes, I do believe that I oversimplified this a lot. In fact, languages like Erlang take an approach much closer to OOP in their design than many "OOP" languages. The main point I was trying to get across was that instead of relying on common object relationships ("I can mutate myself/my instance variables"), you can instead write code in a more functional style. If I had written a longer version of this article I probably would have gone more in-depth on OOP vs. procedural and functional vs. imperative instead of just calling it OOP vs. imperative.
Please don't get me wrong...I enjoyed the hell out of your excellent post.
You are right that FP and OO are not opposed BUT they are very different mind sets.
While F# might run on an OO platform it is still a full FP language based on ML/OCAML (It is missing higher kinded types but that was the .NET platform that caused that limitation). MS just bolted on syntax that allows it to interact with C# and the other languages hosted on .NET
Trying to do OO in F# actually causes a lot of limitations in the language. Things as basic as the pipeline operator failing to play nice once you start using "member" variables. Things just do not compose as well :(
Functional programming is really a complete mental shift from OO. No classes, just data and functions. Oh and functions are also data.
I have written a series called Functional programming for the OO developer, currently intro and 4 parts that explores the difference in mindset of the two style for OO people.
I would suggest giving Clojure a try or even starting with Closurescript if you have a strong understanding of Javascript.
FP has seriously peeked my interest and I hope to get deeper involved with it.
I wish I was better at programming!
There is only one way to be a better programmer, doing more programming :)
The more you do and the more languages and styles you expose yourself to the better you will get.
I have lots of interests to choose from, can't do them all. Programming might come to be one of them but... I ALSO LIKE SLEEPING :)