filter, map e reduce

Essa semana Quando começei a escrever esse artigo me veio uma ideia meio maluca: Seria possível implementar um banco de dados relacional utilizando apenas map, filter e reduce?

A resposta é: É possível, e minha implementação pode ser encontrada nesse repositório. Vale lembrar que essa implementação é apenas um exercício criativo, ou seja, não me cobre dizendo que não se trata de um banco de dados completo.

Agora vamos direto ao ponto: O objetivo desse artigo é explicar a partir de exemplos como utilizar as funções filter, map e reduce em situações comuns no trabalho de um programador.

O array

O array é uma estrutura de dados onde os elementos ficam dispostos na memória de forma sequencial e uma de suas propriedades é o acesso direto aos elementos por meio do índice. Algo como o exemplo abaixo:

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

// saida:
// melancia

Essa operação é extremamente rápida e tem complexidade O(1). Contudo, descobrir qual o índice à partir do valor não é uma operação igualmente trivial, uma vez que no pior caso é necessário visitar todos os itens da estrutura para que se possa encontrar o índice, como demonstrado no exemplo abaixo:

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

// saida:
// 2 abacate

lembrando que o algoritimo acima foi escrito apenas para fins de ilustração e o mesmo resultado pode ser obtido com os métodos indexOf e find, ou ainda com o método filter na posição 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"));

// saida:
// 2
// abacate
// abacate
// true

devemos observar que todas as funções acima têm complexidade O(n)

reestruturando o array

Além das funções voltadas para a busca de elementos, tais como indexOf, find, filter e includes, também existem funções voltadas para a conversão do array em um novo array com valores derivados dos valores originais, ou mesmo para a conversão do array em outro tipo de variável.

No exemplo abaixo a função map é usada para converter um array de strings em um array de objetos com uma propriedade contendo a string original e uma segunda propriedade contendo o tamanho da mesma.

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

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

Já nesse segundo exemplo, a função reduce é utilizada para somar e para multiplicar todos os tamanhos de string presentes em um 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));

// saida:
// 20
// 280

Também é possível usar essa tecnica para indexar um array de strings transformando o mesmo em um objeto com a mesma string como chave.

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

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

Por fim, é possível usar a estrutura de dados Map para tornar o exemplo acima mais compacto e performático.

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

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

E o tal banco de dados?

Para essa simplificação do conceito de banco de dados, estou considerando arrays de objetos como tabelas e ignorando por completo as operações de insert por serem óbvias. Logo, para esse artigo, vamos utilizar o "banco de dados" abaixo:

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

// saida:
// 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 } }
// ]

sortear matriculas

No exemplo anterior foram definidas as tabelas alunos e turmas, porém a relação entre as mesmas ainda não foi definida. Então, vamos usar a instrução Array(8) para criar um array com 8 posições, vamos utilizar o método .fill(0) para preencher cada item com o valor zero. Isso é necessário pois o método .map ignora elementos com valor undefined. Por fim, utilizaremos o método .map para converter esse array de zeros em um array de objetos cuja estrutura contem as chaves primárias de aluno e turma geradas aleatoriamente.

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

// saida: 
// 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 } }
// ]

remover matriculas duplicadas no sorteio

Para removermos as entradas duplicadas podemos utilizar uma técnica que consiste em converter o Array em Map indexando pela chave que desejamos tornar única e obtendo o resultado final por meio do método .values().

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

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

// saida: 
// 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 } }
// ]

produto cartesiano (join)

Uma das operações mais comuns nos bancos de dados é o produto cartesiano. Na matemática, essa operação consiste em obter todas as combinações possíveis entre elementos de dois ou mais conjuntos distintos. O algorítimo abaixo permite fazer exatamente isso com as "tabelas" alunos e turmas.

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

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

// saida: 
// 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 }
//  }
// ]

produto entre n tabelas

E, com um novo reduce, podemos reaproveitar a função join para obter o produto cartesiado de n tabelas.

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

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

// saida:
// 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 }
//  },
//  ...
// ]

consultas

Para tornar o produto carteziano útil, é possível adicionar condições com o método filter tornando o resultado em uma consulta.

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

// saida:
// 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 }
//  }
// ]

agregações (group by)

Por fim, é possível fazer agregações utilizando o método reduce combinado a estutura de dados Map

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),
        }), {}
    )
);

// saida: 
// [ 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' ]
//  }
// ]