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.

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

**Imperative programming**: programming with commands—do this, then do that, etc.**Declarative programming**: programming by saying*what*you want, not*how*it should be computed**Structured programming**: programming with nicely nested, crisp, control structures (no "gotos")**Object oriented programming**: programming around a society of objects, each with their own behaviors**Functional programming**: programming by composing side-effect-free functions

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

- Functions without side-effects (e.g., mutable variables, I/O, databases)
- The use of higher-order functions: functions that can (1) take functions as arguments and (2) return functions
- First-class functions: function values can be as freely used as numbers, strings, booleans, etc.
- Recursion, folding, and powerful collection operators in place of loops
- The use of lexical closures for information hiding

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

- Thread-safe, which is huge!
- Amenable to more compiler optimizations, especially in regard to core and thread allocation, and caching of previous results
- Easier to prove correct, because the result of calling a specific function with a specific argument is always the same no matter how many times you make that call. This is referential transparency.

But there's more!

- Functions as values give programmers more opportunities for reuse (Remember Spolsky's article?)
- A lot of Big Data processing is based on the MapReduce paradigm which is straight out of functional programming theory.

Martin Odersky explains this pretty well:

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

**Pure functional languages**, in which you can only do functional programming. There are no side effects ever, so don't even*think*about imperative programming (Haskell, I think).**Mostly functional languages**, in which imperative features are there if you need them, but the language is intended to be used for functional programming 90% or more of the time (LISP, Scheme, Clojure, Standard ML, OCaml, F#).**Imperative languages with great functional programming support**, which may include first-class functions (JavaScript, Scala) or features that are so near first-class functions that they might as well be considered to be so (C#, Ruby, Python).**Imperative languages with minimal functional programming support**, in which you may get pointers to functions but that's about it (Ada, C), or let you simulate higher-order functions with a lot of work (Java, pre Java8).**Languages with truly zero functional programming support**.

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]`

.

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]

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....

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.

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

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]))

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:

`forEach`

`every`

(all)`some`

(any)`one`

`map`

`reduce`

(inject, fold)`reduceRight`

(injectRight, foldRight)`mapConcat`

(flatmap)`takeWhile`

`dropWhile`

`find`

(keep, select)`findAll`

(filter, keepAll, selectAll)`reject`

`partition`

It is also common to see a `sort`

function that is higher-order; you pass in the comparator function.

TODO

An interesting kind of JavaScript Memory Leak

TODO - basic issues about state

TODO - side effects

Read about monads at Wikipedia.

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.

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.

See Wikipedia's article for a nice introduction.

See Wikipedia.