Notes on functional programming (I)

Functional programming is an interesting area covering from general purpose operations to some specialized techniques. Operations like currying, piping or transducing are part of a paradigm that allow us to minimize shared state in our applications, write readable code and make easier to write tests.

For this series we will use a simple and common language: Javascript. It is not a pure functional language, and it lacks of many data structures and characteristics required for functional programming. Thus, we will need to implement them, which will teach us a lot about the essence of this paradigm.

We will cover this topic as a kind of notes for newcomers interested in functional programming, but also for my future self. And we will do it in two articles: here I will layout the the most basic concepts and operations involved in functional programming. We will talk about:

  • Inmutability
  • Purity
  • Arity
  • Currying
  • Partial application
  • Point free style
  • Compose and pipe
  • Eager vs Lazy evaluation

We will go through each of them, with clear examples in Javascript to keep everything simple.

In a second article we will cover composing again, but this time fwith focus on their relation to transducers.

Inmutability

One of the main issues in programming is shared state.

Lets say we are in Javascript, and we have an object with a property a that is saved in the variable x with some value. Now we copy x into y, which means that we save the reference of x into y. Everything that we do to y we will to to x as well. This is problematic, as we may change x in unexpected ways.

language-javascript

⁠const john = { id: 1, name: "john" };
const bob = john;
⁠bob.name = "bob";
⁠console.log(john); // { id: 1, name: "bob" }
Run me in Playground 

To fix this issues we can just spread the properties of john with the spread operator ... into a new object bob:

language-javascript

⁠const john = { id: 1, name: "john" };
⁠const bob = { ...john, name: "bob" ⁠};
⁠console.log(john); // { id: 1, name: "john" }
Run me in Playground 

Another example would be when dealing with concurrent operations. In this case we have a computing operation A, whose result is stored in the variable x. We also have operation B, which computes a new value, storing it again in x. The result is shared state: x holds the value both of A and B. If now A and B are concurrent —which means that we can not ensure the order in which they may happen— we have a program difficult to follow, as we wont know the value of x at each step.

language-javascript

⁠let x = 0;

⁠function operationA(a, b) {
⁠ setTimeout(() => (x = a + b), Math.random() * 200);
⁠}

⁠function operationB(a, b) {
⁠ setTimeout(() => (x = a * b), Math.random() * 200);
⁠}

⁠operationA(2, 3);
⁠operationB(2, 3);

⁠// x == 5 or x == 6?

setTimeout(() => console.log("x:", x), 500); // 5 or 6
Run me in Playground 

This may be solved easily by removing the shared state and keeping each result in a different variable:

⁠language-javascript

⁠const operationA = (a, b) =>
⁠ new Promise((resolve) => {
⁠ setTimeout(() => resolve(a + b), Math.random() * 200);
⁠ });

⁠const operationB = (a, b) =>
⁠ new Promise((resolve) => {
⁠ setTimeout(() => resolve(a * b), Math.random() * 200);
⁠ });

⁠const asyncOperationA = operationA(2, 3); // x == 5
⁠const asyncOperationB = operationB(2, 3); // x == 6

Promise.race([asyncOperationA, asyncOperationB]).then((value) => {
console.log(value);
⁠}); // 5 or 6
Run me in Playground 

This new version of our program will be easier to reason about and debug, as we can access the values stored in memory at each step.

Purity

Functional programming aims for simplicity and predictability, thus the heavy usage of functions. But for functions to be predictable, given the same input they need to return the same output. In this sense a function is an inmutable relation between two sets: input and output, and this relation should not change.

language-javascript

⁠const pureFunction = (a, b) => a < b;
⁠console.log(pureFunction(1, 2)); // true
⁠const impureFunction = (a, b) => (Math.random() > 0.5 ? a < b : a > b);
⁠console.log(impureFunction(1, 2)); // true or false
Run me in Playground 

Purity empowers predictability, but also allows us to memoize function result, avoiding uneeded computations.

Arity

Arity is a term refering to the number of parameters a function receives:

  • A function has arity 0 when does not receive any parameter: it is nullary.
  • A function has arity 1 when receives only one parameter: it is unary.
  • A function has arity 2 when receives two parameters: it is binary.
  • A function has arity n when it may receive any number of parameters: it is n-ary —also known as variadic.
language-javascript

⁠const nullaryFunction = () => "Hello world";
⁠console.log(nullaryFunction()); // hello world

⁠const unaryFunction = (greeting) => `${greeting} world`;
⁠console.log(unaryFunction("hello")); // hello world

⁠const binaryFunction = (greeting, subject) => `${greeting} ${subject}`;
⁠console.log(binaryFunction("hello", "world")); // hello world

⁠const nAryFunction = (...strings) =>
⁠ strings.reduce((acc, curr) => `${acc}${curr} `, "");
⁠console.log(nAryFunction("hello", "world", "and", "pluton"));
⁠// hello world and pluton
Arities, run me in Playground 

Nothing special here, just another term: but an important one, as unary functions are at the core of some functional programming operations.

Currying

Currying is the process to transform a function that takes several parameteres —arity greater han one— into several unary nested functions —remember, functions that take one parameter at a time—.

language-javascript

⁠// Non curried function
⁠const sum = (a, b, c) => a + b + c;
⁠const result = sum(1, 2, 3);
⁠console.log(result); // 6

⁠// Curried function
⁠const sum = (a) => (b) => (c) => a + b + c;
⁠⁠const result = sum(1)(2)(3);
⁠console.log(result); // 6
Currying, run me in Playground 

As we will see later this is a key technique in functional programming: as we will see there are many operations where we need all functions with similar footprint —one input, one output—, allowing combining them in different forms.

Partial application

Partial application is the process of transforming a function taking several parameters into another function getting some of these parameters, and returing a new function taking the rest of parameters, and combining them with the pre-fixed ones.

This is really useful, as it allow us creating functions with preapplied parameters. Which means facilitating function specialization.

For example, lets say we have a createUrl function that receives three string parameters: protocol, domain and path, returning one string combining them.

language-javascript

⁠const createUrl = (scheme, domain, path) => `${scheme}://${domain}/${path}`;

⁠const httpUrl = createUrl("http", "example.com", "hello");
⁠console.log(httpUrl); // "http://example.com/hello"

⁠const httpsUrl = createUrl("https", "example.com", "hello");
⁠console.log(httpsUrl); // "https://example.com/hello"
Run me in Playground 

We probably use this function in many places in our codebase with either "http" or "https". To be more declarative and avoid passing the scheme everytime we need an url we can create two new specialized versions of createUrl: createHttpUrl and createHttpsUrl, by fixing the scheme parameter within the scope of each of these functions.

language-javascript

⁠const createUrl = (scheme, domain, path) => `${scheme}://${domain}/${path}`;

⁠// Partial application: fixing `scheme` parameter
⁠const createUrlWithProtocol = (scheme) =>
⁠ (domain, path) => createUrl(scheme, domain, path);
⁠⁠
⁠⁠const createHttpUrl = createUrlWithProtocol("http");
⁠const createHttpsUrl = createUrlWithProtocol("https");

⁠const httpUrl = createHttpUrl("http", "example.com", "hello");
⁠console.log(httpUrl); // "http://example.com/hello"

⁠⁠const httpsUrl = createHttpsUrl("https", "example.com", "hello");
⁠console.log(httpsUrl); // "https://example.com/hello"
With partial application, run me in Playground 

The new functions are more expressive semantically as well as more efficient, as we reduced the arity of the functions we use to create our urls.

Point-free style

Point-free is a functional programming style where functions are processed without mentioning their parameters —points—.

Lets see an example. When passing functions as parameters to another functions it is common to inline them:

language-javascript

⁠const userName = users.map(
⁠ ({ first, lastName }) => `${first} ${lastName}`
⁠);
With parameters

In point-free style we would extract the function declaration to save it into a variable, which we will pass around:

language-javascript

⁠const composeName = ({ first, lastName }) => `${first} ${lastName}`;
⁠const userName = users.map(composeName⁠);
Point-free style

In general point-free style is more declarative and readable, facilitating function composition as will see.

Compose and pipe

In algebra "function composition" refers to the process of transforming a sequential set of unary functions into nested ones, so the result of one function will be passed as parameter to the one wrapping it.

Lets say we have two functions:

f(x) = 2x\\ ⁠⁠g(x) = x^2

⁠We express that we compose them with the syntax:

f \circ g =(g(x))

Which means that we execute g(x) first, and then f(x) with its result.

It is important to note that function composition is not commutative:

f \circ g \neq g \circ f

although it is associative:

f \circ (g \circ h) = (f \circ g) \circ h

We can translate all this to a programming language easily, as in Javascript functions are first class citizens. This means that we can treat them as variables, so any function may accept another function as parameter.

Given two functions we would be able to execute one within the other:

language-javascript

⁠⁠const f = (x) => x * 2;
⁠const g = (x) => x * x;

⁠const result = f(g(3));
⁠console.log(result); // 18
Run me in Playground 

Lets say this kind of operation is something we do a lot: it would be nice if we had an utility function that, given two functions, returns them composed:

⁠language-javascript

⁠const f = (x) => x * 2;
⁠const g = (x) => x * x;

⁠const compose = (f, g) => (x) => f(g(x));

⁠const composed = compose(f, g);
⁠const resultComposed = composed(3); // 18
Run me in Playground 

In this case we have a function receiving two parameters —arity 2—, doing partial application to fix them within the closure, and will return another function that will use them along with another parameter it will require.

⁠This way, the returned function is saved in the variable composed, which will have f and g in its scope, and will make use of them when it is called with another parameter —3—.

Now lets say we want to compose three functions:

f \circ g \circ h = f(g(x))

We can write this following the same logic, but creating a compose function of arity 3:

language-javascript

⁠const f = (x) => x * 2;
⁠⁠const g = (x) => x * x;
⁠const h = (x) => x - 1;

⁠const compose = (f, g, h) => (x) => f(g(h(x)));

⁠const composed = compose(f, g, h);
⁠console.log(composed(3)); // 8
Run me in Playground 

It works nicely; but this is not very scalable. The next step would be to create a n-ary function that, given any number of functions passed as parameters, returns them composed:

language-javascript

⁠const f = (x) => x * 2;
⁠⁠const g = (x) => x * x;
⁠const h = (x) => x - 1;

const compose = (...fns) => (x) =>
⁠ fns.reduceRight((acc, curr) => curr(acc), x);

⁠const composed = compose(f, g, h);
⁠console.log(composed(3)); // 8
Run me in Playground 

This function receives any number of functions as individual parameters. Then spreads them into an array with the spread operator ..., and will fix them within the closure, returning a new function. This new function will be of arity 1, receiving as parameter the data to process with our functions. Finally it will iterate our array of functions starting right-to-left executing them, meaning it will run the last one first using the provided initial data.

What we just did is to create a compose function: a n-ary utility useful to compose any number of functions as long as they are unary.

Now lets say we want to compose our functions starting from the first one to the last one: instead of Array.reduceRight we can just use Array.reduce:

language-javascript

⁠const f = (x) => x * 2;
⁠⁠const g = (x) => x * x;
⁠const h = (x) => x - 1;

const pipe = (...fns) => (x) =>
fns.reduce((acc, curr) => curr(acc), x);

⁠const piped = pipe(f, g, h);
⁠console.log(piped(3)); // 35
Run me in Playground 

This is called a pipe function. And as function composition is not commutative it returns a different result to compose.

Eager vs Lazy evaluation

Eager evaluation is the inmediate computation of an expression as soon as it is encountered.

For example, in Javascript:

language-javascript

⁠⁠const sum = (a, b) => a + b;
const result = sum(1, 2); // Computed here
⁠console.log(result); // 3
Run me in Playground 

As we see, the expression is evaluated when the function is called, not when its result is used.

Lazy evaluation, on the contrary, delays the computation until its result is used.

Javascript does not support lazy evaluation natively, but it can be implemented in certain ways. With functions for example, or by using generators:

language-typescript

⁠function* lazySum(a, b) {
⁠ yield a + b;
⁠}

⁠let result = lazySum(1, 3); // computation delayed
⁠console.log(result); // not evaluated yet
⁠console.log(result.next().value); // 4
Run me in Playground 

Here the sum is not executed when lazySum is called, but when we use the result by calling next().

Conclusion

This is everything for today. All these operations and concepts are common ground for anyone working nowadays: but they will lay the foundations of what is coming next: transducers.

Stay tuned!