What is functional programming?

Posted on November 14, 2017
Tags: Haskell, FP

I’ve already1 attempted to define functional programming (FP), but I wasn’t satified with it. Kris Jenkins did a much better job, and wrote a couple of very good posts on this:

  1. What Is Functional Programming?
  2. Which Programming Languages Are Functional?

But recently I’ve come across the definition of Graham Hutton in his book2, “Programming in Haskell” (second edition, 2016).

Programming in Haskell cover

And something clicked. I really like it since it’s concise and other things (like purity and immutability) are consequences. Here it is, slightly modified3:

A function is a mapping between one or more arguments and a single result. It’s defined using an equation that gives a name to the arguments and a body that specifies how the result is calculated in terms of the arguments.

For example:

double x = x + x


I’ve emphasized some keywords that highlights the central idea: a function is defined by an equation that specifies (describe) how the result is calculated in terms of the arguments. By this definition we can derive some important properties:

What other languages call functions4, by this definition are really other things: procedures or methods.

So, what is FP? It’s just programming with functions :)

Substitution model

Another interesting consequence of that definition, is the substitution model:

When a function is applied to some values, the result is obtained by substituting those values in the body of the function in place of the argument names.

The result of this substitution and evaluation can sometimes be a single result, but often a function is defined in terms of other functions. In that case, we can continue to perform substitutions until we can reduce the whole program to a final result5. In other words, every program che be represented by a single equation.

When programs are defined this way, they are easier (for both programs and humans) to understand, reason about and manipulate. And we are not talking about a type system6 yet!

Another way to look at purity that follows from this substitution model, is referential transparency. It has been defined by Rúnar Bjarnason as follows:

An expression e is referentially transparent if for all programs p, every occurrence of e in p can be replaced with the result of evaluating e without changing the result of evaluating p.

A function f is pure if the expression f(x) is referentially transparent for all referentially transparent x.

This may seem obscure, pedantic and/or irrelevant, but it’s something profoundly practical and with deep ramifications.

BTW, this is also the reason why “mostly functional” programming doesn’t work.

  1. Warning: post in Italian!

  2. Which I’m studying.

  3. For example, a function doesn’t really need a name (see lambdas).

  4. Don’t get me started on “functors” in C++!

  5. If it terminates.

  6. Which I consider another “secret” weapon by the way.