filter, map and reduce

2022-09-14

javascript functional filter map reduce

~~This week~~ When I started writing this article a crazy idea came to me: would it be possible to implement a relational database using only map, filter and reduce?

The answer is: It is possible, and my implementation can be found ~~in this repository~~. Keep in mind that this implementation is just a creative exercise, so don't blame me for it not being a complete database.

Now let's get straight to the point: The goal of this article is to explain through examples how to use filter, map and reduce in common situations a programmer faces.

The array

An array is a data structure where elements are arranged sequentially in memory and one of its properties is direct access to elements by index. Something like the example below:

let arr = ["manga", "melancia", "abacate"];
console.log(arr[2]);

// output:
// melancia

This operation is extremely fast and has O(1) complexity. However, finding the index from a value is not equally trivial, since in the worst case you need to visit every item in the structure to find the index, as demonstrated below:

let target = "abacate";
let arr = ["manga", "melancia", "abacate"];

let i;
for (i = 0; i < arr.length; i++) {
    if (arr[i] == "abacate")
        break;
}

console.log(i, arr[i]);

// output:
// 2 abacate

Keep in mind that the algorithm above was written for illustration purposes only and the same result can be achieved with indexOf and find, or even with filter at position 0:

let arr = ["manga", "melancia", "abacate"];
console.log(arr.indexOf("abacate"));
console.log(arr.find(x => x == "abacate"));
console.log(arr.filter(x => x == "abacate")[0]);
console.log(arr.includes("abacate"));

// output:
// 2
// abacate
// abacate
// true

We should note that all functions above have O(n) complexity.

restructuring the array

Besides functions focused on element search, such as indexOf, find, filter and includes, there are also functions for converting the array into a new array with values derived from the original values, or even for converting the array into another type of variable.

In the example below, map is used to convert an array of strings into an array of objects with a property containing the original string and a second property containing its length.

let arr = ["manga", "melancia", "abacate"];
arr.map(x => ({
    txt: x,
    ct: x.length
}));

// output:
// [
//  { txt: 'manga', ct: 5 },
//  { txt: 'melancia', ct: 8 },
//  { txt: 'abacate', ct: 7 }
// ]

In this second example, reduce is used to sum and multiply all string lengths in an array.

let arr = ["manga", "melancia", "abacate"];
console.log(arr.reduce((ac, v) => ac + v.length, 0));
console.log(arr.reduce((ac, v) => ac * v.length, 1));

// output:
// 20
// 280

You can also use this technique to index an array of strings by turning it into an object with the same string as key.

let arr = ["manga", "melancia", "abacate"];

let obj = arr.map(x => ({
    txt: x,
    ct: x.length
})).reduce((ac, v) => {
    ac[v.txt] = v;
    return ac
}, {});

console.log(obj);

// output:
// {
//  manga: { txt: 'manga', ct: 5 },
//  melancia: { txt: 'melancia', ct: 8 },
//  abacate: { txt: 'abacate', ct: 7 }
// }

Finally, you can use the Map data structure to make the above example more compact and performant.

let arr = ["manga", "melancia", "abacate"];

let obj = arr.map(x => ({
    txt: x,
    ct: x.length
})).reduce((ac, v) => ac.set(v.txt, v), new Map);

console.log(obj);

// output:
// Map(3) {
//  'manga' => { txt: 'manga', ct: 5 },
//  'melancia' => { txt: 'melancia', ct: 8 },
//  'abacate' => { txt: 'abacate', ct: 7 }
// }

What about the database?

For this simplification of the database concept, I'm considering arrays of objects as tables and completely ignoring insert operations since they are obvious. So, for this article, we'll use the "database" below:

let into_table = (table) => (nome, id) => ({
    [table]: {
        nome,
        id
    }
});

let alunos = ["alice", "claudia", "luiz", "joao"]
    .map(into_table("aluno"));

let turmas = ["quimica", "engenharia", "letras", "fisica"]
    .map(into_table("turma"));

console.log("alunos = ", alunos);
console.log("turmas = ", turmas);

// output:
// alunos = [
//  { aluno: { nome: 'alice', id: 0 } },
//  { aluno: { nome: 'claudia', id: 1 } },
//  { aluno: { nome: 'luiz', id: 2 } },
//  { aluno: { nome: 'joao', id: 3 } }
// ]
// turmas = [
//  { turma: { nome: 'quimica', id: 0 } },
//  { turma: { nome: 'engenharia', id: 1 } },
//  { turma: { nome: 'letras', id: 2 } },
//  { turma: { nome: 'fisica', id: 3 } }
// ]

random enrollments

In the previous example the students and classes tables were defined, but the relationship between them has not been defined yet. So, let's use Array(8) to create an array with 8 positions, then use .fill(0) to fill each item with zero. This is necessary because .map ignores elements with undefined values. Finally, we'll use .map to convert this array of zeros into an array of objects whose structure contains randomly generated primary keys for student and class.

let rand = (ct) => Math.floor(Math.random() * ct);

let matriculas = Array(16)
    .fill(0)
    .map(x => ({
        matricula: {
            aluno: rand(alunos.length),
            turma: rand(turmas.length)
        }
    }));

console.log("matriculas = ", matriculas);

// output: 
// matriculas = [
//  { matricula: { aluno: 3, turma: 1 } },
//  { matricula: { aluno: 3, turma: 1 } },
//  { matricula: { aluno: 3, turma: 1 } },
//  { matricula: { aluno: 1, turma: 0 } },
//  { matricula: { aluno: 0, turma: 2 } },
//  { matricula: { aluno: 0, turma: 2 } },
//  { matricula: { aluno: 1, turma: 1 } },
//  { matricula: { aluno: 2, turma: 2 } },
//  { matricula: { aluno: 1, turma: 3 } },
//  { matricula: { aluno: 3, turma: 1 } },
//  { matricula: { aluno: 0, turma: 3 } },
//  { matricula: { aluno: 1, turma: 1 } },
//  { matricula: { aluno: 1, turma: 2 } },
//  { matricula: { aluno: 0, turma: 3 } },
//  { matricula: { aluno: 1, turma: 2 } },
//  { matricula: { aluno: 3, turma: 1 } }
// ]

removing duplicate enrollments

To remove duplicate entries we can use a technique that consists of converting the Array into a Map indexed by the key we want to make unique and obtaining the final result through the .values() method.

matriculas = Array.from(
    matriculas
    .reduce(
        (ac, v) => ac.set(
            v.matricula.aluno + "|" + v.matricula.turma,
            v
        ),
        new Map
    )
    .values()
);

console.log("matriculas = ", matriculas);

// output: 
// matriculas = [
//  { matricula: { aluno: 3, turma: 1 } },
//  { matricula: { aluno: 1, turma: 0 } },
//  { matricula: { aluno: 0, turma: 2 } },
//  { matricula: { aluno: 1, turma: 1 } },
//  { matricula: { aluno: 2, turma: 2 } },
//  { matricula: { aluno: 1, turma: 3 } },
//  { matricula: { aluno: 0, turma: 3 } },
//  { matricula: { aluno: 1, turma: 2 } }
// ]

Cartesian product (join)

One of the most common operations in databases is the Cartesian product. In mathematics, this operation consists of obtaining all possible combinations between elements of two or more distinct sets. The algorithm below does exactly that with the "tables" students and classes.

let join = (a, b) =>
    a.map(x => b.map(y => ({
        ...x,
        ...y
    })))
    .reduce((ac, it) => ac.concat(it), []);

console.log("prod = ", join(alunos, turmas));

// output: 
// prod = [
//  {
//  aluno: { nome: 'alice', id: 0 },
//  turma: { nome: 'quimica', id: 0 }
//  },
// ...
//  {
//  aluno: { nome: 'claudia', id: 1 },
//  turma: { nome: 'fisica', id: 3 }
//  },
// ...
//  { 
//  aluno: { nome: 'joao', id: 3 },
//  turma: { nome: 'fisica', id: 3 }
//  }
// ]

product of n tables

And, with a new reduce, we can reuse the join function to obtain the Cartesian product of n tables.

let join_all = (all) =>
    all.slice(1)
    .reduce((ac, v) => join(ac, v), all[0]);

console.log("join_all = ", join_all([
    alunos, turmas, matriculas
]));

// output:
// join_all = [
//  {
//  aluno: { nome: 'alice', id: 0 },
//  turma: { nome: 'quimica', id: 0 },
//  matricula: { aluno: 3, turma: 1 }
//  },
//  {
//  aluno: { nome: 'alice', id: 0 },
//  turma: { nome: 'quimica', id: 0 },
//  matricula: { aluno: 1, turma: 0 }
//  },
//  {
//  aluno: { nome: 'alice', id: 0 },
//  turma: { nome: 'quimica', id: 0 },
//  matricula: { aluno: 0, turma: 2 }
//  },
//  ...
//  {
//  aluno: { nome: 'claudia', id: 1 },
//  turma: { nome: 'fisica', id: 3 },
//  matricula: { aluno: 1, turma: 3 }
//  },
//  ...
//  {
//  aluno: { nome: 'luiz', id: 2 },
//  turma: { nome: 'letras', id: 2 },
//  matricula: { aluno: 1, turma: 0 }
//  },
//  ...
// ]

queries

To make the Cartesian product useful, you can add conditions with the filter method, turning the result into a query.

let result = join_all([alunos, matriculas, turmas])
    .filter(x => x.matricula.aluno == x.aluno.id)
    .filter(x => x.matricula.turma == x.turma.id);

console.log("prodn aluno, matricula, turma: ", result);

// output:
// prodn aluno, matricula, turma: [
//  {
//  aluno: { nome: 'claudia', id: 1 },
//  matricula: { aluno: 1, turma: 1 },
//  turma: { nome: 'enfermagem', id: 1 }
//  },
//  {
//  aluno: { nome: 'claudia', id: 1 },
//  matricula: { aluno: 1, turma: 3 },
//  turma: { nome: 'letras', id: 3 }
//  },
//  {
//  aluno: { nome: 'claudia', id: 1 },
//  matricula: { aluno: 1, turma: 0 },
//  turma: { nome: 'sistemas de informação', id: 0 }
//  },
//  {
//  aluno: { nome: 'luiz', id: 2 },
//  matricula: { aluno: 2, turma: 3 },
//  turma: { nome: 'letras', id: 3 }
//  },
//  {
//  aluno: { nome: 'luiz', id: 2 },
//  matricula: { aluno: 2, turma: 0 },
//  turma: { nome: 'sistemas de informação', id: 0 }
//  },
//  {
//  aluno: { nome: 'joao', id: 3 },
//  matricula: { aluno: 3, turma: 0 },
//  turma: { nome: 'sistemas de informação', id: 0 }
//  }
// ]

aggregations (group by)

Finally, you can perform aggregations using reduce combined with the Map data structure.

let group_by = (data, key, out, start) => Array.from(
    data
    .reduce((ac, v) =>
        ac.set(key(v), out(ac.get(key(v)) || start, v)), new Map
    ).values()
);

console.log(
    group_by(result, x => x.turma.nome, ac => ac + 1, 0)
);

console.log("\n");

console.log(
    group_by(
        result,
        x => x.aluno.nome,
        (ac, v) => ({
            aluno: v.aluno.nome,
            total: ac.total + 1 || 1
        }), {}
    )
);

console.log("\n");

console.log(
    group_by(
        result,
        x => x.aluno.nome,
        (ac, v) => ({
            aluno: v.aluno,
            turmas: (ac.turmas || []).concat(v.turma.nome),
        }), {}
    )
);

// output: 
// [ 1, 2, 3 ]
// [
//  { aluno: 'claudia', total: 3 },
//  { aluno: 'luiz', total: 2 },
//  { aluno: 'joao', total: 1 }
// ]
// [
//  {
//  aluno: { nome: 'claudia', id: 1 },
//  turmas: [ 'enfermagem', 'letras', 'sistemas de informação']
//  },
//  {
//  aluno: { nome: 'luiz', id: 2 },
//  turmas: [ 'letras', 'sistemas de informação' ]
//  },
//  {
//  aluno: { nome: 'joao', id: 3 },
//  turmas: [ 'sistemas de informação' ]
//  }
// ]