Filter (higher-order function)

In functional programming, filter is a higher-order function that processes a data structure (usually a list) in some order to produce a new data structure containing exactly those elements of the original data structure for which a given predicate returns the boolean value true.

Example

In Haskell, the code example

 filter even [1..10]

evaluates to the list 2, 4,…10 by applying the predicate even to every element of the list of integers 1, 2,… 10 in that order and creating a new list of those elements for which the predicate returns the boolean value true, thereby giving a list containing only the even members of that list. Conversely, the code example

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

evaluates to the list 1, 3,…9 by collecting those elements of the list of integers 1, 2… 10 for which the predicate even returns the boolean value false (with . being the function composition operator).

Language comparison

Filter is a standard function for many programming languages, e.g., Haskell,[1] OCaml,[2] Standard ML,[3] or Erlang.[4] Common Lisp provides the functions remove-if and remove-if-not.[5] Scheme Requests for Implementation (SRFI) 1 provides an implementation of filter for the language Scheme.[6] C++ provides the algorithms remove_if (mutating) and remove_copy_if (non-mutating); C++11 additionally provides copy_if (non-mutating).[7] Smalltalk provides the select: method for collections. Filter can also be realized using list comprehensions in languages that support them.

In Haskell, filter can be implemented like this:

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

Here, [] denotes the empty list, and : denotes the concatenation operator used to create a new list from a given value and an existing list.

Filter in various languages
Language Filter Notes
C# 3.0 ienum.Where(pred)
or
The where clause		 Where is an extension method
ienum is an IEnumerable
Similarly in all .NET languages
CFML obj.filter(func) Where obj is an array or a structure. The func receives as an argument each element's value.
Clojure (filter predicate list)[8] Or, via list comprehension: (for [x list :when (pred x)] x)
Common Lisp (remove-if inverted-pred list)
(remove-if (complement pred) list)
(remove-if-not pred list)		 The function remove-if-not has been deprecated[5] in favor of the equivalent remove-if where the predicate is complemented.[9] Thus the filter (remove-if-not #'oddp '(0 1 2 3)) should be written (remove-if (complement #'oddp) '(0 1 2 3)) or more simply: (remove-if #'evenp '(0 1 2 3)) where evenp returns the inverted value of oddp.[10]
C++ std::remove_copy_if(begin, end, result, prednot)
std::copy_if(begin, end, result, pred) (C++11)		 in header <algorithm>
begin, end, result are iterators
predicate is reversed
D std.algorithm.filter!(pred)(list)
Erlang lists:filter(Fun, List) Or, via list comprehension: [ X || X <- List, Fun(X) ]
Haskell filter pred list Or, via list comprehension: [x | x <- list, pred x]
Haxe list.filter(pred)
Lambda.filter(list, pred)
 Or, via list comprehension: [x | x <- list, pred x]
J (#~ pred) list An example of a monadic hook. # is copy, ~ reverses arguments. (f g) y = y f (g y)
Java 8+ stream.filter(pred)
JavaScript 1.6 array.filter(pred)
Mathematica Select[list, pred]
Objective-C (Cocoa in Mac OS X 10.4+) [array filteredArrayUsingPredicate:pred] pred is an NSPredicate object, which may be limited in expressiveness
F#, OCaml, Standard ML List.filter pred list
PARI/GP select(expr, list) The order of arguments is reversed in v. 2.4.2.
Perl grep block list
grep expr, list
PHP array_filter(array, pred)
Prolog filter(+Closure,+List,-List) Since ISO/IEC 13211-1:1995/Cor.2:2012[11] the core standard contains closure application via call/N[12]
Python filter(func, list) Or, via list comprehension: [x for x in list if pred(x)]. In Python 3.x, filter was changed to return an iterator rather than a list. The complementary functionality, returning an iterator over elements for which the predicate is false, is also available in the standard library as filterfalse in the itertools module.
Ruby enum.find_all {block}
enum.select {block}		 enum is an Enumeration
S, R Filter(pred,array)
array[pred(array)]		 In the second case, pred must be a vectorized function
Scala list.filter(pred) Or, via for-comprehension: for(x <- list; if pred) yield x
Scheme R6RS (filter pred list)
Smalltalk aCollection select: aBlock
Swift array.filter(pred)
filter(sequence, pred)
XPath, XQuery list[block]
filter(list, func)		 In block the context item . holds the current value

Variants

Filter creates its result without modifying the original list. Many programming languages also provide variants that destructively modify the list argument instead for faster performance. Other variants of filter (e.g., Haskell dropWhile[13] and partition[14]) are also common. A common memory optimization for purely functional programming languages is to have the input list and filtered result share the longest common tail (tail-sharing).

See also

References

  1. ↑ filter in the Haskell Standard Prelude
  2. ↑ filter in the OCaml standard library module list
  3. ↑ "The List structure". The Standard ML Basis Library. Retrieved 2007-09-25.
  4. ↑ filter/2 in the Erlang STDLIB Reference Manual documentation of the module lists
  5. 1 2 Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT in the Common Lisp HyperSpec
  6. ↑ filter in SRFI 1
  7. ↑ remove_if and remove_copy_if in the SGI Standard Template Library (STL) spec
  8. ↑ clojure.core/filter on ClojureDocs
  9. ↑ Function COMPLEMENT in the Common Lisp HyperSpec
  10. ↑ Function EVENP, ODDP in the Common Lisp HyperSpec
  11. ↑ ISO/IEC 13211-1:1995/Cor 2:2012
  12. ↑ http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
  13. ↑ Haskell filter dropWhile
  14. ↑ Haskell filter partition
This article is issued from Wikipedia - version of the 10/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.