Estimate project
← All posts

Functional Programming – what is it?

What do we really mean by "programming with functions"? Let's look for an answer.

25 min read
Functional ProgrammingProgramming Languages

According to an “orthodox” definition, functional programming (FP) means programming with pure / mathematical / side-effect-free functions. Yet this is neither practical nor in line with how people actually use the term every day.

So what is functional programming? And even if we go along with that definition, what do we really mean by “programming with functions”? Let’s look for an answer.

“You know it when you see it”

Before we get to formal definitions, let’s examine a few code samples. Each time we’ll implement the same functionality in two different styles: a “functional” one and a non-functional one. From these, we’ll attempt to pin down the characteristics of a functional programming language and style.

Bonus: are you able to name every language used here?

Collections

We’ll begin with one of the most common applications of functional programming: transforming collections:

const numbers = [1, 2, 3, 4, 5, 6];

const result = numbers
  .map((num) => num * 2)
  .filter((num) => num % 3 === 0)
  .reduce((acc, num) => acc + num, 0);
const numbers = [1, 2, 3, 4, 5, 6];

let result = 0;

for (let i = 0; i < numbers.length; i++) {
  const doubled = numbers[i] * 2;
  if (doubled % 3 === 0) {
    result += doubled;
  }
}

The functionality is identical, yet the code looks totally different! The very first example already shows that FP really is a programming style in its own right, fundamentally unlike an imperative or procedural approach.

As you probably guessed, functional programming is represented by the first snippet. Which properties make this code “functional”?

To begin with, the collection is transformed declaratively: we state which operations should be applied (map, filter, reduce) rather than how to carry them out.

Next, the first snippet relies heavily on function application: the map, filter, and reduce functions are applied to certain arguments. Those arguments are themselves functions. This means we are using higher-order functions: functions parameterized by other functions.

Lastly, function composition is at work. The output of map serves as the input to filter, and the output of filter in turn serves as the input to reduce.

The imperative snippet, by contrast, relies on explicit control flow (for loops, if conditionals) and mutable data (result). Perhaps more significantly (although this may be a matter of taste), its procedural rather than declarative character means it’s not instantly clear what transformation is being applied to the input array.

Collections, continued

The second example is about transforming collections as well. Here are the snippets:

val menu: List<Meal> = if (vegetarian) {
  entireMenu.filter { meal -> meal.ingredients.all { it.plant } }
} else {
  entireMenu.filter { meal -> meal.ingredients.any { it.meat } }
}
val dietaryRestriction: (Meal) -> Boolean = if (vegetarian) {
  { m -> m.ingredients.all { it.plant } }
} else {
  { m -> m.ingredients.any { it.meat } }
}

val menu = entireMenu.filter(dietaryRestriction)

Both snippets make use of tools from the functional programming toolbox (described above). The second one, however, also defines dietaryRestriction as a value which happens to be a function.

In other words, functional languages treat functions as first-class values. You can use them like any other value: assign them to variables, pass them as arguments, or return them from functions.

The first snippet forces us to spell out the filter invocation (simple as it is) twice. The second snippet avoids this code duplication because functions can be treated as values.

Data definition

Transforming collections is one thing, but first we need some way to define the data structures that we’ll transform. Let’s consider a third example in which we build some data: a mapping from persons to addresses. On their birthday, one of the persons moves, and the mapping gets updated:

case class Person(name: String, age: Int)
case class Address(where: String, permanent: Boolean)

val chris = Person("Chris", 29)
val friends = Map(
  chris -> Address("Berlin", permanent = true),
  Person("Nicole", 36) -> Address("Paris", permanent = false)
)

val updatedFriends = friends
  .removed(chris)
  .updated(chris.copy(age = 30),
    Address("Munich", permanent = true))
class Person { String name; int age; }
class Address { String where; boolean permanent; }

Person chris = new Person("Chris", 29);
Map<Person, Address> friends = new HashMap<>();
friends.put(chris, new Address("Berlin", true));
friends.put(new Person("Nicole", 36),
  new Address("Paris", false));

chris.setAge(30);
friends.put(chris, new Address("Munich", true));

There are no higher-order functions here, nor functions used as first-class values. Even so, we’d call the first snippet “functional” and the second – “imperative”. What makes the difference?

What matters is that the 1st listing uses immutable data structures, whereas the 2nd relies on mutable ones. In the first snippet, the Map and the Address and Person classes are all immutable. Once their instances have been created, they can’t be modified. All we can do is produce updated copies of these data structures with functions like removed, updated, and copy.

Immutable data brings many advantages, particularly when data is shared between functions and processes running concurrently. When you know that a function simply cannot modify the arguments it receives, or that some data can be read safely without synchronization, reasoning about the code becomes easier.

The imperative version (second snippet) relies on mutable data structures (HashMap, classes whose fields can change). We still invoke functions to modify the data (put, setAge), but they usually return nothing meaningful (they are void, or yield () / Unit values). In other words, we invoke them solely for their side effects.

As far as programming style goes, immutable data structures have further consequences. Since copy, removed, and updated return updated values, we can (and must) rely on function composition to express successive transformations of the friends map; e.g., what removed returns is fed into updated.

Conversely, side-effecting functions that return nothing meaningful get in the way of function composition and functional programming, which become much more difficult, if possible at all. We’re forced instead to write a sequence of effectful statements.

This brings us to another characteristic of functional style: limiting the effects of functions. As shown above, we contrast effect-free functions (which we call solely to get their return value) operating on immutable collections with side-effecting functions operating on mutable collections. Reducing effects automatically lets us program in a more functional style. How far should we push this idea?

Effects

Speaking of effects: they’re everywhere. Talking to databases, issuing HTTP requests, and launching rockets are everyday tasks for a programmer. Let’s look at some code samples in that domain:

public class RocketLauncher {
  public void launch() {
    checkFuelLevel();
    initializeNavigation();
    performSystemCheck();
    igniteEngine();
    System.out.println("Success!");
  }
}
launchRocket :: IO ()
launchRocket = do
  checkFuelLevel
  initializeNavigation
  performSystemCheck
  igniteEngine
  putStrLn "Success!"
launchRocket : '{IO}
launchRocket _ =
  checkFuelLevel
  initializeNavigation
  performSystemCheck
  igniteEngine
  printLine "Success!"

Again, all three do the same thing. Reading them, we think of the code in a similar, imperative manner: “Launching a rocket means checking the fuel level first, then initializing navigation, running the system checks, and lastly igniting the engine. After that I can tell the world about one more successful launch”. So at a meta-level, all of them convey the same reasoning. At the programming level, though, they couldn’t be more different!

The first snippet is what we might call “plain old imperative programming”. Calling a function immediately triggers a sequence of (side) effects, and then we move on.

The second snippet, by contrast, models effects as values. Functions such as checkFuelLevel, initializeNavigation, etc. merely build & return values that are descriptions of computations. Modeling effects as values is a technique for writing effect-free functions.

These values are then combined into one bigger description that sequences the inner descriptions via the do-notation (syntactic sugar for calling a chain of IO.flatMap higher-order functions). Effects happen only when a top-level interpreter evaluates this description (which may happen once, many times, or not at all). As a result, defining effectful computations is decoupled from evaluating them.

We won’t go into a thorough analysis of the advantages and drawbacks of restricting effects this way, as that would require covering control monads, laziness, etc. – the Internet already covers it extensively. Suffice it to say that (some, at least) functional languages provide a means of modeling effects as values and evaluating them lazily.

Earlier, we said that functional style gains from reducing a function’s possible effects as far as possible, and here we push that to the extreme. Effects aren’t permitted at all. This radical approach pays off: we can be 100% functional. It also comes at a considerable price, though: runtime, cognitive, and syntactic overhead, given how pervasive side-effects are in real-world codebases.

The third snippet shows a kind of compromise: executing effectful computations requires an ability, which is included in the function’s type. You can view such code imperatively, with effects evaluated right away when the ability is in scope. Or you can treat every function that requires abilities as lazy and therefore effect-free, since the effects can only happen once an ability is supplied.

Composing programs

Let’s look at how larger programs can be built from smaller parts:

var order = Order.Parse(request); // might throw
order.Validate(); // might throw
order.CalculateTotal();

if (request.LoyalCustomer)
{
  order.SetLoyal(true);
  order.ApplyDiscount();
}

order.CalculateTax();

var invoice = new Invoice(order.Total, order.Tax);
parse_order request (* returns a Result *)
  |> Result.bind validate_order
  |> Result.map (fun order ->
    create_invoice
      (apply_discount (calculate_total order) request)
      (calculate_tax order))

There are two kinds of composition at play here. The first is combining order parsing and validation, either of which can fail. The first example handles this effectfully, by throwing exceptions. The second does it without effects: errors are represented as values through a Result data type (some languages use Either for the same purpose). More generally, modeling concepts as values is something you’ll often see in functional languages.

The second is combining several functions to express the invoice calculation logic. The first snippet achieves this through imperative steps (a series of statements), mutable data, and side-effecting functions.

In the second snippet, functions like apply_discount, calculate_total, etc. neither mutate data nor produce other effects; they just compute something from their inputs and return values. We rely on function composition of effect-free functions, through expressions that produce immutable data. These are exactly the characteristics we spotted when examining data definition. Clearly, this is FP.

Data & behavior

Lastly, let’s take a (brief) look at how object-oriented and functional programming relate to each other. They can live side by side (as F# and Scala show), but they sometimes answer the same question differently.

interface Shape { double area(); }

class Square implements Shape {
  private double side;
  Square(double side) { this.side = side; }

  double area() { return side * side; }
}

class Circle implements Shape {
  private double radius;
  Circle(double radius) { this.radius = radius; }

  double area() { return Math.PI * radius * radius; }
}
enum Shape {
  Square { side: f64 },
  Circle { radius: f64 },
}

fn area(shape: &Shape) -> f64 {
  match shape {
    Shape::Square { side } => side * side,
    Shape::Circle { radius } => std::f64::consts::PI * radius * radius,
  }
}

Object-oriented programming answers the question “how to handle code & data” by combining the two: that is the essence of encapsulation. Data is hidden from those using the abstraction and can be changed only through the methods the object exposes. This frequently goes together with mutability. Encapsulating data can be the correct choice, but it’s not the only one.

FP’s alternative answer is to separate data and behavior. Data structures are defined with no behavior attached (behavior is expressed through functions). Data tends to be immutable (as noted before), and most FP languages, if not all, come with built-in support for algebraic data types (ADTs) and pattern matching. In the second snippet above, Shape is an enum – a coproduct – with two variants – Square and Circle – each a struct (product) holding a single field.

ADTs offer a practical, flexible, and type-safe means of defining immutable data structures. Together with functions, they form the fundamental building blocks of functional programs.

Traits and non-traits of functional programming languages

What we’ve learned so far can be summarized as a “checklist” of traits a programming language may possess. Each of them makes a language more likely to be seen as functional, or at least makes it possible to program in a functional style. Alongside, there’s a list of non-traits that can help us recognize imperative or procedural languages:

Traits of a “functional” approach Non-traits of a “functional” style
Composing functions Imperative steps
Higher-order functions Loops, conditionals
Functions as first-class values Duplicated code
Functions free of effects Functions with side effects
Effects represented as values Effects performed immediately
Expressions Statements
Immutable data Mutable data
ADTs & pattern matching Classes, inheritance
Data & behavior kept apart Data & behavior bundled together

Having developed some intuition and covered the practical aspects – which features of programming languages are seen as “functional” – let’s move on to theory and formal definitions.

A theoretical take on FP

When trying to discover and understand what Functional Programming is, the natural first step is to look it up on Wikipedia. The article is fairly extensive, but we’ll concentrate on its opening paragraph, which contains the definition:

a paradigm in which programs are built by applying and composing functions

That’s all – and it matches what we’ve found so far. If function application & composition is to be the main tool for building programs, we’ll soon need higher-order functions and functions as first-class values. Without them, we couldn’t use this programming style effectively.

Consequently, a functional program is a tree of function applications. On one hand, this gives it a declarative feel, where we describe the “what” rather than the “how” (although the line between them is frequently fuzzy). Being declarative also means that our program’s behavior is specified without explicit control flow constructs, or at least with fewer of them. On the other hand, we end up dealing with expressions – yet another trait of functional programming that appeared in the examples.

Keep in mind that when we list “functions as first-class values” or “higher-order functions” as required language features, we mean that they come with reasonably light-weight syntax and are comfortable to use; the bare semantic ability to “hack around and define a higher-order function” isn’t enough.

But what’s a function?

The definition above has one weakness. What exactly is a function? There are two ways to look at it. One is to follow the function link on Wikipedia, which tells us that:

a function is a unit of software that can be called, has well-defined behavior, and may be invoked many times

The other is for those with a more mathematical bent. We know well that a function f: D → C is a relation in which every x ∈ D corresponds to exactly one f(x) ∈ C. Mathematical functions are deterministic and free of effects; their result is determined solely by their input. Neither the state of the world, nor the time of day, the weather, or what’s stored in the database affects a function’s result.

Which function definition we adopt determines which flavor of functional programming we end up with. Taking the computer-oriented definition, in which functions may have (side)-effects, yields what I’ll refer to as casual functional programming (a term I’ve just made up and that isn’t in common use – at least not yet).

Taking the mathematical definition yields pure functional programming, a far more widespread term, in which every function is free of effects.

Purity is an excellent and worthy goal. Still, no popular language lets us verify that a function is pure. An escape hatch always exists – Haskell has unsafePerformIO, after all. This doesn’t make the concept useless, but it may suggest that demanding purity across a whole codebase isn’t necessarily a desirable property.

Isn’t casual FP just clean code?

But – you might object – by broadening the definition into “casual FP”, we’re essentially saying we want to build programs by applying and composing callable units of software (which may have any effects). Isn’t that just programming with small functions? Something people have long promoted as part of clean code?

Yes – refactoring OO spaghetti code into small methods moves you toward FP. Clean code can be packed with FP principles.

And no – small methods alone won’t suffice if we want to compose functions more often. Their shape will also need to change dramatically: rather than mutating and causing side-effects, they should return meaningful values that can serve as inputs to other functions.

Only once we add higher-order functions, functions as 1st-class values, ADTs, immutability, an expression-oriented language, restricting (though not necessarily removing) effects etc., do we reach casual FP.

How functional a language can be considered depends on whether building programs with these FP traits is ergonomic and the main approach (rather than a secondary or merely possible one).

Where FP’s value lies

In my view, most of what the functional programming style offers comes from bridging the gap between imperative/procedural styles and casual FP. In other words, we make use of the FP traits defined above (functions as 1st-class values, higher-order functions, immutable data, limiting effects) without necessarily being very strict about them.

The next step, moving from casual FP to pure FP (effect-free functions, meaning every effect is a value), can be worthwhile, but its returns may also diminish.

Let’s look at these three examples:

var users = new ArrayList[User]()
for id <- peopleIds do
  users.add(fetchFromDb(id))

var likes = new ArrayList[Response]()
var dislikes = new ArrayList[Response]()
for user <- users do
  val response = sendRequest(user)
  if response.body.likedSciFiMovies.contains("Star Wars")
  then likes.add(response)
  else dislikes.add(response)
peopleIds
  .map(fetchFromDb)
  .map(sendRequest)
  .map(_.body.likedSciFiMovies)
  .partition(_.body
    .likedSciFiMovies
    .contains("Star Wars"))
peopleIds
  .traverse: id =>
    fetchFromDb(id)
      .flatMap(sendRequest)
  .map(_.partition(_.body
   .likedSciFiMovies
    .contains("Star Wars")))

The first one follows an imperative, mutable style full of control flow constructs such as loops. It has the side-effecting methods fetchFromDb and sendRequest. The code is “OK”, but could we improve it?

The second snippet does the same thing, refactored into casual FP. The higher-order functions map and partition express the desired transformation, and function composition chains the steps together; fetchFromDb and sendRequest remain effectful. That’s to be expected, though, considering their names and the functionality we’re building.

Lastly, the third snippet has been refactored into pure FP, with effects represented as values. As a result, composing & transforming them has to happen at the value level, adding an extra layer that shows up here as traverse and map invocations. Effects are controlled and evaluated lazily; their definitions are separated from their evaluation, yet most of the time we don’t take advantage of these capabilities.

A similar view appears in a well-known FP talk by Jane Street – to my knowledge, the largest commercial OCaml user and active members of the FP community. The talk “Why FP doesn’t matter” begins by presenting some of the ideas discussed above and then describes the features that make FP matter for Jane Street:

  1. Correctness: expressive static types and ADTs let you make illegal states unrepresentable
  2. Dexterity: no boilerplate, static type checking, e.g. exhaustiveness checks when data types evolve
  3. Performance: compiling high-level OCaml code to machine code is predictable and fairly easy to reason about

Purity and laziness sit near the bottom of the list – handy now and then, but not essential parts of functional programming.

To wrap up the discussion of whether purity matters, I think we should remember that shared mutable state will always exist. I wholeheartedly agree that removing it from a program’s in-memory state is good practice that all of us should aim for, regardless of our favorite programming style. But think of a program running two processes at the same time:

// thread 1
writeToDatabase(user.copy(age = user.age + 1))

// thread 2
readFromDatabase(userId)

No matter how we represent these effectful functions – with a monad, immediate effects, or abilities – when reading the code we must still bear in mind that running it will mutate some global mutable state (here, in the database).

The state our code operates on isn’t limited to what lives in memory, like global variables. (Which, again, we should steer clear of! Don’t make life harder than necessary.) There’s also the database, the filesystem, and countless external services, where every POST/PUT call mutates the broadly understood “state of the world” that the service we’re building belongs to.

You can’t avoid mutating global state – sorry!

Other definitions of FP

Unsurprisingly, plenty of other FP definitions float around online. Since AI is taking over anyway, let’s hear what it thinks:

ChatGPT emphasizes purity, immutability, and higher-order functions, which closely matches what we’ve found. Perhaps purity will drop down the list once this article makes it into the training set; time will tell!

And StackOverflow? Several related questions exist, but let’s look at the one about FP versus non-FP programming. Unsurprisingly, the accepted answer mentions functions as first-class values and immutability.

Another answer aligns with the casual vs. pure distinction we drew earlier. If that answer is historically accurate, casual FP came first and was only later overtaken by Haskell’s focus on purity!

Speaking of history, we can’t skip the paper Why Functional Programming Matters by John Hughes – most likely regarded as a classic by now. At first sight, the definition the paper uses mentions only function composition & application:

Reading further, though, it becomes evident that the paper’s functions are the mathematical kind. So no side-effects and no mutation: pure FP. The paper introduces higher-order functions and laziness as two new kinds of “glue” for writing modular programs, likening this to how structured programming improved upon gotos. We’ve in fact already touched on John’s paper indirectly, when discussing the Jane Street talk, which agrees with the paper’s thesis only in part.

Lastly, what does the front page of the Internet – Reddit – say? There are indeed several threads, such as What even is FP and why do we like it? (do we?). The subreddit has no memes, but one answer appeals to me in particular:

It highlights the ergonomic and community side of a functional language: you can not only do everything functionally, but that’s also the recommended approach, in keeping with the spirit of the language.

Other highly upvoted answers do lean toward pure FP:

What is FP, then?

Let’s try to condense our findings into as compact a definition of FP as we can:

Functional programming is an approach where a program’s logic is expressed mainly through function composition. Here, a function is code with a well-defined interface that can be called repeatedly. Functional programming frequently relies on the tools and techniques below, though not always all of them, nor all the time:

  • Functions treated as 1st-class values
  • Higher-order functions
  • Preferring expressions to statements
  • Immutable data structures
  • Algebraic Data Types & pattern matching
  • Representing effects as values
  • Steering clear of shared mutable state
  • Avoiding effects or keeping them limited
  • Keeping behavior & data separate

A functional programming language is one that makes functional programming ergonomic, as reflected in its standard library, external libraries, and documentation. A language counts as functional only when FP is the dominant way of building programs. FP has to belong to the spirit of the language, not merely be technically feasible.

Regarding these tools & techniques, it’s worth asking whether they are desirable features of a programming language, and to what extent. How functional should our languages be?

Some of them are uncontroversial and broadly recognized as helpful; others are debatable. None of them is a silver bullet. Each deserves its own article, and the Internet already has plenty of those, so we’ll leave it there.

FP won’t magically make your code better across the board. Frequently it will, but not in every case. Functionally written code tends to be safer, easier to read, more concise, etc. Naturally, in some use-cases it can also be worse, and the imperative, mutable version may prove easier to maintain.

How functional are the languages we use & love?

Based on the characteristics above, let’s attempt a “functionality scorecard”: a subjective, hand-wavy rating of “how FP” several popular languages are. So yes, take these with a grain of salt, and feel free to tweak the scores to correct any mistakes of mine.

The scoring categories match the characteristics defined earlier, plus one extra category for “how functional the standard library is”, meant to capture whether FP is the style the language was built for or merely an option.

Below is the table, linked to a Google Sheet you can copy and modify as you like:

The languages are a mix, and some of them appeared in the code snippets above. Let’s start with Java. Your first association is probably object-oriented rather than functional programming, and with good reason. You can represent functions as values and write in a functional style if you choose, but the language and standard library will push back. Java’s standard collections are mutable, and the whole Java ecosystem rests on mutable data structures that encapsulate data inside objects. The recently added records and pattern matching nudge the language toward FP, but FP will never stand on equal footing with OO, imperative, or procedural styles in it.

And Kotlin? It solves many of Java’s issues, beginning with syntax, and also provides tools for building immutable data structures. You can write FP-style code with it; still, Kotlin remains deeply rooted in Java’s ecosystem. Its standard library collections aren’t immutable, and libraries frequently feel Java-like. This gives superb interop with Java, but also means some of Java’s problems remain unsolved.

Staying on the JVM, there’s Scala, a language intended as a hybrid of OO and FP. As Scala is the language I use most, I’ve split it into the two flavors in use today: the direct-style one, which matches casual FP, and a pure-FP one. Scala’s standard library is fully functional and provides immutable data structures by default. This strongly shapes how Scala libraries are written. Avoiding mutable shared state and constraining effects are common practice in Scala, but they still depend on discipline – the compiler doesn’t check them.

Next comes “the” FP language: Haskell. It checks almost every box, providing pure FP where effects can be defined only via the IO monad. Escape hatches still exist (in the form of the unsafePerformIO function, which is unsafe by definition). Haskell experiments with many interesting programming ideas, which is both a blessing and a curse: it’s known for its numerous compiler extensions, which effectively produce many different flavors of Haskell. Thanks to this, however, FP frequently gets pushed to new frontiers.

Lastly, there’s an apparently unlikely candidate: Rust. Can Rust be regarded as a functional programming language at all? As it turns out, yes – it scores quite high on our scorecard. So either Rust really is functional, or our scorecard is flawed. Let’s look more closely, though: functions are first-class values; data is modeled by default with enums and structs (= ADTs); preventing shared-mutable-state is among Rust’s main design goals. Rust gets there with different tools (ownership tracking rather than immutability), but the result isn’t all that different. You’ll sometimes wrestle with the borrow checker, but in return you get raw performance and more predictable memory usage.

Ranking of languages

Certain languages are clearly functional: Haskell, Scala, F#, and OCaml belong here (note that only in Haskell is it the “default” that every function is pure & effects are represented as values). Certain languages are clearly not functional: Java and C# are textbook examples. Most land somewhere in the middle, like Kotlin and Rust. Bear in mind that “how FP our code is” should never be the ultimate goal; it’s simply a set of tools that combine well to help us build better software.

Most of our code will blend styles, sometimes even inside one function, and that’s perfectly fine.

Concluding

Functional programming isn’t going anywhere. It hasn’t conquered the world, but many popular programming languages today have adopted at least some of its ideas. It’s worth recognizing them correctly and understanding how FP is applied in practice. As the code samples in the first section showed, FP is a broader term than just programming with pure functions.

We’ve examined Haskell, Rust, Scala, Java, and Kotlin in detail. But there are also C#, TypeScript, JavaScript, Python, Ruby, and many more – each with at least some functional features, not to mention functional-first languages like F# or OCaml. All of them are used in production every day to ship working software. Functional programming lets us do that with more confidence and efficiency.

What counts in FP are the basics: comfortable syntax for treating functions as first-class values, higher-order functions, immutable data structures, ADTs, and a functional standard library. This is why most of FP’s value is found in the “casual” variant, which makes it available to a wide audience.

If your language makes FP the most ergonomic and practical style, embracing it across the language, standard library, and community – wonderful! If it doesn’t, functional programming can still bring substantial value.