Functional Programming

This thing called “functional programming” is finally all the rage, after being introduced over a half centry ago. Let's see what it’s all about.

The Basics

What is it?

Functional programming is one of many recognized ways of programming, called paradigms. Roughly, the most common paradigms include:

There are many other paradigms as well, but those are the main ones.

What are some of FP’s characteristics?

Why is it important?

Three big reasons, at least. When you truly have no side effects, your code is automatically:

But there's more!

Martin Odersky explains this pretty well:

Language Support for Functional Programming

I think you can roughly group languages in a kind of spectrum like this:

A Relatively Simple Example

Let's implement the famous greedy change making algorithm for U.S. quarters, dimes, nickels, and pennies, several ways. The idea is that a single value is input and the result is an array of the form [q,d,n,p].

Solution 1: A non-functional solution, using mutable variables

Let’s start with the painfully traditional, step-by-step, mutable variable approach, that builds up an array in a for-loop. First, JavaScript:

function change(amount) {
  let result = [];
  let remaining = amount;
  for (let value of [25, 10, 5, 1]) {
    result.push(Math.floor(remaining / value));
    remaining %= value;
  }
  return result;
}

In Python:

def change(amount):
    result = []
    remaining = amount
    for value in [25, 10, 5, 1]:
        result.append(remaining // value)
        remaining %= value
    return result

In Ruby:

def change(amount)
  result = []
  remaining = amount
  [25, 10, 5, 1].each do |value|
    result << remaining / value
    remaining %= value
  end
  result
end

In Java:

public static List<Integer> change(int amount) {
    List<Integer> result = new ArrayList<Integer>();
    int remaining = amount;
    for (int value : Arrays.asList(25, 10, 5, 1)) {
        result.add(remaining / value);
        remaining %= value;
    }
    return result;
}

Let's try to understand how this works:

Iteration  value  remaining   result
---------------------------------------
        0     25         99   []
        1     10         24   [3]
        2      5          4   [3,2]
        3      1          4   [3,2,0]
        4                 0   [3,2,0,1]

Solution 2: A functional (no-variables) solution, using recursion instead of loops

We can make a slight change to the previous table:

values    remaining   result_so_far
-----------------------------------
[25,10,5,1]      99   []
[10,5,1]         24   [3]
[5,1]             4   [3,2]
[1]               4   [3,2,0]
[]                0   [3,2,0,1]

Now, let’s make a function c(values,remaining,result) whose input is a row of the table and whose output is the call for the next row of the table. Ooooooh. And, of course, when values is empty, it’ll output the result. Like this:

c([25,10,5,1], 99, [])
    = c([10,5,1], 24, [3])
    = c([5,1], 4, [3,2])
    = c([1], 4, [3,2,0])
    = c([], 0, [3,2,0,1])
    = [3,2,0,1]

The second and third lines say: "Changing 24 cents with dimes, nickels, and pennies, given that you have three quarters already, is done by changing 4 cents with nickels and pennies, given that you already have three quarters and two dimes."

In JavaScript:

function change(amount) {
  function c(values, remaining, result) {
    if (values.length === 0) {
      return result;
    } else {
      return c(values.slice(1), remaining % values[0], [...result, Math.floor(remaining / values[0])]);
    }
  }
  return c([25, 10, 5, 1], amount, []);
}

This is probably a terrible solution in JavaScript. JavaScript arrays are mutable, so this code likely makes copies whenever the new arrays were passed along. This is horribly inefficient, but suppose the compiler could figure out that we never actually change the array of denominations, and manages to shares state (without copying) among each of the parameters. In some languages, lists or arrays are defined to be immutable, so this sharing behavioris essentially wired into the language definition, so this kind of code is fast. This happens in Elm:

change amount =
  let c values remaining result =
    case values of
      [] -> result
      value::rest ->
        c rest (remaining % value) (result ++ [remaining // value])
  in
    c [25,10,5,1] amount []

and in Standard ML:

fun change amount =
  let
    fun c [] remaining result = result
      | c (value::rest) remaining result =
          c rest (remaining mod value) (result @ [remaining div value])
  in
    c [25,10,5,1] amount []
  end;

and in Clojure:

(defn change [amount]
  (letfn [
    (change-helper [values amount result]
      (if (empty? values)
        result
        (change-helper (rest values) (rem amount (first values))
          (conj result (quot amount (first values))))))
    ]
    (change-helper [25 10 5 1] amount [])))

Actually, wait, that’s not a good Clojure solution....

Solution 3: Clojure loop/recur...because JVM

ATTENTION CLOJURE PROGRAMMERS. Clojure runs on the JVM which does not support tail recursion optimization. Fortunately, Rich Hickey has your back and added some language features that compensated for this sadness. You need to do things this way:

(defn change [amount]
  (loop [values [25 10 5 1] remaining amount result []]
    (if (empty? values)
      result
      (recur (rest values) (rem remaining (first values))
        (conj result (quot remaining (first values)))))))

Wait, we still haven’t gotten it. We need transients:

(defn change [amount]
  (loop [values [25 10 5 1] remaining amount result (transient [])]
    (if (empty? values)
      (persistent! result)
      (recur (rest values) (rem remaining (first values))
        (conj! result (quot remaining (first values)))))))

The ML-like languages implement tail recursion automatically. No need for all this.

Solution 4: A solution using reduce

Reduction is cool. Look how we flow the partial results through the array of denominations:

coin-reduce.png

Our code gets concise but I’m not sure if it’s any more readable:

function change(amount) {
  const c = (acc, value) => [acc[0].concat([Math.floor(acc[1]/value)]), acc[1]%value];
  return [25, 10, 5, 1].reduce(c, [[], amount])[0];
}

How about the Clojure version?

(defn change [amount]
  (reduce (fn [accumulation value]
    (let [left (peek accumulation)]
      (conj (pop accumulation) (quot left value) (rem left value))))
    [amount]
    [25 10 5]))

Higher Order Functions

A higher order function is a function that can be passed functions as arguments or that returns a function. The simplest examples are probably:

function twice(f, x) {
    return f(f(x))
}

function apply(f, x) {
    return f(x)
}

function compose(g, f) {
    return x => g(f(x));
}

It is very common to see higher-order functions that operate on collections. This often makes your code much simpler since you don't need loops and conditionals! Examples:

It is also common to see a sort function that is higher-order; you pass in the comparator function.

Closures

TODO

An interesting kind of JavaScript Memory Leak

Effects in Pure Functional Languages

TODO - basic issues about state

TODO - side effects

Read about monads at Wikipedia.

Theoretical Foundations

The idea of functional programming is rooted in (1) the ideal of the mathematical function, and (2) the theory of combinators so let's take a quick review of these things.

Functions

Informally, a function is a mapping from an argument to a result. It always produces the same result for the same argument. More formally, in set theory, a function from a set A to a set B is a subset of A × B such that each element of A appears exactly once as the first component of a tuple in the set.

See Wikipedia for more.

The Lambda Calculus

See Wikipedia's article for a nice introduction.

Combinators and Combinatory Logic

See Wikipedia.