Filter (higher-order function)

On this page

Higher-order function that selects elements from a data structure based on a predicate 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.

We don't have any images related to Filter (higher-order function) yet.

You can add one yourself here.

We don't have any YouTube videos related to Filter (higher-order function) yet.

You can add one yourself here.

We don't have any PDF documents related to Filter (higher-order function) yet.

You can add one yourself here.

We don't have any Books related to Filter (higher-order function) yet.

You can add one yourself here.

We don't have any archived web articles related to Filter (higher-order function) yet.

You can submit a link to a page to archive here.

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).

Visual example

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 : f ( x ) = { T r u e if x ≡ 0 ( mod 2 ) F a l s e if x ≡ 1 ( mod 2 ) . {\displaystyle f(x)={\begin{cases}\mathrm {True} &{\text{ if }}x\equiv 0{\pmod {2}}\\\mathrm {False} &{\text{ if }}x\equiv 1{\pmod {2}}.\end{cases}}}

This function express that if x {\displaystyle x} is even the return value is T r u e {\displaystyle \mathrm {True} } , otherwise it's F a l s e {\displaystyle \mathrm {False} } . This is the predicate.

Language comparison

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).

Filter in various languages

Language	Filter	Notes
APL	(pred array)/arrayorpred{⍵/⍨⍺⍺ ⍵}array	The second example is an APL dop.
C# 3.0	ienum.Where(pred)orThe 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)⁸	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⁹ in favor of the equivalent remove-if where the predicate is complemented.¹⁰ 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.¹¹
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) ]
Groovy	list.findAll(pred)
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)
Julia	filter(pred, array)	The filter function also accepts dict datatype. Or, via list comprehension: [x for x in array if pred(x)]
Java 8+	stream.filter(pred)
JavaScript 1.6	array.filter(pred)
Kotlin	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¹² the core standard contains closure application via call/N¹³
Python	filter(func, list)	Or, via list comprehension: [x for x in list if pred(x)]. In Python 3, 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
Rust	iterator.filter(pred)	iterator is an Iterator and the filter method returns a new iterator; pred is a function (specifically FnMut) that receives the iterator's item and returns a bool
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)(remove inverted pred list)(partition pred list 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¹⁵ 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).

References

filter in the Haskell Standard Prelude http://haskell.org/onlinereport/standard-prelude.html#$vfilter ↩
filter in the OCaml standard library module list http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html ↩
"The List structure". The Standard ML Basis Library. Retrieved 2007-09-25. http://www.standardml.org/Basis/list.html#SIG:LIST.filter:VAL ↩
filter/2 in the Erlang STDLIB Reference Manual documentation of the module lists http://www.erlang.org/doc/doc-5.5.4/lib/stdlib-1.14.4/doc/html/lists.html#filter/2 ↩
Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT in the Common Lisp HyperSpec http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#remove-if-not ↩
filter in SRFI 1 http://srfi.schemers.org/srfi-1/srfi-1.html#FilteringPartitioning ↩
remove_if and remove_copy_if in the SGI Standard Template Library (STL) spec http://www.sgi.com/tech/stl/remove_if.html ↩
clojure.core/filter on ClojureDocs http://clojuredocs.org/clojure_core/1.3.0/clojure.core/filter ↩
Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT in the Common Lisp HyperSpec http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#remove-if-not ↩
Function COMPLEMENT in the Common Lisp HyperSpec http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_complement.html ↩
Function EVENP, ODDP in the Common Lisp HyperSpec http://clhs.lisp.se/Body/f_evenpc.htm ↩
ISO/IEC 13211-1:1995/Cor 2:2012 http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=58033 ↩
"Draft technical corrigendum 2". http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call ↩
"Built-in Functions — Python 3.9.0 documentation". docs.python.org. Retrieved 2020-10-28. https://docs.python.org/3/library/functions.html#filter ↩
Haskell filter dropWhile http://haskell.org/onlinereport/standard-prelude.html#$vdropWhile ↩
Haskell filter partition http://www.haskell.org/onlinereport/list.html#sect17.3 ↩

Example

Visual example

Language comparison

Variants

See also

References