En programación funcional , un filtro es una función de orden superior que procesa una estructura de datos (normalmente una lista ) en algún orden para producir una nueva estructura de datos que contenga exactamente aquellos elementos de la estructura de datos original para los que un predicado dado devuelve el valor booleano true .
En Haskell , el ejemplo de código
filtro uniforme [ 1 .. 10 ] evalúa la lista 2, 4, …, 10 aplicando el predicado evena cada elemento de la lista de números enteros 1, 2, …, 10 en ese orden y creando una nueva lista de aquellos elementos para los que el predicado devuelve el valor booleano verdadero, dando así una lista que contiene solo los miembros pares de esa lista. Por el contrario, el ejemplo de código
filtro ( no.par ) [ 1..10 ] evalúa la lista 1, 3, …, 9 al recopilar aquellos elementos de la lista de números enteros 1, 2, …, 10 para los cuales el predicado evendevuelve el valor booleano falso (siendo .el operador de composición de función ).
A continuación, puede ver una vista de cada paso del proceso de filtrado para una lista de números enteros X = [0, 5, 8, 3, 2, 1]según la función:
Esta función expresa que si es par, el valor de retorno es , de lo contrario, es . Este es el predicado.
El filtro es una función estándar para muchos lenguajes de programación , por ejemplo, Haskell, [1] OCaml , [2] Standard ML , [3]
o Erlang . [4] Common Lisp proporciona las funciones remove-ify remove-if-not. [5] Scheme Requests for Implementation (SRFI) 1 proporciona una implementación de filtro para el lenguaje Scheme . [6] C++ proporciona los algoritmos remove_if (mutante) y remove_copy_if(no mutante); C++11 proporciona además copy_if(no mutante). [7] Smalltalk proporciona el select:método para colecciones. El filtro también se puede implementar utilizando listas por comprensión en lenguajes que las admitan.
En Haskell, filterse puede implementar así:
filtro : :( a -> Bool ) -> [ a ] - > [ a ] filtro _ [] = [ ] filtro p ( x : xs ) = [ x | px ] ++ filtro pxs Aquí, []denota la lista vacía, ++la operación de concatenación de listas, y [x | p x]denota una lista que contiene condicionalmente un valor, x, si la condición p xse cumple (se evalúa como True).
El filtro crea su resultado sin modificar la lista original. Muchos lenguajes de programación también proporcionan variantes que modifican destructivamente el argumento de la lista para un rendimiento más rápido. Otras variantes del filtro (por ejemplo, Haskell dropWhile[14] y partition[15] ) también son comunes. Una optimización de memoria común para lenguajes de programación puramente funcionales es hacer que la lista de entrada y el resultado filtrado compartan la cola común más larga ( tail-sharing ).
listlists