Functional Programming Cheatsheet

Comprehensive cheatsheet of fundamental and intermediate concepts in functional programming.

đź’ˇ Note: While the following code examples are in TypeScript, the concepts are applicable to any language that supports functional programming.

Fundamental Concepts

Functions

A function is a mapping between types.

// square :: number -> number
function square(x: number): number {
  return x * x;
}

Immutability

A mutable value can be changed after it’s created.

let x = 42;
x = 43; // ok

An immutable value cannot be changed after it’s created. Instead of modifying existing data, create new values.

const x = 42;
x = 43; // TypeError: Assignment to constant variable.

Higher-Order Functions

A higher-order function is a function that takes one or more functions as arguments or returns a function as its result.

/* 
* map is a higher-order function 
* because it takes a function as an argument
*/
[1, 2, 3].map((x) => x * 2);

Pure Functions

A pure function has no side effects and always returns the same result for the same input.

/* 
* add is a pure function 
* add(2,3) always returns 5
*/
function add(a, b) {
  return a + b;
}

Side Effects

A side effect is any change to state or anything observable outside the function’s scope.

let counter = 0;
function incrementCounter(x) {
  counter += x;
  return counter;
}

Referential Transparency

A referentially transparent expression can be replaced with its result without changing the behavior of the program.

/* 
* add is a referentially transparent function
* add(2,3) can be replaced with 5 
* without changing the behavior of the program
*/
function add(a, b) {
  return a + b;
}

Currying

Currying is transforming a function that takes multiple arguments into a sequence of functions that each take a single argument.

// original version
const add = (a, b) => a + b;

// curried version
const add_ = (a) => (b) => a + b;

add(1, 2); // 3
add_(1)(2); // 3

Partial Application

Partial application is a technique where a curried function is called with fewer arguments than it expects.


const add = (a) => (b) => a + b;
const add3 = add(3);

add3(2); // 5

Function Composition

Function composition is combining two or more functions to create a new function where the output of one function becomes the input of the next.

const add2 = x => x + 2;
const multiply3 = x => x * 3;

// compose functions right to left
const compose = (f, g) => x => f(g(x));
const fun = compose(multiply3, add2);

fun(4); // (4 + 2) * 3 = 18

Common Operations

It is common in functional programming to use one-word verbs to name functions.

  • Most functions use imperative form: map, tap, pop, drop, etc.
  • Boolean functions usually use present tense: includes, has, isEmpty, etc.
  • “Getter” functions are sometimes nouns: head, tail, last, prop, etc.

apply

Calls a function with given value(s).

Math.max.apply(null, [1, 2, 3]); // 3
Math.max(1, 2, 3); // 3

compose

Combines functions from right to left. The result of each function is passed as an argument to the next function.

const add2 = x => x + 2;
const multiply3 = x => x * 3;

// compose functions right to left
const compose = (f, g) => x => f(g(x));
const fun = compose(multiply3, add2);

fun(4); // (4 + 2) * 3 = 18

đź’ˇ compose is like pipe but right to left.

drop

Drops the first n elements from a collection. Inverse of take.

const numbers = [1, 2, 3, 4, 5];
drop(2, numbers); // [3, 4, 5]

filter

Returns a new collection containing only the elements that satisfy a predicate function.

const numbers = [1, 2, 3, 4, 5, 6];
const isEven = x => x % 2 === 0;

// [2, 4, 6]
numbers.filter(isEven); 

const users = [
  { name: 'Alice', age: 25 },
  { name: 'Bob', age: 17 },
  { name: 'Carol', age: 30 }
];

// ['Alice', 'Carol']
users
  .filter(user => user.age >= 18) 
  .map(user => user.name)

const words = [
  'hello', 
  'world', 
  'functional', 'programming'
];

// ['functional', 'programming']
words.filter(word => word.length > 5);

flatten

Transforms a collection of collections into a flat collection. Also known as flat.

const nested = [1, [2, 3], [4, 5, 6]];
nested.flat(); // [1, 2, 3, 4, 5, 6]

flatMap

Maps over a collection then flattens it.

const numbers = [1, 2, 3];
const duplicate = (x) => [x, x];
numbers.map(duplicate); // [[1, 1], [2, 2], [3, 3]]
numbers.map(duplicate).flat(); // [1, 1, 2, 2, 3, 3]
numbers.flatMap(duplicate); // [1, 1, 2, 2, 3, 3]

đź’ˇ flatMap is also known as bind, chain, and join.

Returns the first element of a collection.

const numbers = [1, 2, 3];
head(numbers); // 1

const empty = [];
head(empty); // undefined

// With strings
const text = "hello";
head(text); // "h"

has

Checks if an Object or Record has a given key or property.

const user = new Map();
user.set('name', 'Alice');
user.set('age', 30);

user.has('name'); // true

includes

Checks if a collection contains a given value.

const numbers = [1, 2, 3, 4, 5];
numbers.includes(3); // true

const text = "hello";
text.includes("e"); // true

last

Returns the last element of a collection.

const numbers = [1, 2, 3, 4, 5];
last(numbers); // 5

const text = "hello";
last(text); // "o"

map

Transforms each element in a collection using a function and returns a new collection with the results.

const numbers = [1, 2, 3, 4];
numbers.map(x => x * 2); // [2, 4, 6, 8]

// With objects
const users = [
  { name: 'Alice', age: 25 },
  { name: 'Bob', age: 30 }
];
users.map(user => user.name); // ['Alice', 'Bob']

pick

Creates an object composed of the picked object properties.

const user = { name: 'Alice', age: 30, email: 'alice@example.com' };
pick(['name', 'email'], user); // { name: 'Alice', email: 'alice@example.com' }

pipe

Similar to compose but combines functions from left to right.

const add2 = x => x + 2;
const multiply3 = x => x * 3;

// compose functions left to right
const fun = pipe(add2, multiply3);

fun(4); // (4 + 2) * 3 = 18

prop

Retrieves a property from an object by its path.

const user = { 
  info: { 
    name: 'Alice',
    address: { city: 'New York' } 
  } 
};

prop('info.name', user); // 'Alice'
prop(['info', 'address', 'city'], user); // 'New York'

reduce

Reduces a collection into a single value by applying a function to each element and accumulating the results.

[1, 2, 3, 4].reduce((sum, n) => sum + n, 0); // 10

const cart = [
  { item: 'Book', price: 10 },
  { item: 'Pen', price: 2 }
];
cart.reduce((total, item) => total + item.price, 0); // 12

reject

Returns a new collection excluding elements that satisfy a predicate function.

const numbers = [1, 2, 3, 4, 5, 6];
function isEven(x) {
  return x % 2 === 0;
}
reject(isEven, numbers); // [1, 3, 5]

đź’ˇ reject is like filter but inverts the predicate.

return

Returns a value wrapped in a monadic container.

Monadic return is not to be confused with the return keyword or statement in traditionally imperative languages.


// Array.of is `return` operation
const x = 42;
const a = Array.of(x);
const a_ = [x]; // shorthand for Array.of(x)

// Promise.resolve is `return` operation
const x = 42;
const p = Promise.resolve(x);

take

Takes the first n elements from a collection. Inverse of drop.

take(2, [1, 2, 3, 4]); // [1, 2]

tap

Executes a function with the value and returns the value unchanged. Useful for side effects like logging.

const addTwoAndLog = pipe(
  addTwo,
  tap(console.log), // logs 6
  multiplyByThree
);

addTwoAndLog(4); // 18

tail

Returns all elements of a collection except the head.

tail([1, 2, 3]); // [2, 3]
tail([1]); // []
tail("hello"); // "ello"

zip

Combines two collections into an collection of pairs.

// [[1, 'a'], [2, 'b'], [3, 'c']]
zip([1, 2, 3], ['a', 'b', 'c']);

Intermediate Concepts

Abstract Data Types

A type is a set of values and operations on those values.

An abstract data type (ADT) is a conceptual type that is language-agnostic and defined by its behavior (operations) rather than its implementation (data representation).

Bag

A bag (also known as multiset) is a collection that allows duplicate elements and doesn’t maintain order.

Example: A shopping cart is a Bag because it allows multiple items of the same type.

đź’ˇ A Bag is like a Set but allows duplicates.

Graph

A graph is a collection of nodes connected by edges.

Example: A social network is a Graph. Users and posts are nodes. Likes and follows are edges.

đź’ˇ A Graph is like a Tree but can have multiple paths between nodes.

List

A list is an abstract data type that represents an ordered, finite collection of values.

Example: A train is a List. Each car is an element linked to the next car.

Map

A map (also known as dictionary) is a collection of key-value pairs where each key appears only once.

Example: A user database is a Map. Users are identified by a unique ID.

Queue

A queue is a collection that where elements are added at the end and removed from the front.

Example: The checkout line at a store is a Queue.

Set

A set is a collection of distinct elements where order doesn’t matter and duplicates are not allowed.

Example: A deck of cards is a Set. Each card appears only once.

đź’ˇ A Set is like a Bag but all elements are unique.

Stack

A stack is a collection where elements are added and removed from the top.

Example: A stack of plates in a cafeteria dispenser. You can only take the top plate, and new plates must be added to the top.

đź’ˇ A Stack is like a Queue except elements are added and removed from the top.

Tree

A tree is a hierarchical data structure consisting of nodes connected by edges, with one root node and no cycles.

Example: A family tree is a Tree.

đź’ˇ A Tree is like a Graph but has one root node and does not allow cycles.

Functors

A functor, roughly speaking, is a container type that implements map and preserves structure during transformation.

// Array is a functor because it implements map
const numbers = [1, 2, 3];
const doubled = numbers.map(x => x * 2); // [2, 4, 6]

Monads

A monad, roughly speaking, is a functor that implements flatMap and return.

For example, the JavaScript Array is a monad because it implements flatMap and return.

const duplicate = x => [x, x];

// Array literal is `return` operation
const numbers = [1, 2]; 

// `flatMap` operation
numbers.flatMap(duplicate); // [1, 1, 2, 2]

đź’ˇ See: Caveman Explains Monads

Either

A monad that represents values with two possibilities.

Either has two variants:

  • Left(_): An error is present.
  • Right(_): A value is present.

Note that variants are not types. Here, they’re just two sides of the same coin.

Example: A coin flip is Either where Left is heads and Right is tails.

Future & Promise

Futures and Promises are two related concepts that represent asynchronous computations.

You can make a Promise and it’s up to you to keep it. When someone else makes you a promise you must wait to see if they honour it in the Future (source).*

async function fetchUser(id): Promise<User> {
  const response = await fetch(`/users/${id}`);
  return response.json();
}

List

List is a monad that represents an ordered, finite collection of values which can be mapped or flatMapped over.

Option & Maybe

A monad that represents optional values. Also known as Maybe.

Option has two variants:

  • Some(_): A value is present. Some is also known as Just.
  • None: No value is present. None is also known as Nothing.

Note that Some and None are not types. They are two variants of the same type.

đź’ˇ Option is a subset of Either where the Left variant is None and the Right variant is Some.

Result

A subset of Either that represents fallible computations.

Result has two variants:

  • Ok(_): Operation succeeded and a value is present.
  • Error(_): Operation failed and an error is present.

Algebraic Data Types

An algebraic data type is a composite type made from combining other types. There are two main ways to combine types:

Product Types

A product type combines multiple fields where all fields must be present. The term product comes from the Cartesian product of sets.

Tuple

A tuple is a finite, ordered sequence of values. It is a product type.

enum Suit {
  // ...
}

enum Rank {
  // ...
}

// This Card is a Tuple
type Card = [Suit, Rank];
Record & Struct

A Record, also known as a Struct, is a product type with a fixed set of fields.

enum Suit {
  // ...
}

enum Rank {
  // ...
}

// This Card is a Record
type Card = {
  suit: Suit;
  rank: Rank;
};

Sum Types

A sum type represents variants where one of the possibilities must be chosen. The term sum comes from the sum of sets.

Enum

An enum is a sum type with a fixed set of variants.

enum Suit {
  Hearts,
  Diamonds,
  Clubs,
  Spades
}
Tagged Union

A tagged union is a sum type with a fixed set of variants that are tagged with a string or symbol.

type Suit = 
  | "Hearts"
  | "Diamonds"
  | "Clubs"
  | "Spades";
Either

Either is a sum type with two variants: Left and Right.

Option

Option is a sum type with two variants: Some and None.

Result

Result is a sum type with two variants: Ok and Error.