Functional Programming: a small introduction

It seems there's some confusion on why you might use functional programming methods like map/reduce/filter, and so I thought I'd write something to try and explain why I think they're useful and interesting.

Reduce

Imagine you have an array of numbers, and you want to sum them.

The common imperative approach is usually something like this:

const ints = [1, 2, 3, 4]
let sum = 0
for (let i = 0; i < ints.length; i++) {
  sum += ints[i]
}
console.log(sum)

Functional programming offers an alternative approach:

function add(a, b) {
  return a + b
}

function sum(a) {
  return a.reduce(add, 0)
}

sum(ints) // -> 10

I think about reduce as a way to join many values into a single value, it takes a series of values and builds up a new value.

How reduce works

A simple implementation of reduce() might be something like this. Let's break it down step by step:

A function that takes another function as an argument (or returns another function) is called a higher-order function. reduce is a higher-order function that "folds" multiple values into a single value.

Eloquent JavaScript has an exercise where they ask the reader to turn a simple array into a nested object, such that:

const nums = [1, 2, 3] // an array of numbers

// becomes

const result = {
  value: 1,
  rest: {
    value: 2,
    rest: {
      value: 3,
      rest: null,
    },
  },
}

There are a number of ways to solve this, but here is my approach:

const nums = [1, 2, 3]
const result = nums.reduceRight((rest, value) => ({ value, rest }), null)
console.log(result)

reduceRight is the same as reduce except it starts at the end of the array, and works backwards.

Even though JavaScript is weakly typed, analyzing the type signatures of functions can still yield valuable information about how a function works.

The type of functions used in reducers is a b -> a, that is, a function that takes two arguments and returns a value that's the same type as the first argument.
reduce is a function with the signature (b a -> b) b [a] -> b: it accepts a reducer function, a thing b, a list a, and returns a thing the same type of b.

I should note that recursive solutions are more typical in functional approaches.

function reduce(fn, init, a) {
  if (a.length === 0) return init
  return reduce(fn, fn(init, a[0]), a.slice(1))
}
function reduceRight(fn, init, a) {
  if (a.length === 0) return init
  return reduceRight(fn, fn(init, a[a.length - 1]), a.slice(0, -1))
}
const nums = [1, 2, 3, 4]
console.log(reduce((a, b) => a + b, 0, nums))
console.log(reduceRight((rest, value) => ({ value, rest }), null, nums))

Map

But reducing an array to a single value is only one of many things programmers do with arrays.

What if you wanted to transform each element? Maybe you have an array of numbers and you want to multiply them all by themselves?

The imperative approach might be something like:

const ints = [1, 2, 3, 4]
const squared = []
for (let i = 0, length = ints.length; i < length; ++i) {
  squared.push(ints[i] * ints[i])
}
console.log(squared)

In functional programming, when you want to iterate over a set and transform it, you would use map.

const ints = [1, 2, 3, 4]
const squared = ints.map(n => n * n)
console.log(squared)

This is much tidier, in my opinion. When you see that big messy for loop, you have no idea what's going on until you fully read the whole thing and attempt to mentally parse it. When you see map, without reading anything but that word, you immediately know that you are creating a new array with all of the values changed by a given function.

map has a type signature of (a -> b) [a] -> [b], it's a function that receives a function of type a which returns a thing of type b when given a list of a, and then returns a list of bs.

You could implement map like the following:

function map(func, arr) {
  const state = []
  for (let i = 0, l = arr.length; i < l; ++i) {
    state.push(func(arr[i]))
  }
  return state
}
console.log(map(n => n * n, [1, 2, 3]))

It follows much the same pattern as the reduce function. In fact, they're almost identical...

If you recall, reduce always returns a single value. Well, an array, although it contains many items, is itself a single value. What if you give reduce an empty array as the initial value, and add to that array instead?

const ints = [1, 2, 3, 4]
const product = ints.reduce((prev, curr) => {
  prev.push(curr * curr)
  return prev
}, [])
console.log(product)

It works just as expected!

In fact, you can implement map as a wrapper around reduce:

const ints = [1, 2, 3, 4]
const map = (fn, a) =>
  a.reduce((prev, curr) => {
    prev.push(fn(curr))
    return prev
  }, [])
console.log(map(n => n * n, ints))

If your map function returns another array, you can even "un-nest" or flatten the arrays into a single array:

const flatMap = (fn, a) => a.reduce((p, c) => p.concat(c), [])
console.log(flatMap(n => [n, n], [1, 2, 3, 4]))

Filter

Filtering a list of values is another useful task to be done with an array.

We can implement a filter function that iterates over the whole list, and returns a new list of values that only match a given function:

const filter = (fn, a) => a.reduce((p, c) => (fn(c) ? p.concat([c]) : p), [])
const isEven = n => n % 2 === 0
console.log(filter(isEven, [1, 2, 3, 4]))

Partition

A slight twist on filter, this splits an array into two arrays whether they match a predicate function:

const partition = (fn, a) =>
  a.reduce(
    (p, c) => {
      const idx = Number(fn(c))
      p[idx].push(c)
      return p
    },
    [[], []],
  )
console.log(partition(n => n % 2 === 0, [1, 2, 3, 4]))

I'm of the opinion unless you need to break or continue inside a loop, most use-cases of for to iterate over an array can usually be replaced with a higher order function like reduce, and get huge gains in readability.

If you know that map operates on a function and an array, and you see the following, which one takes you longer to read and understand what it does?

const items = [
  { foo: 'a', bar: 1 },
  { foo: 'b', bar: 2 },
]

// functional
const newList = items.map(e => e.foo)

// imperative
const newList = []
for (let i = 0; i < items.length; i++) {
  newList.push(items[i].foo)
}

Helper functions

That example above, taking an array of objects and retrieving the value of a particular properties from each one, is a common enough pattern that I'd like to make a special function for it:

I can take this another step further and make a function specifically for retrieving values from an array of objects:

const items = [
  { foo: 'a', bar: 1 },
  { foo: 'b', bar: 2 },
]
const prop = a => b => b[a]
console.log(items.map(prop('foo')))
const pluck = (a, b) => b.map(prop(a))
console.log(pluck('foo', items))

If you're interested in learning more about functional programming, check out my post on currying and partial application