Filter (higher-order function)

From Wikipedia, the free encyclopedia

Jump to: navigation, search

In functional programming, filter is a higher-order function that processes a data structure (typically 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.

Contents

[edit] 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).

[edit] Implementation

Filter is a standard function for many programming languages, e.g. Haskell,[1] Objective Caml,[2] Standard ML,[3] or Erlang.[4] Common Lisp provides the functions remove-if and remove-if-not.[5] SRFI 1 provides an implementation of filter for the Scheme programming language.[6] C++ provides the algorithms remove_if (mutating) and remove_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
Haskell filter pred list Or, via list comprehension: [x | x <- list, pred x]
OCaml, Standard ML List.filter pred list
Python filter(func, list) Or, via list comprehension: [x for x in list if pred(x)]
Ruby enum.find_all {block}
enum.select {block}		 enum is an Enumeration
C++ std::remove_copy_if(begin, end, result, prednot) in header <algorithm>
begin, end, result are iterators
predicate is reversed
Perl grep block list
grep expr, list
C# 3.0 ienum.Where(pred) Where is an extension method
ienum is an IEnumerable
Similarly in all .NET languages
JavaScript 1.6 array.filter(pred)
Common Lisp (remove-if-not pred list)
Scheme R6RS, Clojure (filter pred list)
Erlang lists:filter(Fun, List)
PHP array_filter(array, pred)
Mathematica Select[list, pred]
S/R Filter(pred,array)
array[pred(array)]		 In the second case, pred must be a vectorized function
Objective-C (Cocoa in Mac OS X 10.4+) [array filteredArrayUsingPredicate:pred] pred is an NSPredicate object, which may be limited in expressiveness

[edit] Variants

Filter creates its result without modifying the original list. Many programming languages also provide variants that destructively modify the list argument instead for performance reasons. Other variants of filter (like e.g. dropWhile and partition) 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).

[edit] References

  1. ^ filter in the Haskell Standard Prelude
  2. ^ filter in the Objective Caml standard library module list
  3. ^ "The List structure". The Standard ML Basis Library. http://www.standardml.org/Basis/list.html#SIG:LIST.filter:VAL. Retrieved on 2007-09-25. 
  4. ^ filter/2 in the Erlang STDLIB Reference Manual documentation of the module lists
  5. ^ remove-if-not in the Common Lisp HyperSpec
  6. ^ filter in SRFI 1
  7. ^ remove_if and remove_copy_if in the SGI STL spec

[edit] See also

  This computer science article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org/wiki/Filter_(higher-order_function)"
Personal tools
Languages