Filter (higher-order function)
   HOME

TheInfoList



OR:

In
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
, filter is a higher-order function that processes a data structure (usually a
list A ''list'' is any set of items in a row. List or lists may also refer to: People * List (surname) Organizations * List College, an undergraduate division of the Jewish Theological Seminary of America * SC Germania List, German rugby unio ...
) in some order to produce a new data structure containing exactly those elements of the original data structure for which a given
predicate Predicate or predication may refer to: * Predicate (grammar), in linguistics * Predication (philosophy) * several closely related uses in mathematics and formal logic: **Predicate (mathematical logic) **Propositional function **Finitary relation, o ...
returns the
boolean value In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in ...
true.


Example

In
Haskell Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
, the code example filter even ..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) ..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).


Visual example

Below, you can see a view of each step of the filter process for a list of integers X = , 5, 8, 3, 2, 1/code> according to the function :f(x) = \begin \mathrm &\text x \equiv 0 \pmod\\ \mathrm & \text x \equiv 1 \pmod. \end This function express that if x is even the return value is \mathrm, otherwise it's \mathrm. This is the predicate.


Language comparison

Filter is a standard function for many
programming language A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language. The description of a programming ...
s, e.g., Haskell,filter
in the Haskell Standard Prelude
OCaml,filter
in the OCaml standard library module list
Standard ML, or Erlang. Common Lisp provides the functions remove-if and remove-if-not.''Function'' REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT
in the
Common Lisp HyperSpec The Common Lisp HyperSpec is a technical standard document written in the hypertext format ''Hypertext Markup Language'' (HTML). It is not the American National Standards Institute The American National Standards Institute (ANSI ) is a priv ...
Scheme Requests for Implementation Scheme Requests for Implementation (SRFI) is an effort to coordinate libraries and extensions of standard Scheme programming language, necessitated by Scheme's minimalist design, and particularly the lack of a standard library before Scheme R6RS. SR ...
(SRFI) 1 provides an implementation of filter for the language Scheme.filter
in SRFI 1
C++ C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
provides the
algorithms In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
remove_if (mutating) and remove_copy_if (non-mutating);
C++11 C++11 is a version of the ISO/ IEC 14882 standard for the C++ programming language. C++11 replaced the prior version of the C++ standard, called C++03, and was later replaced by C++14. The name follows the tradition of naming language versions b ...
additionally provides copy_if (non-mutating).remove_if
an

in the SGI
Standard Template Library The Standard Template Library (STL) is a software library originally designed by Alexander Stepanov for the C++ programming language that influenced many parts of the C++ Standard Library. It provides four components called ''algorithms'', '' ...
(STL) spec
Smalltalk provides the select: method for collections. Filter can also be realized using
list comprehension A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical ''set-builder notation'' (''set comprehension'') as distinct from the use of ...
s in languages that support them. In Haskell, filter can be implemented like this: filter :: (a -> Bool) -> -> 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).


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 and partitionHaskell filter ''partition''
/ref>) are also common. A common memory optimization for
purely functional programming language In computer science, purely functional programming usually designates a programming paradigm—a style of building the structure and elements of computer programs—that treats all computation as the evaluation of mathematical functions. Program ...
s is to have the input list and filtered result share the longest common tail ( tail-sharing).


See also

*
Map (higher-order function) In many programming languages, map is the name of a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called ''apply-t ...
*
List comprehension A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical ''set-builder notation'' (''set comprehension'') as distinct from the use of ...
*
Guard (computing) In computer programming, a guard is a boolean expression that must evaluate to true if the program execution is to continue in the branch in question. Regardless of which programming language is used, a guard clause, guard code, or guard statemen ...


References

{{Reflist Higher-order functions Articles with example Haskell code