Filtro (função de ordem superior) - Filter (higher-order function)

Na programação funcional , o filtro é uma função de ordem superior que processa uma estrutura de dados (geralmente uma lista ) em alguma ordem para produzir uma nova estrutura de dados contendo exatamente aqueles elementos da estrutura de dados original para os quais um determinado predicado retorna o valor booleano true .

Exemplo

Em Haskell , o exemplo de código

 filter even [1..10]

avalia a lista 2, 4,…, 10 aplicando o predicado evena cada elemento da lista de inteiros 1, 2,…, 10 nessa ordem e criando uma nova lista daqueles elementos para os quais o predicado retorna o valor booleano verdadeiro , fornecendo assim uma lista contendo apenas os membros pares dessa lista. Por outro lado, o exemplo de código

 filter (not . even) [1..10]

avalia para a lista 1, 3,…, 9 coletando aqueles elementos da lista de inteiros 1, 2,…, 10 para os quais o predicado evenretorna o valor booleano falso ( .sendo o operador de composição da função ).

Exemplo visual

Abaixo, você pode ver uma visão de cada etapa do processo de filtro para uma lista de inteiros de X = [0, 5, 8, 3, 2, 1]acordo com a função:

$${\ displaystyle f (x) = {\ begin {cases} True & {\ text {if}} x \ equiv 0 {\ pmod {2}} \\ False & {\ text {if}} x \ equiv 1 {\ pmod {2}}. \ End {cases}}}$$

Esta função expressa que se for par, o valor de retorno é , caso contrário, é . Este é o predicado. ${\ displaystyle x}$${\ displaystyle True}$${\ displaystyle False}$

Visualização das etapas de processamento ao aplicar a função de filtro em uma lista

Comparação de linguagem

Filtro é uma função padrão para muitas linguagens de programação , por exemplo, Haskell, OCaml , Standard ML ou Erlang . Common Lisp fornece as funções remove-ife remove-if-not. Scheme Requests for Implementation (SRFI) 1 fornece uma implementação de filtro para a linguagem Scheme . C ++ fornece os algoritmos remove_if (com mutação) e remove_copy_if(sem mutação); C ++ 11 fornece adicionalmente copy_if(sem mutação). Smalltalk fornece o select:método para coleções. O filtro também pode ser realizado usando compreensões de lista em idiomas que as suportam.

Em Haskell, filterpode ser implementado assim:

 filter :: (a -> Bool) -> [a] -> [a]
 filter _ []     = []
 filter p (x:xs) = [x | p x] ++ filter p xs

Aqui, []denota a lista vazia, ++a operação de concatenação de lista e [x | p x]denota uma lista contendo um valor xcondicionalmente p x,, se a condição for mantida (avalia para True).

Variantes

O filtro cria seu resultado sem modificar a lista original. Muitas linguagens de programação também fornecem variantes que modificam destrutivamente o argumento da lista para um desempenho mais rápido. Outras variantes de filtro (por exemplo, Haskell dropWhilee partition) também são comuns. Uma otimização de memória comum para linguagens de programação puramente funcionais é fazer com que a lista de entrada e o resultado filtrado compartilhem a cauda comum mais longa ( compartilhamento de cauda ).

Veja também

• Mapa (função de ordem superior)
• Compreensão de lista
• Guarda (computação)

Referências