HOME

TheInfoList



OR:

In
functional programming In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
, filter is a
higher-order function In mathematics and computer science, a higher-order function (HOF) is a function that does at least one of the following: * takes one or more functions as arguments (i.e. a procedural parameter, which is a parameter of a procedure that is itself ...
that processes a
data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...
(usually a
list A list is a Set (mathematics), set of discrete items of information collected and set forth in some format for utility, entertainment, or other purposes. A list may be memorialized in any number of ways, including existing only in the mind of t ...
) 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 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 pioneered several programming language ...
, 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. Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
s, e.g., Haskell,filter
in the Haskell Standard Prelude
OCaml OCaml ( , formerly Objective Caml) is a General-purpose programming language, general-purpose, High-level programming language, high-level, Comparison of multi-paradigm programming languages, multi-paradigm programming language which extends the ...
,filter
in the
OCaml OCaml ( , formerly Objective Caml) is a General-purpose programming language, general-purpose, High-level programming language, high-level, Comparison of multi-paradigm programming languages, multi-paradigm programming language which extends the ...
standard library module list
Standard ML Standard ML (SML) is a General-purpose programming language, general-purpose, High-level programming language, high-level, Modular programming, modular, Functional programming, functional programming language with compile-time type checking and t ...
, or Erlang.
Common Lisp Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ''ANSI INCITS 226-1994 (S2018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperli ...
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
Scheme Requests for Implementation (SRFI) 1 provides an implementation of filter for the language Scheme.filter
in SRFI 1
C++ provides the
algorithms In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...
remove_if (mutating) and remove_copy_if (non-mutating);
C++11 C++11 is a version of a joint technical standard, ISO/IEC 14882, by the International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC), for the C++ programming language. C++11 replaced the prior vers ...
additionally provides copy_if (non-mutating).remove_if
an

in the SGI Standard Template Library (STL) spec
Smalltalk Smalltalk is a purely object oriented programming language (OOP) that was originally created in the 1970s for educational use, specifically for constructionist learning, but later found use in business. It was created at Xerox PARC by Learni ...
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) -> -> 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 languages 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 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-to-all'' wh ...
* List comprehension * Guard (computing)


References

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