De­spite its rep­u­ta­tion as a math­e­mat­i­cal fad, func­tional pro­gram­ming had the great­est re­turn on in­vest­ment of all the com­puter sci­ence I stud­ied:

• An abil­ity to think clearly, re­mov­ing un­nec­es­sary com­plex­ity from the code.
• Es­sen­tially re­mov­ing the de­bug­ging phase.

To show these prop­er­ties, we will go back­wards:

1. Im­per­a­tive bugs
   What is a bug?
2. Func­tional prin­ci­ples
   How to pre­vent bugs?
3. Im­per­a­tive ex­am­ple
   A bug-prone prob­lem
4. Func­tional ex­am­ple
   An ap­pli­ca­tion of (2) to the prob­lem
5. Typ­ing
   New pos­si­bil­i­ties opened by this par­a­digm

Im­per­a­tive bugs

Bugs hap­pen when a com­puter runs in­struc­tions you wrote but not those you meant. A bug, there­fore, man­i­fests it­self in the form of an un­wanted ef­fect (or worse, its ab­sence, much harder to de­bug). The process is as fol­lows:

1. Reach a state where the bug man­i­fests it­self.
2. Read the code back­wards, keep­ing the state of the mem­ory in mind, play­ing back the in­struc­tions.
3. Every time some­thing af­fects the er­ro­neous state, ex­plore that ex­e­cu­tion branch.
4. Go back to (2) and ex­plore the whole ex­e­cu­tion tree un­til you find the source of the bug.

The branch­ing fac­tor makes this process ex­po­nen­tial and, there­fore, very time-con­sum­ing.

The prob­lem, es­sen­tially, lies in the chang­ing na­ture of the state: many in­struc­tions can change one vari­able, and be­cause of the na­ture of com­pu­ta­tion, there is some­times no other op­tion than to re­play the ex­e­cu­tion.

Func­tional prin­ci­ples

Let us, there­fore, de­clare the fol­low­ing prin­ci­ples:

1. Im­mutabil­ity: a vari­able is de­clared once and for all, and con­se­quently, con­stant.
2. No loops: there is no point in run­ning in­struc­tions twice if vari­ables do not change.
3. No side ef­fects: pro­ce­dures change the state of the com­puter.
4. Every­thing is a value: since there are no side ef­fects, code only makes sense as a value.
5. Fi­nally, sep­a­ra­tion of logic and data (≠ ob­ject-ori­ented pro­gram­ming): since vari­ables are con­stant, new state is ex­pressed with new vari­ables. There­fore, data is tran­sient, while logic is per­sis­tent.

Since code only trans­forms data, like a func­tion, we call this kind of pro­gram­ming func­tional.

While these prin­ci­ples, when prop­erly fol­lowed, elim­i­nate bugs, but is it not lim­it­ing?

Im­per­a­tive ex­am­ple

Let us try a sim­ple ex­am­ple: re­vers­ing a linked list. Here is an im­per­a­tive so­lu­tion, where we in­vert point­ers:

You can edit and run the code!

Phew: it works on our small ex­am­ple. But the logic is com­plex, par­tic­u­larly the re­as­sign­ment of point­ers. If there was an er­ror, where should we look? The ini­tial­i­sa­tion of previous and current? Is the or­der of the in­struc­tions in the loop cor­rect? Etc.

The only way to be sure is to test all the cases:

• null,
• one NodeList,
• many NodeList.

What is triv­ial on one small ex­am­ple be­comes im­pos­si­ble at a larger scale. The de­vel­oper lives in the ter­ror that, sooner or later, a bug ap­pears, and he will have to sift through all this im­per­a­tive logic. So, let us make that code func­tional in­stead.

Func­tional ex­am­ple

Since we op­er­ate on data, let us look at the shape of our in­put, and what we need.

1. Pos­si­ble op­er­a­tions. There is only one di­rec­tion in which we can it­er­ate: from the head to the tail.
2. Shape of data. So, when our ListNode is null, it means that we have reached the end of the list.
3. Needs. There, we should ap­pend all the val­ues we have seen, in the right or­der. Let us sup­pose we have it, in­side the pa­ra­me­ter tail. We will see later how to get it.

Half of our work is done! What about the sec­ond case, when our ListNode is not null? It means that we are it­er­at­ing, cur­rently ex­am­in­ing a node of our list. Our tail pa­ra­me­ter con­tains every­thing we have seen so far, in the right or­der. So, we will build the cor­rect tail for the next node:

Fi­nally, we can con­tinue the it­er­a­tion:

Done! Here is the com­plete func­tion:

Much cleaner. One has to get used to read and write code in this style (the great­est par­a­digm change in my pro­gram­ming ca­reer!) but the ben­e­fits are, ac­tu­ally, even greater.

Typ­ing

When we were de­bug­ging, we read the code while keep­ing prop­er­ties about the state of mem­ory in our head.

With func­tional pro­gram­ming, since vari­ables do not change, we can di­rectly as­sert these prop­er­ties in our code. That is typ­ing. More specif­i­cally, what is known at com­pile time is called sta­tic typ­ing.

Then, the com­piler ver­i­fies and com­poses all these lit­tle as­ser­tions to prove that our re­sult is cor­rect: it is what we meant.

Here is our func­tional code, with the most ex­ten­sive typ­ing:

For some­one who is not used to types, this is cer­tainly fright­en­ing. Types are longer than our func­tion! (Smarter type sys­tems than Type­Script might be able to in­fer them au­to­mat­i­cally. This area of re­search is par­tic­u­larly ac­tive.)

While the ex­am­ple is run­ning cor­rectly, let us see what the types tell us.

In­deed: when some­one gives us a cir­cu­lar linked list, we will cy­cle in­def­i­nitely. It showed us a bug be­fore run­ning the code.

In ad­di­tion, you can hover on the vari­able test above to see the in­ferred type: Type­Script knows that it has the cor­rectly-or­dered se­quence 🥇 🥈 🥉 be­fore run­ning the code!

It is only pos­si­ble thanks to the prin­ci­ples listed above. We can de­fine much more pre­cisely the pre- and post­con­di­tions of our func­tion. With this ap­proach, you do not have to keep prop­er­ties about your code in mind. Our code is proven safe: the fo­cus is less on tests, but they can still be use­ful when the type sys­tem is not pow­er­ful enough. How­ever, in­stead of fight­ing the type sys­tem, we usu­ally try to make in­valid states im­pos­si­ble in the de­f­i­n­i­tion of the shape of our data.

Per­son­ally, I find types es­pe­cially use­ful dur­ing:

• pro­to­typ­ing: I of­ten start draft­ing code by writ­ing types. They are a tool for thought; a no­ta­tion for con­di­tions.
• refac­tor­ing: the com­piler warns you when some­one (of­ten one­self!) is break­ing your code.

For a fur­ther study of the power of type sys­tems in a func­tional con­text, you can check gen­er­alised al­ge­braic datatypes and de­pen­dent types.