Filter (higher-order function)

---

title: "Filter (higher-order function)" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["higher-order-functions", "articles-with-example-haskell-code"] description: "Computer programming function" topic_path: "general/higher-order-functions" source: "https://en.wikipedia.org/wiki/Filter_(higher-order_function)" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Computer programming 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.

Example

In Haskell, the code example

::code[lang=haskell] 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 ::code[lang=haskell] 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) = \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 is even the return value is \mathrm{True}, otherwise it's \mathrm{False}. This is the predicate. ::figure[src="https://upload.wikimedia.org/wikipedia/commons/5/52/Filter-steps-loillierbe.gif" caption="View of processing steps when applying filter function on a list" alt="applying filter function processing steps"] ::

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: ::code[lang=haskell] 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).

::data[format=table title="Filter in various languages"]

Language	Filter	Notes
APL	(*pred* *array*)/*array*
or
*pred**array*	The second example is an APL dop.
C# 3.0	*ienum*.Where(*pred*)
or
The 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)`	2=lisp	(remove-if-not #'oddp '(0 1 2 3))}} should be written or more simply: 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
begin, end, result are iterators
predicate is reversed
D	std.algorithm.filter!(*pred*)(*list*)
Erlang	lists:filter(*Fun*, *List*)	Or, via list comprehension: {{code
Groovy	*list*.findAll(*pred*)
Haskell	filter *pred* *list*	Or, via list comprehension: `[x
Haxe	*list*.filter(*pred*)
`Lambda.filter(list, pred)
`	Or, via list comprehension: `[x	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		url=http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
Python	filter(*func*, *list*)	Or, via list comprehension: *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](https://doc.rust-lang.org/std/iter/trait.Iterator.html) and the filter method returns a new iterator; *pred* is a function (specifically [FnMut](https://doc.rust-lang.org/std/ops/trait.FnMut.html)) that receives the iterator's item and returns a [bool](https://doc.rust-lang.org/std/primitive.bool.html)
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
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

References

1. [http://haskell.org/onlinereport/standard-prelude.html#$vfilter filter] in the Haskell Standard Prelude
2. [http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html filter] in the [[OCaml]] standard library module list
3. "The List structure". The Standard ML Basis Library.
4. [http://www.erlang.org/doc/doc-5.5.4/lib/stdlib-1.14.4/doc/html/lists.html#filter/2 filter/2] in the Erlang STDLIB Reference Manual documentation of the module lists
5. [http://www.lispworks.com/documentation/HyperSpec/Body/f_rm_rm.htm#remove-if-not ''Function'' '''REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT'''] in the [[Common Lisp HyperSpec]]
6. [http://srfi.schemers.org/srfi-1/srfi-1.html#FilteringPartitioning filter] in SRFI 1
7. [http://www.sgi.com/tech/stl/remove_if.html remove_if] and [http://www.sgi.com/tech/stl/remove_copy_if.html remove_copy_if] in the SGI [[Standard Template Library]] (STL) spec
8. [http://clojuredocs.org/clojure_core/1.3.0/clojure.core/filter clojure.core/filter on ClojureDocs]
9. [http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_complement.html ''Function'' '''COMPLEMENT'''] in the [[Common Lisp HyperSpec]]
10. [http://clhs.lisp.se/Body/f_evenpc.htm ''Function'' '''EVENP, ODDP'''] in the [[Common Lisp HyperSpec]]
11. [http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=58033 ISO/IEC 13211-1:1995/Cor 2:2012]
12. "Draft technical corrigendum 2".
13. "Built-in Functions — Python 3.9.0 documentation".
14. [http://haskell.org/onlinereport/standard-prelude.html#$vdropWhile Haskell filter ''dropWhile'']
15. [http://www.haskell.org/onlinereport/list.html#sect17.3 Haskell filter ''partition'']

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::