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?