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. 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). Below, you can see a view of each step of the filter process for a list of integers X = [0, 5, 8, 3, 2, 1] according to the function : This function express that if is even the return value is , otherwise it's . This is the predicate. Filter is a standard function for many programming languages, e.g., Haskell, OCaml, Standard ML, or Erlang. Common Lisp provides the functions remove-if and remove-if-not. Scheme Requests for Implementation (SRFI) 1 provides an implementation of filter for the language Scheme. C++ provides the algorithms remove_if (mutating) and remove_copy_if (non-mutating); C++11 additionally provides copy_if (non-mutating). 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) = [x | p x] ++ filter p xs Here, [] denotes the empty list, ++ the list concatenation operation, and [x | p x] denotes a list conditionally holding a value, x, if the condition p x holds (evaluates to True).