Filter (higher-order function)

<h2 id="example">Example</h2>
In <a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a>, 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 <a href="/facts/Function_composition_operator/HMADGqKA">function composition operator</a>).

<h3>Visual example</h3>
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.

<h2 id="language-comparison">Language comparison</h2>
Filter is a standard function for many <a href="/facts/Programming_language/cWTYbgWa">programming languages</a>, e.g.,
Haskell,<a class="footnote-ref" id="fnref:1" href="#fn:1">1</a>
<a href="/facts/OCaml/ThBGLND8">OCaml</a>,<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
<a href="/facts/Standard_ML/4LaEq9tA">Standard ML</a>,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
or <a href="/facts/Erlang_(programming_language)/2PuxmzT3">Erlang</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
<a href="/facts/Common_Lisp/mq1pRbSF">Common Lisp</a> provides the functions remove-if and remove-if-not.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
<a href="/facts/Scheme_Requests_for_Implementation/I5lcAax9">Scheme Requests for Implementation</a> (SRFI) 1 provides an implementation of filter for the language <a href="/facts/Scheme_(programming_language)/0aGdf3SC">Scheme</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
<a href="/facts/C%252B%252B/Et0F2qn9">C++</a> provides the <a href="/facts/Algorithm_(C%252B%252B)/DeedBBhb">algorithms</a> remove_if (mutating) and remove_copy_if (non-mutating); <a href="/facts/C%252B%252B11/fI3YCoKQ">C++11</a> additionally provides copy_if (non-mutating).<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> <a href="/facts/Smalltalk/Ru2UPVDE">Smalltalk</a> provides the select: method for collections. Filter can also be realized using <a href="/facts/List_comprehension/aYAax9k0">list comprehensions</a> 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<table><tbody><tr><th scope="col">Language</th><th scope="col">Filter</th><th scope="col">Notes</th></tr><tr><td><a href="/facts/APL_(programming_language)/E2sb98gC">APL</a></td><td>(pred array)/arrayorpred{⍵/⍨⍺⍺ ⍵}array</td><td>The second example is an APL <a href="https://aplwiki.com/wiki/Dop">dop</a>.</td></tr><tr><td><a href="/facts/C_Sharp_(programming_language)/UC2gxeyb">C#</a> 3.0</td><td>ienum.Where(pred)or<a href="https://msdn.microsoft.com/en-us/library/bb311043.aspx">The where clause</a></td><td>Where is an extension method ienum is an IEnumerable Similarly in all .NET languages</td></tr><tr><td><a href="/facts/CFML/AbjNUunm">CFML</a></td><td>obj.filter(func)</td><td>Where obj is an array or a structure. The func receives as an argument each element's value.</td></tr><tr><td><a href="/facts/Clojure/3JRNxKXx">Clojure</a></td><td>(filter predicate list)<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></td><td>Or, via <a href="/facts/List_comprehension/aYAax9k0">list comprehension</a>: (for [x list :when (pred x)] x)</td></tr><tr><td><a href="/facts/Common_Lisp/mq1pRbSF">Common Lisp</a></td><td>(remove-if inverted-pred list)(remove-if (complement pred) list)(remove-if-not pred list)</td><td>The function remove-if-not has been deprecated<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> in favor of the equivalent remove-if where the predicate is complemented.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> 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.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></td></tr><tr><td><a href="/facts/C%252B%252B/Et0F2qn9">C++</a></td><td>std::remove_copy_if(begin, end, result, prednot)std::copy_if(begin, end, result, pred) (C++11)</td><td>in header <algorithm> begin, end, result are iterators predicate is reversed</td></tr><tr><td><a href="/facts/D_(programming_language)/4qIzRjkF">D</a></td><td>std.algorithm.filter!(pred)(list)</td><td></td></tr><tr><td><a href="/facts/Erlang_(programming_language)/2PuxmzT3">Erlang</a></td><td>lists:filter(Fun, List)</td><td>Or, via <a href="/facts/List_comprehension/aYAax9k0">list comprehension</a>: [ X || X <- List, Fun(X) ]</td></tr><tr><td><a href="/facts/Groovy_(programming_language)/vGAckbte">Groovy</a></td><td>list.findAll(pred)</td><td></td></tr><tr><td><a href="/facts/Haskell_(programming_language)/4Htv9WLu">Haskell</a></td><td>filter pred list</td><td>Or, via <a href="/facts/List_comprehension/aYAax9k0">list comprehension</a>: [x | x <- list, pred x]</td></tr><tr><td><a href="/facts/Haxe/jp87sM7P">Haxe</a></td><td>list.filter(pred)Lambda.filter(list, pred)</td><td>Or, via <a href="/facts/List_comprehension/aYAax9k0">list comprehension</a>: [x | x <- list, pred x]</td></tr><tr><td><a href="/facts/J_(programming_language)/EdIVMBj7">J</a></td><td>(#~ pred) list</td><td>An example of a monadic hook. # is copy, ~ reverses arguments. (f g) y = y f (g y)</td></tr><tr><td><a href="/facts/Julia_(programming_language)/AoB0PJ9C">Julia</a></td><td>filter(pred, array)</td><td>The filter function also accepts dict datatype. Or, via <a href="/facts/List_comprehension/aYAax9k0">list comprehension</a>: [x for x in array if pred(x)]</td></tr><tr><td><a href="/facts/Java_(programming_language)/9ScgFyAL">Java</a> 8+</td><td>stream.filter(pred)</td><td></td></tr><tr><td><a href="/facts/JavaScript/XhhIIEsl">JavaScript</a> 1.6</td><td>array.filter(pred)</td><td></td></tr><tr><td><a href="/facts/Kotlin_(programming_language)/CrAqIFLn">Kotlin</a></td><td>array.filter(pred)</td><td></td></tr><tr><td><a href="/facts/Mathematica/dRwoGFG2">Mathematica</a></td><td>Select[list, pred]</td><td></td></tr><tr><td><a href="/facts/Objective-C/5mM557BW">Objective-C</a> (<a href="/facts/Cocoa_(API)/p10p5aFI">Cocoa</a> in Mac <a href="/facts/OS_X/Y93vVpTm">OS X</a> 10.4+)</td><td>[array filteredArrayUsingPredicate:pred]</td><td>pred is an <a href="https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSPredicate_Class/Reference/NSPredicate.html">NSPredicate</a> object, which may be limited in expressiveness</td></tr><tr><td><a href="/facts/F_Sharp_(programming_language)/jdXHnYz5">F#</a>, <a href="/facts/OCaml/ThBGLND8">OCaml</a>, <a href="/facts/Standard_ML/4LaEq9tA">Standard ML</a></td><td>List.filter pred list</td><td></td></tr><tr><td><a href="/facts/PARI%2fGP/JhTL8ysP">PARI/GP</a></td><td>select(expr, list)</td><td>The order of arguments is reversed in v. 2.4.2.</td></tr><tr><td><a href="/facts/Perl/fx31kjlT">Perl</a></td><td>grep block list grep expr, list</td><td></td></tr><tr><td><a href="/facts/PHP/vU6YRJX0">PHP</a></td><td>array_filter(array, pred)</td><td></td></tr><tr><td><a href="/facts/Prolog/r5h66Qh1">Prolog</a></td><td>filter(+Closure,+List,-List)</td><td>Since ISO/IEC 13211-1:1995/Cor.2:2012<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> the core standard contains closure application via call/N<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a></td></tr><tr><td><a href="/facts/Python_(programming_language)/YbuGqofa">Python</a></td><td>filter(func, list)</td><td>Or, via <a href="/facts/List_comprehension/aYAax9k0">list comprehension</a>: [x for x in list if pred(x)]. In Python 3, filter was changed to return an <a href="/facts/Iterator/f0HhTBWz">iterator</a> rather than a list.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> 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.</td></tr><tr><td><a href="/facts/Ruby_(programming_language)/BeYSaPSR">Ruby</a></td><td>enum.find_all {block} enum.select {block}</td><td>enum is an Enumeration</td></tr><tr><td><a href="/facts/Rust_(programming_language)/8JNMV19F">Rust</a></td><td>iterator.filter(pred)</td><td>iterator is an <a href="https://doc.rust-lang.org/std/iter/trait.Iterator.html">Iterator</a> and the filter method returns a new iterator; pred is a function (specifically <a href="https://doc.rust-lang.org/std/ops/trait.FnMut.html">FnMut</a>) that receives the iterator's item and returns a <a href="https://doc.rust-lang.org/std/primitive.bool.html">bool</a></td></tr><tr><td><a href="/facts/S_(programming_language)/VTG29WnE">S</a>, <a href="/facts/R_(programming_language)/LSrkr8K8">R</a></td><td>Filter(pred,array)array[pred(array)]</td><td>In the second case, pred must be a vectorized function</td></tr><tr><td><a href="/facts/Scala_(programming_language)/ebL8o6AK">Scala</a></td><td>list.filter(pred)</td><td>Or, via for-comprehension: for(x <- list; if pred) yield x</td></tr><tr><td><a href="/facts/Scheme_(programming_language)/0aGdf3SC">Scheme</a> R6RS</td><td>(filter pred list)(remove inverted pred list)(partition pred list list)</td><td></td></tr><tr><td><a href="/facts/Smalltalk/Ru2UPVDE">Smalltalk</a></td><td>aCollection select: aBlock</td><td></td></tr><tr><td><a href="/facts/Swift_(programming_language)/A7qHQC32">Swift</a></td><td>array.filter(pred) filter(sequence, pred)</td><td></td></tr><tr><td><a href="/facts/XPath/0eCtJoj7">XPath</a>, <a href="/facts/XQuery/47Ep0fSS">XQuery</a></td><td>list[block] filter(list, func)</td><td>In block the context item . holds the current value</td></tr></tbody></table>
<h2 id="variants">Variants</h2>
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<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> and partition<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>) are also common. A common <a href="/facts/Memory_optimization/nXz6RpRM">memory optimization</a> for <a href="/facts/Purely_functional_programming_language/am3DcNAd">purely functional programming languages</a> is to have the input list and filtered result share the longest common tail (<a href="/facts/Tail-sharing/Ik4JTgJW">tail-sharing</a>).

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Map_(higher-order_function)/GdzN4UJl">Map (higher-order function)</a></li>
<li><a href="/facts/List_comprehension/aYAax9k0">List comprehension</a></li>
<li><a href="/facts/Guard_(computing)/QsmS63NU">Guard (computing)</a></li></ul>

<h2 id="references">References</h2>

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

Filter (higher-order function) open-in-new

Filter (higher-order function)