What Is Functional Programming?

“One pervasive feature of all functional programs is recursion”

Simon Peyton Jones, 1987

Functional programming is an enigmatic niche of the computer science world.

As programmers, we’re generally content to agree that it exists, and yet, as though it were some incomprehensible phenomenon of nature, should you press for an explanation as to what this concept really means, you might only receive anecdotal replies.

Most will tell you that it’s “just another paradigm”.

A few might cite you cryptic parables concerning the Lambda Calculus - a little closer to the truth, but this still doesn’t explain functional programming meaningfully.

With a plethora of established functional languages out there, there must be a reason why functional programming was born beyond the whims of paradigmatic uniqueness and datofunctional fluidity.

So, read on as we explore what it really means for a language to be functional, why functional languages exist at all, and what that says about some very popular languages that may not be as functional as they claim to be.

A Three-Course Comprehension

I personally believed I had understood functional programming on three separate occasions, each an improvement from the last.

First was when I started to code. I was just getting into the world of programming and computer science, and I was gaining an awareness of the many different programming paradigms in existence.

Next was when I started my first functional language. This was a first-hand experience, but may have been more misleading than one would expect.

And lastly was when I finally studied functional programming at university.

Just Another Paradigm

I’ve long felt that I would eventually learn functional programming.

In the days when I moved from procedural languages to my first object-oriented language, I thought that functional languages would be a similar step forwards - that functional was to object-oriented as object-oriented was to procedural, and that each successive style built on the last.

My initial assumption about the concept was that functional programming was ‘Just Another Paradigm’. While this belief alone is not wrong, it doesn’t offer any insight into why and how it’s played such a meaningful role in computer science history, and it certainly isn’t enough to motivate the average programmer to dig any deeper.

And yet, learning that functional programming represents more than what you had previously assumed is, somewhat ironically, a necessary step in solidifying the concept in your mind.

Unlike imperative languages, functional languages are considered to be declarative. Where “imperative languages are concerned with giving instructions to a computer”, functional programs are instead focused on “describing a solution to a problem” (Clack et al.). It might not be immediately clear why describing a solution and giving instructions are different approaches, but trust me that different they are. More on this later.

Functional languages stand apart from both object-oriented and procedural languages. Their underlying implementations follow a completely different motivation, and it's this very motivation that necessitates the language features that brought about my second understanding: constants and higher-order functions.

Constants and Higher-order Functions

When I started learning my first functional language (Scala) in 2025, I had already solidified a basic idea that functional programs used constants, treated functions as first-class citizens (whatever that meant), and presumably used a lot of functions.

By then I had already encountered several features of functional languages that had permeated into other languages like C# and JavaScript. I had seen anonymous functions and various implementations of lambda expressions, and I’d started to make frequent use of the .map() and .reduce() methods from which, in a bid to pipeline data more succinctly, I ended up with a fascination for method chaining.

val solution = input
	.split("\r?\n")
	.filter(_.trim.nonEmpty)
	.map { line =>
		val (left, right) = line.splitAt(line.length/2)
		val c = left.intersect(right).head
		if (c.isUpper) (c & 31) + 26 else (c & 31)
	}
	.sum

But even through learning Scala I didn’t fully grasp what functional programming actually meant. Constants and higher-order functions are useful, sure, but they are not exclusive to languages like Haskell, Miranda, and Scala. There are a myriad of non-functional languages that have these features, too.

My second assumption was that functional programming was just coding with lots of dedicated functions and no mutable state, but this didn’t really answer why these languages were built this way.

Even after Scala helped me learn to program without the use of variables, I still had one burning question - what could possibly be the advantage of designing a language like this? And this is what leads us to my third and current understanding of functional programming.

There is a method to this madness.

A Child of the Church

Functional programming should not be thought of as another paradigm so much as an entire mindset shift. These design choices - that some would consider constraints - are very much intentional, and are very much advantageous. Functional programming is not merely another paradigm, and neither is it an amalgam of immutability and first-class functions.

Functional programming was not made to improve data safety or let you write more efficient code.

No, such magnificent strengths are little more than byproducts of a much more beautiful truth:

Functional programming is the application of the Lambda Calculus.

Procedural and object-oriented codebases both define different ways to structure programs, but they ultimately adhere to the same principles: their syntax reflects a clear correspondence to individual machine instructions; and the programmer must control memory allocation manually. You may not even notice that you’re managing memory allocation, but every time you change a variable or make use of a loop, you’re doing exactly that. All languages of this nature can be thought of as implementations of Turing Machines.

Yet Turing Machines are not the only way to do computation.

In the 1930s, American mathematician Alonzo Church developed the lambda calculus, a syntax built of only three terms that was “sufficiently powerful to express all functional programs” (Peyton Jones, 1987). By extension, it could compute anything computable; it was Turing Complete.

The core notion here is that a functional program can be represented as a single, potentially enormous expression, and that this expression can be reduced all the way down into a final result.. Those concepts of immutability and first-class functions are nothing more than a prerequisite to be able to implement the lambda calculus in code.

Lambda expressions can be reduced in any of four ways, known as reductions. Evaluation can then proceed “by repeatedly selecting a reducible expression (or redex) and reducing it.” (Peyton Jones, 1987).

The three terms of the syntax of the lambda calculus are enough to express anything you could envisage in imperative programming. In fact, you don’t even need three terms to do this.

And so it is this truth, that a functional language is one whose runtime evaluates code through reducing expressions, that underpins functional programming.

On The Imperative and The Declarative

Having defined functional programming, let’s explore what we really mean when we say a language is declarative.

First, a recap of how imperative languages handle iteration with loops. In languages like C#, loops are written with three components: the initialised iterator; the condition; and the incrementation of the iterator.

For the iterator to change it has to be mutable. It manages how many times to repeat a section of code, and we normally take advantage of this to loop over each index of an array or other enumerable datatype. Enumerable data are stored contiguously in memory, which enables us to use an iterator to access every index of data with a single base address and an offset (the iterator).

Here’s an example of imperative iteration. The following code from Isola is used to find the first free index of a player’s inventory, using the variable i to achieve this. Curiously, the function actually has a return signature of type bool (it’s possible for the function to not find a free index), but by making use of C#’s out keyword we can return an index if and only if one is available. This imperative pattern is strikingly similar to a specific algebraic data type in languages like Miranda or Haskell, commonly known as a Maybe or an Option type.

public bool GetFirstFreeIndex(out int index)
{
    index = -1;
    for (int i = 0; i < ItemStackList.Length; i++)
    {
        if (ItemStackList[i].Equals(default(ItemStack)))
        {
            index = i;
            return true;
        }
    }
    return false;
}

We can think of the iterator as an explicit helper. We are manually assigning and updating the variable - giving instructions - to cause the computer to execute code. This is the basis of imperative programming.

With functional programming, we do away entirely with the manual oversight of control flow. We have no for loops, no while loops, no variables at all, and memory management must be abstracted beyond our control. We actually have functional languages to thank for garbage collection.

’Iteration’ is instead achieved through a delicate balance of recursion and pattern matching, where code is recursively executed over a data structure until it converges into a base case.

The below code shows how an equivalent function might be written in Miranda:

|| assume itemStackList defined elsewhere
|| assume isEmpty defined elsewhere

resultNum ::= None | Some num

getFirstFreeIndex :: itemStackList -> resultNum
getFirstFreeIndex list
  = xgetFirstFreeIndex list 0
    where
	xgetFirstFreeIndex [] any = None
    xgetFirstFreeIndex (x : xs) index
	  = Some index, if isEmpty x
	  = xgetFirstFreeIndex xs (index+1), otherwise

Look carefully at how we get around the constraints of immutability. Rather than update data in-situ, we use recursion to pass on the new values as arguments to the next function. We effectively update our values, but without breaking the rules of immutability that constrain us.

This isn’t some arbitrary decision to make our own lives harder; immutability is necessary to faithfully implement the lambda calculus. Reductions must be confluent - they must produce the same result irrespective of the order in which they are evaluated - and this could not be guaranteed if variables could arbitrarily change state throughout the program's lifecycle. Immutability ensures a concept known as referential transparency, that any subexpression can be replaced by its evaluated reduction without altering the program’s behaviour.

Thus, we can say that a functional program is declarative: we the programmers are not telling rocks how to run our code, but are simply declaring that our code be run.

The Properties of Functional Programs

Having cast a spotlight on what sets declarative languages apart from imperative ones, it may provide further clarity to explore the key properties that come as a result of implementing the lambda calculus.

Higher-Order Functions

A higher-order function is a function “that either takes another function as an argument or produces a function as a result” (Clack et al.). While the concept is not exclusive to functional languages (JavaScript is a well-known adopter), in functional programming they are not just a feature, but a benefit of the lambda calculus. There is nothing in the rules of the lambda calculus that restricts what can be the argument of a function, and indeed permitting functions as the argument of functions is required in reductions. Notice the mention of a singular ‘argument’ here. This will be relevant later.

Through its use of type declarations, Miranda creates a fantastic visualisation of how this is all handled, where the type of a function is simply a mapping of an input X to an output Y (X -> Y).

f :: x -> y

g :: w -> (x -> y) -> z

Recursion

Having briefly touched on how functional programming languages can avoid loops by using recursion, let’s dive slightly deeper into what this means for the paradigm.

When I first learnt that functional languages depended on recursion I was somewhat sceptical; recursion is a powerful tool, but it can also be slow and susceptible to stack overflows. Yet in the hands of a functional language, it’s a completely different story.

There are actually multiple different kinds of recursion. Stack recursion, the type that most programmers are familiar with, creates a new frame of data on the stack for each cycle. It is very easy to define, and very easy to follow.

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

Stack recursion is the type of recursion susceptible to overflows. It fundamentally relies on being able to return to the previous stack frame to calculate a final result when winding back up the stack spine, and this forces us to keep those stack frames in memory. Thankfully, accumulative recursion comes to the rescue here. This flavour of recursive, intrinsic to methods like fold, uses an accumulator to pass forwards all data needed between two frames, such that the next call of the function can reuse the exact same stack frame in memory.

printdots :: num -> [char]
printdots n
  = printdots_aux(n, "")
    where
    || printdots_aux :: (num, [char]) -> [char]
    printdots_aux (0, a) = a
    printdots_aux (n, a) = printdots_aux(n-1, "." ++ a)

We can see in the above Miranda code that printdots uses an auxiliary function in its definition to set an initial accumulator (an empty list of char), with recursive calls passing all data forwards. Optimising accumulative recursive functions is known as tail call optimisation.

Immutability

Perhaps what functional programs are best known for (and what may be the steepest learning curve for imperative programmers) is immutability. As discussed above, functional languages must enforce immutability of their values to ensure referential transparency.

Yet beyond this necessity, immutability actually brings a host of other benefits to the program lifecycle. Firstly, a whole class of runtime bugs are eliminated entirely. If a value is initialised, it will always be that value; there is no way for it to be changed. Data race conditions cannot exist because values are readonly.

“As a consequence of referential transparency, subcomputations always give the same result for the same arguments. This means that the code is safer and may often be reused in similar contexts”.

Clack et al., 1995

Next, the compiler can perform compile-time optimisations like constant folding. Expressions like x = 45 + 55 can simply reduce all instances of x with the resultant 100, which can improve code performance at a large enough scale. In fact, evaluating mathematical expressions is analogous to one of the reductions of the lambda calculus (although handled by graph reductions in Miranda).

Currying

Pure lambda functions only allow for a single input and a single output, but we often need to use more than one item of data in our functions. Although we could approach this problem by packing all our input data into a singular structure, currying is the general solution, enabling our “functions to be defined with multiple parameters without the need to use a tuple.” (Clack et al.).

In Miranda, currying is expressed syntactically by placing the argument(s) immediately after a function’s name, as in the following implementation of filter, which takes a predicate of type (* -> bool) and a polymorphic list, and returns a new polymorphic list of all values that returned true against that predicate. Anecdotally, note that my implementation constructs the list in reverse order for a slightly improved list-building efficiency (O(1) per prepend = O(n) total), and therefore must reverse the finalised list before returning it to the caller (at a cost of O(n)).

filter :: (* -> bool) -> [*] -> [*]
filter cond list
  = reverse (xFilter list cond [])
    where
    xFilter cond [] result = result
    xFilter cond (x : xs) result
      = xFilter cond xs (x : result), if (cond x)
      = xFilter cond xs result, otherwise

Currying has another major utility beyond solving this restriction of the lambda calculus, and it is arguably all the more important - “its real advantage is that it provides the facility to define functions that can be partially applied” (Clack et al.).

Partial function application lets our functions be invoked with fewer arguments than they need for evaluation. Instead of causing a compiler error, the function instead finds itself in a “state of waiting” where it will not execute until its remaining arguments are applied. This is an invaluable addition to the functional programmer’s toolkit, and allows us not just to build functions from other functions, but also to pull the strings on how our programs themselves evaluate.

The below code snippet shows how filter can be extended by partially applying it with a predicate and no list.

moreThanEight = filter (>8)

moreThanEight [1, 9] || Evaluates to [9]

Of course, in Miranda there is no all-seeing-eye that has to check to see if the right number of arguments have been supplied to the function; partial application, like all properties of functional programs, is simply an incidence of implementing the lambda calculus in code.

What Counts as a ‘Functional’ Language?

The functional paradigm should now be a little less esoteric, but our definition leads us to an unsettling truth. If functional programs are implementations of the lambda calculus, then some functional languages are not so functional after all.

Languages like Scala and F#, both unambiguously considered functional, do use a declarative code style, and do exhibit all the telltale signs of functional programs, and yet they still allow for mutable datatypes with their var and mutable keywords. These languages are clearly flouting the maxim of referential transparency; by our definition they cannot be functional.

Although it is true that Scala and F# are not programmatic implementations of the lambda calculus, if they have all the rich features of actual functional languages, then is this pedantry even necessary? After all, Scala and F# are both cutting-edge languages in their own right; they have earned their seats at the functional table.

There is a term - pure functional languages - that is sometimes used to delineate the two. This can be contrasted with the impure functional languages, to which Scala and F# belong, to define multi-paradigmatic languages that seek to capture the strengths of both the declarative and imperative families. A programming creole.

This is one solution to the ambiguity of ‘functional’ languages, but is it not an injustice to reduce Miranda and Haskell to a mere subcategory of the functional nomenclature?

If our goal is to make functional programming more accessible to those developers whose interest is not yet piqued by the current name, then perhaps it is the paradigm’s very name that betrays it. All languages have functions, and the permeation of the rich functional features into the imperative languages has somewhat blurred the lines.

Instead, the pure functional languages should be thought of as the Lambda languages. With a name true to their roots, they might no longer be an enigmatic niche of the computer science world.

Summary

The functional paradigm is a well-known but seldom understood child of the programming dynasty, but knowing that their design is a direct reflection of their origins casts the spotlight on what they truly mean.

Learning to read and write functional programs is a uniquely rewarding challenge. It compels you to consider the minutiae of every line of code. Mastering a knowledge of higher-order functions, recursion, immutability, and currying will strengthen your code in any paradigm.

However, perhaps just as valuable as its ability to help you program is how functional programs pay homage to the pioneers of the lambda calculus; to our predecessors whose contributions to the code of the past have given us the code of the present.

Are programs functional because they have immutable state and higher-order functions, or do they have immutable state and higher-order functions because they are functional?