Map, filter e reduce

Map: definição e aplicação

Photo by John Moeses Bauan on Unsplash

Olá! Hoje vamos falar de algumas funções muito comuns no paradigma funcional! E não é à toa, tais funções são muito poderosas e podem ser muito expressivas!

Muitas pessoas tem uma certa dificuldade em entendê-las, principalmente a função reduce! Para resolver isso de uma vez e para garantir que todos vão entender como elas funcionam, que tal codificar nossas próprias versões dessas famosas funções? Tenho certeza que isso vai facilitar bastante o entendimento!

Vamos utilizar a linguagem Python implementar nossas versões pŕoprias! Afinal, Python é uma linguagem com uma sintaxe elegante e uma semântica de fácil compreensão!

Ready to roll?

1. Map

A função map é utilizada para transformar lista em uma outra lista através de uma função fornecida como parâmetro para a função map!

Vamos nos atentar a um detalhe importantíssimo : ela retorna uma nova lista de mesmo tamanho da original, ok?

E como a função map pode receber como parâmetro outra função? É simples! Em Python, funções são objetos como outros da linguagem e podem, assim, ser passados como argumentos! Como a função map receber outra função como argumento, podemos dizer que ela é uma função de ordem superior!

Mas, como um função pode transformar uma lista em outra? É simples! Basta aplicar tal função em cada elemento da lista original para ter uma nova lista!

Portanto, map atua como se fosse um “mapa” que usa a função que recebe como argumento para levar cada elemento da lista original para um novo valor na lista de retorno!

Vamos criar a nossa versão da função map! De forma muito criativa, vamos chamá-la de my_map! Esta versão será recursiva pois facilita o entedimento e é muito mais elegante (ops! opinião pessoal detected, rs).

Vamos analisar a assinatura desta função:

my_map(fn, xs)

Vemos que my_map aceita como parâmetros uma função fn e uma lista xs!

Assim, nossa tarefa é aplicar fn em cada elemento da lista xs e retornar uma nova lista com esses retornos!

Primeiramente, vamos pensar no caso trivial quando my_map for invocada para uma lista xs vazia! Neste caso, devemos lembrar que o retorno de map deve ser uma lista! Pois bem, então, com isso, já explicamos as linhas 12 e 13 pois é onde realizamos o teste se xs é uma lista vazia e, se for tal caso, retornamos, também, uma lista vazia!

A listas em Python, quando avaliadas num contexto booleano, retornam False quando vazias! Assim, se xs for vazia, a expressão not xs retorna True!

if not xs: # returns True if xs is empty
    return [] 

Agora, vamos partir para um caso não trivial: quando xs não é uma lista vazia! Bem, neste caso, vamos utilizar a notação de head e tail de uma lista:

Head:

xs = [1, 2, 3]
hd = xs[0] # 1

Definimos head o elemento inicial da lista! Em Python, ele pode ser acessado pelo índice 0. Logo, xs[0].

Tail:

xs = [1, 2, 3]
tl = xs[1:] # [2, 3]

Definimos tail como a lista restante sem o elemento inicial da mesma! Em Python, podemos obter o tail de uma lista através da expressão slice xs[1:] que retorna uma lista sem o elemento inicial que fica no índice 0.

Com isso, conseguimos entender a linha 15! Ufa, estamos quase no fim! Agora, devemos aplicar o que fizemos de forma recursiva!

Vamos analisar a linha 17 para enteder a expressão que retornamos!

return [fn(hd)] + my_map(fn, tl)

A primeira parte desta expressão, antes do operador + é responsável por aplicar a função fn que recebemos como parâmetro para criar uma nova lista no head da lista xs original!

Em seguida, criamos uma nova lista com apenas o elemento fn(hd):

[fn(hd)] # apply fn to hd and create a new list with 1 element

Com isso, começamos a construir uma nova lista a partir da função fn!

Agora, devemos nos lembrar, novamente, que my_map retorna uma lista! Assim, para duas listas, o operador + concatena (“junta”) as duas listas, isto é, adiciona a segunda lista no final da primeira:

[1, 2] + [3, 4] == [1, 2, 3, 4] # concatenates two lists

Como a expressão [fn(hd)] será avaliada como uma lista e como sabemos que o retorno de my_map é outra lista, concluimos que nosso return é coerente pois retorna uma lista concatenada!

Por fim, precisamos apenas criar uma elegante recursão para terminarmos! Analisando a expressão após o operador +:

my_map(fn, tl)

Vemos que invocamos a função my_map recursivamente com a mesma função fn! Contudo, o segundo argumento, agora, é o tail da lista xs original! Veja que tail sempre exclui o head (primeiro elemento) de forma a ser menor que xs original! Assim, garantimos que nosso algoritmo irá convergir em uma solução final e que não teremos uma recursão infinita que irá explodir nossa call stack e gerar uma bela exceção! (Ah, quantas vezes já não fiz isso…. rs)

Mas, pera ai! Se em cada invocação de my_map, invocamos-na com uma lista menor (tail), uma hora essa lista vai ser vazia, certo??

Perfeito! É isso mesmo! Lembram do nosso caso trivial? Ele está lá pra isso também! Yay! Assim, quando aintigmos tal condição, as linhas 12 e 13 darão conta do recado e retornarão uma lista vazia! Com isso, nosso algoritmo recursivo consegue convergir para um resultado final! Elegante, não? Nada de for’s imperativos, índices errados sendo acessados, rs! (Mas, vamos com calma, Python esta mais para linguagem imperativa do que funcional conforme o próprio Guido van Rossum — autor da linguagem Python — já comentou! Infelizmente, faltam algumas otimizações na linguagem como tail recursions e outras features importantes e típicas do mundo funcional… mas, mesmo assim, ainda conseguimos cumprir o objetivo de entender map, filter, reduce com a bela sintaxe de Python).

Assim, entendemos e implementamos a ideia por trás da função map! Resumidamente, nós aplicamos uma outra função em cada elemento de uma lista original para criamos uma outra lista nova e fizemos isso de uma forma recursiva e elegante!

Por fim, as linhas 19 até 23 vão mostrar a aplicação da nossa my_map! Expressões lambdas em Python são formas de criar funções anônimas, isto é, funções sem nome ou que não possuem um binding com um identificador que permite referenciá-la! Assim, são formas de criar funções para uso local e rápido e que não precisam ser armazenadas em uma variável. Por exemplo, a expressão a seguir define uma função anônima que recebe o parâmetro arg1 e retorna 2 * arg1.

lambda arg1 : 2 * arg1

Para os interessados, Python possui a função map (built-in) que vem com a biblioteca padrão da linguagem! O uso de map será análogo ao my_map! Contudo, em Python 3.x, a função map retorna um objeto map e não uma lista!

Contudo, tal objeto map pode ser convertido em uma lista através da função list()! Existe uma motivação que pode gerar um futuro post sobre a razão de ser assim, mas, basicamente, envolve iterators e um uso mais racional de memória por parte do interpretador Python já que se este retornasse uma lista teriamos um algoritmo com complexidade de espaço O(n) e já com um iterator… OK. Deixemos isso para um outro post, rs!

Ah, uma última coisa: cuidado ao definir uma função com nome de map! Lembre-se que este nome referencia a função built-in da linguagem Python! Ao fazer isso, você vai definir uma função sua que não referenciará a função map original e otimizada da linguagem! Quem ai nunca criou uma variável chamada str em Python e depois não sabia o por quê da função str não funcionar….

O quê?? Eu nunca fiz isso não! Que absurdo... tá bom vai… já fiz e ainda fa… Pera lá, já não está na hora de ACABAR com este post?!

No caso de dúvidas, sugestões ou erros, por favor entre em contato! Discussões são sempre bem vindas!

Até o próximo post, no qual falaremos sobre filter!