Functional programming

The big picture: programs made of functions

A function is like a machine with a slot for ingredients and a tray for the result. The things you put in are called arguments (or parameters). The thing that comes out is the return value. In functional programming we love functions so much that we treat them like any other thing, such as a number or a word: we can keep a function in a variable, hand it to another function, or get one back as a result. A language that allows this has first-class functions.

Functional programming rests on two big habits. The first is to write pure functions, whose result depends only on their arguments. The second is to use immutable data, which never changes: to make a change you build a new value. The unavoidable side effects, such as talking to the network, are pushed to the edges of the program.

  input --> [ clean ] --> [ filter ] --> [ total ] --> output

  Each box is a function.
  Each arrow carries a value, not a changed variable.

Pure functions and referential transparency

A pure function is a function that behaves like one in mathematics. Two rules: (1) the same arguments always give the same result, and (2) calling it changes nothing that anyone can notice outside it. A calculator button is pure: 7 times 6 is 42 today, tomorrow and on Mars.

Anything a function does besides computing its result is a side effect: writing to the screen, a file, the network or a database; changing a global variable; or changing the argument it received. Reading something that can change is also a problem: the clock, the user's typing, a random number or a mutable global variable. These are hidden inputs, because they do not appear in the parameter list. Side effects are hidden outputs.

Replacing a call by its value

An expression is referentially transparent when you can swap it for its value and the program does not change. It is how we reason in algebra: if y = 3 * 4, you can write 12 wherever you see y. Pure functions always give that. A function that changes state breaks it:

let calls = 0;
const next = (): number => {
	calls += 1;
	return calls;
};

const a = next() + next(); // 1 + 2 = 3
calls = 0;
const x = next(); // 1
const b = x + x; // 1 + 1 = 2, not 3

Referential transparency allows nice tricks. Memoisation stores the result of a call and returns it when the same arguments come again. This is correct only for pure functions: if the function read the clock, the cache would return an old time; if it wrote to a file, the second call would silently skip the writing.

How to make a function pure

Turn the hidden input into a parameter. A function isExpired(coupon) that asks the clock what time it is becomes isExpired(coupon, now). Now a test passes any instant it likes and needs no fake clock. The real clock is read in one place at the edge of the program. The same fix works for withTax(price): write withTax(price, taxRate).

• Tests without mocks. A mock is a stand-in for something the test cannot control, such as the clock or the database. A pure function has no such thing: build values, call it, compare the result.
• Deterministic is not the same as pure. A function sum(xs) that also prints its result always returns the same number, but printing is an effect, so it is not pure and its call cannot be skipped by a cache.
• Local mutation is fine. If a function makes a new array inside, fills it with push in a loop and returns it, nobody outside can tell. It is still pure, because the changed thing never escaped before the end.
• Property-based tests. These generate hundreds of random inputs and check a rule such as decode(encode(x)) == x. When one fails, they run the function many times with smaller inputs to find the smallest failing one. This only works if each run depends on the input alone, so pure functions are the perfect target.

Immutability: data that never changes

A value is immutable when it never changes after it is built. Operations that seem to modify it return a new value and leave the old one as it was. Think of a printed photo: to put a hat on the person you print a new photo. The one in the album stays the same, so nobody who is looking at it gets a surprise.

That removes a whole family of bugs, the ones where one part of the program changes data behind the back of another part that was using it. It also helps concurrency (many tasks running at once): the classic danger is shared mutable state, two tasks touching the same data while at least one of them writes. If the data cannot change, it can be shared freely. This is a big reason why Elixir and Erlang scale well over many processor cores.

Immutability in TypeScript

Copying with spread syntax ({ ...a }) is shallow: it makes a new outer object, but fields that hold objects or arrays still point to the same inner values. To update nested data immutably, copy every level along the path:

const a = { name: 'Ana', tags: ['x'] };
const bad = { ...a, name: 'Bia' };
bad.tags.push('y'); // a.tags changed too! same array

const good = { ...a, tags: [...a.tags, 'y'] }; // new array too

Immutability in Elixir

In Elixir all data is immutable. List.delete(list, 2) returns a new list and does not touch list; to keep the result you must bind it to a name. A name can be rebound (x = 2 after x = 1), but that is not mutation: the old value still exists for whoever already had it. A function created while x was 1 keeps seeing 1, because an anonymous function captures values, not names.

Why it is not slow: structural sharing

Copying a big list for every change would be terrible. The trick is that the new value reuses the parts of the old one that did not change. An Elixir list is a chain of cells, each pointing to the next. Adding to the front creates one new cell that points to the old list. Adding to the end needs a new copy of every cell before it, because each one must point to a new next cell.

  new:   [0] --+
               v
  list:  [1] -> [2] -> [3] -> []

  1 new cell. The old list is untouched and shared.

Higher-order functions: map, filter, reduce

A higher-order function is a function that takes another function as an argument, returns a function, or both. It separates 'how to walk through the data' from 'what to do with each item'. The higher-order function knows how to walk. The function you hand it says what to do.

In a chain such as xs.filter(...).map(...), each step receives the collection that the previous step produced. [1, 2, 3, 4] goes through filter for evens and becomes [2, 4], then through map times ten and becomes [20, 40].

How reduce works

reduce takes an initial value for the accumulator and a function. For each item, the function receives the accumulator and the item, and what it returns becomes the next accumulator. Tracing the accumulators on paper is the safest way to compute a reduction:

  start acc = 10
  item 1:  10 + 2 = 12
  item 2:  12 + 4 = 16
  item 3:  16 + 6 = 22   <- result

• Always give an initial value. It is the answer for an empty collection: 0 for a sum, 1 for a product, an empty list for joining lists. In JavaScript, [].reduce((a, b) => a + b) with no initial value throws a TypeError.
• The accumulator can be a structure. With a pair like {count, sum} you compute several things in a single pass over the data, with no temporary lists.
• Reduce is the general one. map and filter are special cases where the accumulator is a list. We still use them because they tell the reader the intention: map means n go in and n come out.
• Argument order differs by language. In Elixir, Enum.reduce(list, initial, fn x, acc -> ... end) gives the item first and the accumulator second. Building a list with [x | acc] produces the items in reverse, because adding at the front is the cheap operation.

A classic trap

map calls your function with three arguments: the item, its index and the whole array. parseInt(text, base) takes the base as its second argument, so ['1', '2', '3'].map(parseInt) gives [1, NaN, NaN]. The safe way is to write the function out: xs.map(s => parseInt(s, 10)), or to use Number.

Reducing in parallel

Imagine splitting a long list into pieces, reducing each piece on a different worker, then combining the partial results in order. The answer equals the one-worker answer only if the combining function is associative: grouping does not matter. Sum, product, maximum and joining lists are associative. Subtraction is not: (10 - 3) - 2 = 5 but 10 - (3 - 2) = 9. The function must also be pure, or the order of execution would show in the result.

Closures: functions with a memory

When you create a function inside another function, and the inner one uses variables of the outer one, it takes access to those variables with it. Even after the outer function has finished, the variables stay alive as long as the inner function exists. That pair, the code plus the variables it remembers, is a closure.

function makeAdder(n: number): (x: number) => number {
	return (x) => x + n; // remembers n
}
const add5 = makeAdder(5);
console.log(add5(10)); // 15

Which variables a function can see is decided by lexical scope, which means by where the function is written in the source code. That is the base of partial application and currying, which we meet later.

Each call gets its own memory

Every time the outer function runs, a fresh set of variables is made. Two closures born from two different runs have separate states. Only closures born in the same run share their variables.

function counter(): () => number {
	let c = 0;
	return () => {
		c += 1;
		return c;
	};
}
const a = counter();
const b = counter();
a(); a();
console.log(b()); // 1: b has its own c

It remembers the variable, not a copy

In JavaScript and TypeScript a closure keeps a reference to the variable. If the variable is changed later, the function sees the new value. So a captured let rate that is reassigned is a hidden input of the function. Declaring it with const removes the surprise.

The old loop trap comes from this. With var, the variable has function scope, so all the closures made in a loop share one single i, and after the loop it is 3. With let, the variable has block scope, and the for makes a new binding for each turn, so each closure gets its own.

const fs: Array<() => number> = [];
for (var i = 0; i < 3; i++) fs.push(() => i);
console.log(fs.map((f) => f())); // [3, 3, 3]
// with `let i`, it would print [0, 1, 2]

Useful, with two warnings

• Private state without classes (the module pattern). A function declares a local variable and returns an object whose methods use it. Whatever is not returned is out of reach. But remember that this private mutable state makes the methods impure.
• Elixir captures values. An anonymous function takes the values of outer variables when it is created, and rebinding a name inside it does not change anything outside. So Enum.each(list, fn _ -> count = count + 1 end) leaves count at 0, and the compiler warns that the new count is never used. To accumulate, use Enum.reduce, where the accumulator is passed and returned.
• Memory leaks. Captured variables live as long as the closure lives. A long-lived closure, such as an event handler, a timer or a cache entry, that captures a huge array keeps the whole array in memory. Capture only what you need (for example, store the length in a constant) or remove the handler.

Recursion and tail calls

Recursion means that a function solves a problem by calling itself on a smaller version of the same problem. Picture a set of nesting dolls: to count the dolls, you open the biggest one, count 1 and then count the dolls inside, which is the same job on a smaller set. A correct recursive function always has two parts.

1. Base case: the version so small that you can answer directly (the empty list has 0 items; the smallest doll has nothing inside).
2. Recursive step: a call on a smaller input, so that every call gets closer to the base case.

Without a base case, or without getting closer to it, the function never stops. Why? Each call needs a frame on the call stack, a pile of notes that holds the parameters, the local variables and the place to go back to. The frame is thrown away only when the call returns. An endless recursion piles up frames until the stack is full; in JavaScript you see RangeError: Maximum call stack size exceeded.

def sum([]), do: 0
def sum([head | tail]), do: head + sum(tail)

# sum([4, 5, 6]) = 4 + (5 + (6 + 0))

For a list of n items this makes n + 1 calls: one per item and one for the empty list. The additions wait on the way in and are done on the way out. Because there is still work to do after each call returns, this function is not tail-recursive.

Tail calls

A call is in tail position when it is the very last thing the function does: whatever the call returns is exactly what the function returns, with no addition, joining or other work left. A function whose recursive calls are all in tail position is tail-recursive. To get there, use an accumulator: do the pending work beforehand and carry the partial result as an argument.

def len(list, acc \\ 0)
def len([], acc), do: acc
def len([_ | tail], acc), do: len(tail, acc + 1)

def fact(0, acc), do: acc
def fact(n, acc), do: fact(n - 1, acc * n)

With tail-call optimisation, the runtime replaces the current frame with the new one instead of stacking another, so a recursion of a million steps uses a constant amount of stack, like a loop. The Erlang virtual machine, where Elixir runs, always does this. Among JavaScript engines only JavaScriptCore does, and only in strict mode, so in portable TypeScript (Node.js uses V8) a million-deep recursion still overflows. There, write a loop or use reduce.

Elixir has no while or for loop with a counter that changes, because that needs a mutable variable. Repetition is a function that calls itself with the new values as arguments. In everyday code you rarely write it by hand: Enum.map, Enum.reduce and for comprehensions are built on it.

Composition and currying

Composition joins two functions into a new one: the output of the first becomes the input of the second. It is like connecting pipes: the opening where water comes out of one must fit the opening where it goes into the next. In math, compose(f, g)(x) means f(g(x)): the function written last is applied first.

Many people find that right-to-left reading confusing, so libraries also offer pipe, which applies functions in the order you write them: pipe(f, g)(x) is g(f(x)), like an assembly line. pipe(f, g, h)(x) is h(g(f(x))).

const pipe =
	(...fns: Array<(n: number) => number>) =>
	(x: number): number =>
		fns.reduce((acc, f) => f(acc), x);

pipe((n) => n + 1, (n) => n * 2, (n) => n - 3)(4); // 7

This shows that functions are ordinary values: they can sit in an array and be walked through like any other data. Using reduceRight instead of reduce gives compose.

Rules of composition

• Types must fit. For f: A => B and g: B => C, the composed function has type A => C. The middle type B disappears from the final signature, and the type checker complains if the pipes do not fit.
• Associative. (f ∘ g) ∘ h equals f ∘ (g ∘ h). So you can drop the parentheses and pull a stretch from the middle of a pipeline into a named function without changing the result.
• Identity. The identity function x => x does nothing, and composing with it changes nothing. It is the neutral element, like 0 in addition.
• Not commutative. The order matters. With inc = n + 1 and dbl = n * 2, compose(inc, dbl)(5) is 11 and compose(dbl, inc)(5) is 12.

Currying and partial application

Currying (named after the logician Haskell Curry) changes the shape of a function: (a, b) => ... becomes a => b => .... A curried function takes one argument at a time, and each step returns a function that remembers the earlier arguments through a closure.

const multiply = (a: number) => (b: number): number => a * b;

[1, 2, 3].map(multiply(3)); // [3, 6, 9]

const add = (a: number, b: number) => a + b;
const add10 = add.bind(null, 10); // partial application

Partial application is giving only some of the arguments and keeping a function that waits for the rest. The two ideas are cousins: currying changes the shape of the function, partial application is the act of fixing arguments. A curried function makes partial application easy, but you can also do it without currying, with bind or with a small lambda such as n => multiply(3, n).

The Elixir pipe

Elixir has a built-in operator |>. At compile time it rewrites a |> f(b) as f(a, b): the left side becomes the first argument. The standard library was designed for this: the main data is always the first parameter. A pipeline then reads in the order in which things happen, with no nested calls.

  nested (read inside-out):   c(b(a(x)))

  pipe (read top-down):       x
                              |> a()
                              |> b()
                              |> c()

Algebraic data types and pattern matching

Algebraic data types (ADTs) are made with just two operations. A sum type means 'or': the value is exactly one of several variants, each marked by a tag. A product type means 'and': the value has all its fields at the same time. A Shape that is either a circle or a rectangle, never both, is a sum. A point with an x and a y is a product.

type Shape =
	| { kind: 'circle'; r: number }
	| { kind: 'rect'; w: number; h: number };

function area(s: Shape): number {
	switch (s.kind) {
		case 'circle': return Math.PI * s.r ** 2;
		case 'rect': return s.w * s.h;
		default: {
			const unreachable: never = s;
			return unreachable;
		}
	}
}

In TypeScript the sum type is the discriminated union: every variant has a field in common (here kind) with a different literal in each. When you test that field with if or switch, the compiler narrows the type inside each branch, so s.r is allowed only in the circle case. In Elixir the same idea is a tuple tagged with an atom, such as {:circle, r}.

Exhaustiveness: the compiler as a helper

never is the type with no values. After all variants are handled, what is left in default is never, and the assignment compiles. If someone adds a triangle variant, what is left is no longer never, so the compiler points to every switch that must be updated. This is the exhaustiveness check.

Why 'algebraic'? Counting values

Because we can count the possible values like arithmetic. In a product the possibilities multiply; in a sum they add.

Comparing that number with the number of real states of your problem is an objective way to judge a model. A request is either loading, or a success with data, or a failure with a message: 3 states. If you model it as a record with loading, data and error all optional, you allow many meaningless combinations, such as 'loading and with an error'. Listing exactly the valid states as a sum type makes illegal states unrepresentable: the compiler refuses the invalid one, and no test is needed for it.

Pattern matching in Elixir

• `=` is the match operator, not assignment. The left side is a pattern: literals must be equal and variables are bound to the matching parts. {:ok, value} = {:error, :timeout} fails with a MatchError. Writing {:ok, value} = ... is a way of asserting success.
• Clauses are tried in order. A function with several clauses matches on its arguments, and the first clause that fits runs. Put specific cases first and the catch-all _ last. The compiler warns about a clause that can never be reached, but it never reorders anything.
• Lists are a recursive sum type. A list is either [] or [head | tail], a first item linked to the rest. After [head | tail] = [1], head is 1 and tail is [].
• The pin operator `^`. A variable in a pattern normally matches anything and is rebound. ^x binds nothing and demands a value equal to what x already holds.

Lazy evaluation

Normally a program is eager: it computes an expression the moment it sees it. With lazy evaluation, the program keeps only the recipe and cooks it when somebody asks for the result. That avoids useless work and lets you describe sequences that never end, as long as you only take a part of them.

Laziness in the three languages

• Elixir: the Enum module is eager, each function walks the whole collection and returns a finished list. The Stream module is lazy: Stream.map(list, f) returns a stream, which only describes the work. The work starts when the stream is handed to an Enum function such as Enum.to_list or Enum.take.
• JavaScript and TypeScript: a generator (function*) is a lazy sequence. Calling it runs nothing and returns an iterator. Each next() runs the body up to the next yield, hands over the value and pauses. That is why while (true) is fine: only what is asked for is computed.
• Java: a stream pipeline has a source, zero or more intermediate operations (filter, map, sorted) and one terminal operation (collect, sum, forEach, reduce). Intermediate ones are lazy. Only the terminal one starts the traversal. With no terminal operation, zero elements are processed.

function* naturals(): Generator<number> {
	let n = 1;
	while (true) {
		yield n;
		n += 1;
	}
}
const it = naturals();
it.next();
it.next();
console.log(it.next().value); // 3

Vertical against horizontal

An eager pipeline works horizontally: it finishes step one for all the elements, then step two for all. A lazy pipeline works vertically: it pulls one element through all the steps, then the next one. When the consumer stops early, a lazy pipeline does only the necessary work and builds no middle lists.

  eager (all of map, then all of filter):
      m1 m2 m3 m4  f1 f2 f3 f4

  lazy (one element at a time, stops at the first hit):
      m1 f1 | m2 f2 | m3 f3 -> found, stop
      (the element 4 is never touched)

In the same way, 1..1_000_000 |> Stream.map(...) |> Enum.take(2) runs the function on only the first two numbers. The consumer sets the amount of work: Enum.take(2) pulls one element at a time and halts the walk after the second.

Option and Result types, functors and monads by intuition

How should a function say 'I found nothing' or 'something went wrong'? Using null or throwing an exception hides this fact from the signature. Functional languages make absence and failure ordinary values in the type, so the compiler makes you deal with them.

Option

Option (also called Maybe or Optional) is a sum type with two variants: Some(value) and None. A function that returns Option<User> warns, in its signature, that the user may not exist. TypeScript has this built in: with strictNullChecks on, a function that returns string | undefined makes n.length a compile error until you check n. Without the option, undefined fits in every type and the error shows up only at run time.

Result

Result is the same idea for errors: Ok(value) or Error(reason). Failure is part of the contract. In Elixir the convention is {:ok, value} or {:error, reason}, and the caller decides with case or with. Functions that end in !, such as File.read!, raise an exception instead, for when failure is unexpected.

Functors: containers with a good map

map(f) on an Option applies f to the value inside, if there is one, and does nothing if the Option is empty. Your function only knows the happy case; the Option takes care of the other. You can think of an Option as a list with zero or one item. Arrays, Option, Result and promises all have such a map, and we call them functors: containers whose map transforms the content and keeps the shape. 'Well-behaved' means two laws: mapping the identity function changes nothing, and mapping f and then g equals mapping the composition of f and g.

Monads: chaining steps that can fail

What if the function you give to map itself returns an Option, like parse: string => Option<number>? Then map(parse) produces Option<Option<number>>, a box inside a box. flatMap (also called chain, bind or andThen) applies the function and flattens the result. Arrays behave the same: map with a function that returns arrays gives an array of arrays, and flatMap gives a flat array.

By intuition, a monad is a container with flatMap. With map the shape is fixed: only the content changes. With flatMap the function returns a new container, so a step can change the course of the next ones: an Option may become empty, a Result may become an error, an array may grow or shrink.

type Result<T> = { ok: true; value: T } | { ok: false; error: string };
const chain = <A, B>(r: Result<A>, f: (a: A) => Result<B>): Result<B> =>
	r.ok ? f(r.value) : r;
const half = (n: number): Result<number> =>
	n % 2 === 0 ? { ok: true, value: n / 2 } : { ok: false, error: 'odd ' + n };

// 12 -> 6 -> 3 -> half(3) fails
chain(chain(chain({ ok: true, value: 12 }, half), half), half);
// { ok: false, error: 'odd 3' }

In Elixir, with does this job. While each pattern matches, execution goes on and earlier variables are available. At the first step that does not match, the with returns that value and skips the rest. A promise's then plays both roles: if your function returns a plain value it acts like map, and if it returns another promise it acts like flatMap, waiting for it, so Promise.resolve(1).then(n => Promise.resolve(n + 1)) is a Promise<number>, not a promise of a promise.

Managing side effects

A program with no side effects would be useless: it could not read a file, answer a web request or show anything on screen. So functional programmers do not try to remove effects. They push them to the edge. The central idea is called functional core, imperative shell.

  +--------- imperative shell (thin) ---------+
  |  clock, random, files, network, database  |
  |        +--------------------------+       |
  |  in -> |   functional core        | -> out|
  |        |   pure: decide, compute, |       |
  |        |   validate, format       |       |
  |        +--------------------------+       |
  +--------------------------------------------+

The core receives plain data and returns plain data. The shell touches the world: clock, random generator, files, network, database and screen. A handy test to classify an operation: would it give the same result if repeated with the same values? If not, it belongs in the shell.

The gain: easy tests

Tests with effects are slow, fragile and need setup: start a database, fake the clock, clean up files. When the logic is in pure functions, each test is one call with values and one comparison. You get a wide base of fast tests for the core and only a few integration tests for the shell, which is so thin and free of decisions that a few are enough.

Two techniques

Explicit random state. A pseudo-random generator is a deterministic function of its internal state. The impurity comes from hiding that state in a global variable. If you make it explicit, next(state) returns {value, newState} and is pure. Keeping the seed (the starting state) is enough to replay a failing run. Erlang and Elixir follow this model in :rand.uniform_s and similar functions.

Effects as data. The core does not send the e-mail. It returns a description of what to do, and the shell carries it out:

type Effect = { type: 'sendEmail'; to: string };

function decide(state: State, cmd: Command): Effect[] {
	return [{ type: 'sendEmail', to: 'ana@example.test' }];
}
// shell: for (const e of decide(s, c)) perform(e);

The description can be compared, logged, filtered or replayed. It is the idea behind Elm, Redux and the 'commands' of event-driven systems.

Where does changing state live in Elixir?

Data is immutable, but a server process, such as a GenServer, does keep state that changes over time. A process is a loop: it waits for a message, computes the reply and the next state, and calls itself again with that state, through a tail call. The 'mutable state' is just the sequence of arguments of those calls. The effect is confined to the process, access is serialised by its mailbox, and the callbacks that compute the next state can be pure and tested directly.

Functional style in Elixir and TypeScript

Elixir was built for functional style, so good habits come for free. TypeScript lets you write both ways, so you must choose well. Here are the details that most often surprise people.

Copying methods and in-place methods in JavaScript

xs.sort(...) changes xs and also returns it. So const ys = xs.sort(...) gives you one array with two names, and xs === ys is true. Use xs.toSorted(...) or sort a copy with [...xs].sort(cmp). Typing parameters as readonly T[] lets the compiler stop you from mutating.

Another trap: sort without a comparison function compares the text form of the items. So [10, 9, 1].sort() gives [1, 10, 9]. A test with single-digit examples would not notice. A property such as 'each element is less than or equal to the next', tested with generated inputs, finds it quickly.

Elixir details

• Pipe. c(b(a(x))) is written x |> a() |> b() |> c(). The data goes first and each line is one step.
• Capture operator `&`. &(&1 * 2) makes an anonymous function in which &1 is the first argument. With a name and arity, &String.upcase/1 turns a named function into a value. Both are used to pass functions to Enum.map and friends: Enum.map([1, 2, 3], &(&1 * 2)) gives [2, 4, 6].
• `Enum` on maps returns lists. Enum works on anything that implements the Enumerable protocol (lists, maps, ranges, streams) but returns lists. Enum.map(%{a: 1}, fn {k, v} -> {k, v * 2} end) gives [a: 2], a list of pairs. To get a map back, use Map.new(map, fn {k, v} -> {k, v * 2} end). With more than one key, do not rely on the order in which a map is walked.
• TypeScript's `map` exists only on arrays and always returns an array.

Putting it all together

All the ideas lean on each other. Immutable data makes functions pure. Pure functions can be memoised, tested without mocks and run in parallel. Because functions are values, we can pass them (higher-order), remember variables (closures), fix arguments (currying) and connect them (composition). With no mutable counters, repetition is recursion. Sum types make illegal states unrepresentable, and Option and Result make failure visible. Laziness saves work, and the functional core keeps the unavoidable effects in the shell.

  immutable data --> pure functions --> easy tests, parallel, memoise
          |                  |
          v                  v
   recursion, reduce    composition, currying, map/filter
          |                  |
          +----> ADTs, Option/Result <---+
                         |
                         v
          functional core + imperative shell

Common mistakes

• Thinking const makes an object immutable. It only stops the name from being reassigned.
• Thinking that a deterministic function is automatically pure. Printing is an effect.
• Using Enum.each with a variable to accumulate in Elixir. Use Enum.reduce.
• Using list ++ [x] in a loop. It copies the whole list every time.
• Expecting a tail-recursive function to be safe in Node.js for a million steps.
• Forgetting that xs.sort() changes xs.