Map, filter e reduce

Filter: definição e aplicação com recibos in-app da Apple!

Photo by John Moeses Bauan on Unsplash

Olá gente! Que tal, hoje, aprendermos de uma vez um outra função muito expressiva e poderosa? Sim, após o último post sobre map, vamos hoje entender o que é filter! Novamente, vamos utilizar a linguagem Python para exemplificar uma vez que sua sintaxe é de fácil compreensão!

Ready to rumble?

1. Filter

A função filter é uma função de ordem superior que é utilizada para remover ou filtrar elementos indesejados que estejam presentes em uma determinada lista original. Assim, por exemplo, se temos a seguinte lista:

[1, 2, 3]  # the original list

Podemos aplicar um filtro nessa lista original para remover todos os elementos menores que 2 para obter a seguinte lista já filtrada:

[2, 3]  # the filtered list

Vamos ao primeiro detalhe importantíssimo sobre filter: diferentemente da função map, a função filter pode retornar listas com tamanhos diferente da lista original, ou seja, pode retornar uma lista igual à original, menor ou até mesmo uma lista vazia! (Ah e claro, mas nunca uma lista maior, rs)

Mas… qual o motivo disso?

É bastante simples! O nome filter não é à toa! Nós utilizamos essa função para aplicar um filtro em uma lista de elementos original para remover/filtrar todos os elementos que não satisfaçam às condições que desejamos!

Para aplicar tais condições, devemos nos lembrar que filter, como map, é uma função de ordem superior. Logo, podemos passar uma função como parâmetro para a própria função filter, a qual será responsável por definir as condições para um elemento permanecer ou ser removido da lista original! Neste artigo, chamarei tal função passada à função filter como função de filtro (que criativo, não? rs).

Mas, como a função de filtro pode determinar condições sobre quais elementos permanecem na lista original e quais não??

É aqui que precisamos entender um segundo detalhe importantíssimo da função filter:

A função passada à função filter deve retornar um valor booleano uma vez que tal função será aplicada em cada elemento da lista original! Isso porque cada elemento da lista original será passado como parâmetro para a função de filtro e, caso esta retorne o valor True, tal elemento permanecerá na lista filtrada e, caso a função de filtro retorne o valor False, tal elemento será removido.

Vamos criar nossa própria função filter para facilitar o entendimento?

2. Criando nossa versão:

Vamos analisar o seguinte trecho de código:

De forma análoga à nossa função map do post anterior, definimos nas linhas 12 e 13 o caso base da nossa recursão, isto é, quando a lista passada para a nossa função filter for vazia, retornamos uma lista vazia!

Na linha 16, definimos a cabeça (hd) e cauda (tl) da lista como fizemos para nossa função map! Para quem não se lembra, hd é o primeiro elemento da lista e tl é toda lista restante sem este primeiro elemento. Vemos, aqui, que uma lista pode ser definida em termos de si mesma. Por exemplo:

  lista     -->   cabeça  +  lista (cauda)
[1, 2, 3]   -->     1     +    [2, 3]  

Quando uma estrutura de dados pode ser definida em termos dela mesma, dizemos que esta é uma estrutura de dados recursiva. E é por isso que recursão cai muito bem com essas funções map, filter, reduce e outras mais “funcionais” já que podem ser aplicadas em listas que são estruturas recursivas… ;)

Voltando ao exemplo, na linha 19, executamos a função de filtro passando como parâmetro cada elemento da lista original, isto é, passando hd para tal função! Como já discutimos, tal função de filtro deve usar tal parâmetro para verificar uma dada condição e, caso tal elemento passe nessa condição, a função de filtro deve retornar True. Caso contrário, deve retornar False! Ou seja, a avaliação da invocação da função filter_fn deve sempre gerar um booleano!

if filter_fn(hd):  # filter_fn MUST return a boolean value

Na linha 21, temos o caso no qual o elemento da lista original supre a condição determinada pela função filtro e, assim, deve permanecer na lista original:

return [hd] + my_filter(filter_fn, tl)  # adds hd to the new list!

Veja que neste caso utilizamos hd para construir uma nova lista [hd] que será concatenada/unida às listas retornadas pelas invocações recursivas da função my_filter! Lembrando que tais invocações retornaram outras listas com os outros elementos que passaram na condição da função de filtro! Quando o caso base da recursão for atingido, a concatenação ocorrerá com a lista vazia da linha 13 que não altera o resultado final.

Para os elementos que não suprem as condições da função de filtro, executamos a linha 24:

return my_filter(filter_fn, tl)  # skips the hd of the list

Veja que neste caso, apenas retornamos o resultado da invocação recursiva para o tail da lista, isto é, nós simplesmente pulamos a adição do elemento hd na nova lista filtrada uma vez que tal elemento não passou nas condições de filter_fn.

Por fim, notemos que todas as invocações recursivas utilizam a a cauda da lista original (tl). O design do algoritmo recursivo foi feito dessa forma para que este algoritmo seja capaz de convergir em um resultado final, isto é, para que nossa recursão trabalhe com listas cada vez menores até atingirmos nosso caso base (uma lista vazia) e, assim, não termos nenhum problema de recursões infinitas e call stacks sendo explodidas rs…!

3. Testando:

Que tal aplicarmos esse conhecimento em um caso um pouco mais prático? Pois é…. há pouco tempo atrás, precisei utilizar a função filter em uma app que lidava com assinaturas in-app da Apple!

Resumidamente, quando uma pessoa faz uma compra in-app na Apple, um recibo criptografado é gerado. Após descriptografar tal recibo, era possível ter acesso a informações sobre a compra como o identificador da transação, qual produto comprado, data de compra, etc.

Segue um exemplo de um desses recibos cuja estrutura é bem parecida com a original, mas com dados fictícios (recibo estilo ios-7):

Como meu sistema lidava com assinaturas, não era interessante para mim compras que não tivessem uma data de início e fim. Assim, olhando tal recibo de compra, vemos que no campo latest_receipt_info temos uma lista com dois produtos que possuem 2 product_ids diferentes (product_id é um identificador de produto de um app na Apple, como um SKU).

O primeiro produto, o br.com.app.subscription, possui um purchase_date e um expires_date e é justamente uma assinatura renovável. Já o outro produto da lista, br.com.app.useless, possui apenas o campo purchase_date, mas sem o campo expires_date de forma que tal produto pode ser uma assinatura não renovável e, portanto, devia ser ignorada pela aplicação.

Assim, decidi utilizar a função built-in da linguagem Python: o filter! Assim, dado esse caso real, vamos aproveitar este contexto para utilizar a função my_filter que criamos para resolver esse problema! Assim, que tal escrevermos um teste para esse caso? Vamos ao código:

Para este teste simples, vamos utilizar o módulo unittest da linguagem Python. Criamos, então, a classe MyFilterAppleReceiptTestCase. No método setUp (linha 14), criamos uma variável de instância chamada apple_receipt com o mesmo formato de recibo que comentamos anteriormente.

Na linha 69, definimos nosso teste unitário! Veja que a variável local expected_latest_receipt_info é justamente uma lista, mas sem o produto br.com.app.useless (afinal, desejamos apenas assinaturas com início e fim, certo?), ou seja, esta lista filtrada é justamente o que esperamos que a nossa função my_filter produza como resultado! Assim, na linha 96, realizamos a invocação da nossa função my_filter, passando a função anônima (lambda) como sendo a função de filtro para estabelecer a condição de que cada produto dentro da chave “latest_receipt_info” deve ter uma data final, isto é, um expires_date:

lambda receipt: "expires_date" in receipt  # evals to a bool

Veja que esta função lambda aceita como parâmetro uma variável chamada receipt, que sabemos que será cada dicionário da lista original “latest_receipt_info”. Além disso, tal função retorna um booleano que é o resultado da operação com a keyword in da linguagem Python. Tal operador simplesmente irá utilizar um algoritmo de busca da linguagem para verificar se cada dicionário receipt possui uma chave chamada “expires_date”. Se tal dicionário possuir tal chave, o resultado será True (logo é uma assinatura e deve ser mantida na lista filtrada). Caso contrário, tal expressão gerará o valor False e irá remover tal dicionário da lista original, que é exatamente o que acontece com o produto br.com.app.useless que não nos interessa e, assim, pode ser removido!

Como resultado, nosso assert na linha 99 garante que a lista produzida (filtrada) é exatamente a esperada, somente com assinaturas!

Ufa, é isso ai! Por fim, vale, novamente, como na função map, lembrar que a linguagem Python já possui uma função built-in chamada filter e que é muito mais otimizada que a qual nos criamos! Além disso, como discutido no post anterior, tal função built-in retorna um objeto filter que pode ser convertido para uma lista através da função list()!

Por fim, é importante lembrar que recriamos a função filter para aprendermos um pouco mais sobre tal função, mas é, em geral, muito melhor utilizar a função padrão da linguagem que já passou por diversas otimizações e testes!

É isso ai gente! Qualquer dúvida ou erro, basta falar! Discussões são sempre bem vindas! Até o próximo post no qual falaremos sobre reduce! (essa é a mais complicada, mas, com calma, a gente chega lá, rs!!)