📚 Austin Merrick’s Blog

Functional Programming - How and Why

Let's start with an example. In Advent of Code 2022 day 1 we get groups of numbers as input like:

1000
2000
3000

4000

5000
6000

7000
8000
9000

10000

We want a program that sums up each group and returns the largest. The largest in this example is the 4th group, 24000.

Here is an imperative solution:

const input = $("pre").innerText
let runningMax = 0
for (let group of input.split("\n\n")) {
    let runningSum = 0
    for (let num of group.split("\n"))
	    runningSum += Number(num)
    runningMax = Math.max(runningMax, runningSum)
}
console.log(runningMax)

Here is a functional solution:

const input = $("pre").innerText
function sumGroup(group) {
	return group
		.split("\n")
		.map(Number)
		.reduce((a,b)=>a+b)
}
const sortedGroups = input
	.split("\n\n")
	.map(sumGroup)
	.sort((a,b)=>a-b)
console.log(sortedGroups.at(-1))

The imperative solution:

The functional solution:

Higher order functions are functions that operate on other functions. map, reduce, and sort take a function as an argument.

How exactly does one do functional programming?

Avoid Favor
mutable state function parameters and immutable data
iterative steps transforming data
loop statements recursion or higher order functions
intertwined data and behavior separated data and behavior

Often times functional programming looks like using higher level functions. You might be wondering, "Functions like map are basically fancy loops! What if map did not already exist?" A functional programmer would write map themself using recursion. Anything written with loop statements can be rewritten with recursion.

Imagine we want a range function where range(5) returns [1,2,3,4,5].

Imperative solution:

function range(end) {
	let nums = []
	for (let i=1; i<=end; i++)
		nums.push(i)
	return nums
}

Functional solution:

function range(end, cur=[]) {
	if (cur.length >= end) return cur
	return range(end, [...cur, cur.length+1])
}

This recursive solution suffers performance penalties however. See this HN comment for more info.

I would have never thought to use recursion for this function before learning about functional programming. Now I might actually prefer the recursive solution.

Why use functional programming

Functional programming has some amazing benefits:

Avoid bugs related to mutable state. Static typing removes the class of bugs caused by type errors. Similarly, functional programming removes the class of bugs caused by mutation. Every programmer has copied an array, modified the copy, then spent way too long trying to figure out how the original got modified (aka shallow copies vs. deep copies). Mutable state causes especially tricky bugs in large code bases. What shallow copy made the mutation? It could be anywhere!

Write declarative code. Imperative code describes how to do things. Declarative code describes what we are doing. Because of this, declarative code is easier to understand and modify. Think about how the original imperative solution has variables named runningMax and runningSum. It's tempting to name these variables maxGroup and sum, but that would be lying. They start at 0 and change over the course of the program. We are stuck with variable names describing how we do things. In the functional solution, sortedGroups describes exactly what we are doing.

Write code that is easier to test. In imperative code it is common to write void functions which mutate state. Games tend to define update() functions which mutate some state each tick. We can avoid mutation by taking game state as an argument and returning new state. Now our game is much easier to test too! We simply call update with some game state and assert that the result is what we expect. Imagine how hard it would be test the imperative update function!