Filter (higher-order 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

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

File:Filter-steps-loillierbe.gif

Language comparison

Filter is a standard function for many programming languages, e.g.,

Haskell,[http://haskell.org/onlinereport/standard-prelude.html#$vfilter filter] in the Haskell Standard Prelude

OCaml,[http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html filter] in the OCaml standard library module list

Standard ML,{{cite web|url=http://www.standardml.org/Basis/list.html#SIG:LIST.filter:VAL|work=The Standard ML Basis Library|title=The List structure|accessdate=2007-09-25}}

or Erlang.[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

Common Lisp provides the functions remove-if and remove-if-not.[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

Scheme Requests for Implementation (SRFI) 1 provides an implementation of filter for the language Scheme.[http://srfi.schemers.org/srfi-1/srfi-1.html#FilteringPartitioning filter] in SRFI 1

C++ provides the algorithms remove_if (mutating) and remove_copy_if (non-mutating); C++11 additionally provides copy_if (non-mutating).[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 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).

class="wikitable" style="font-size: 85%"

|+ Filter in various languages

! scope="col" | Language

! scope="col" | Filter

! scope="col" | Notes

APL

| (pred array)/array
or
pred{{codett|{⍵/⍨⍺⍺ ⍵}|apl}}array

| The second example is an APL [https://aplwiki.com/wiki/Dop dop].

C# 3.0

| ienum.Where(pred)
or
[https://msdn.microsoft.com/en-us/library/bb311043.aspx 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)[http://clojuredocs.org/clojure_core/1.3.0/clojure.core/filter clojure.core/filter on ClojureDocs]

| 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.[http://www.ai.mit.edu/projects/iiip/doc/CommonLISP/HyperSpec/Body/fun_complement.html Function COMPLEMENT] in the Common Lisp HyperSpec Thus the filter {{code|2=lisp|(remove-if-not #'oddp '(0 1 2 3))}} should be written {{code|2=lisp|(remove-if (complement #'oddp) '(0 1 2 3))}} or more simply: {{code|2=lisp|(remove-if #'evenp '(0 1 2 3))}} where evenp returns the inverted value of oddp.[http://clhs.lisp.se/Body/f_evenpc.htm Function EVENP, ODDP] in the Common Lisp HyperSpec

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

| 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]

| (#~ 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 [https://developer.apple.com/documentation/Cocoa/Reference/Foundation/Classes/NSPredicate_Class/Reference/NSPredicate.html 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[http://www.iso.org/iso/iso_catalogue/catalogue_tc/catalogue_detail.htm?csnumber=58033 ISO/IEC 13211-1:1995/Cor 2:2012] the core standard contains closure application via call/N{{Cite web|url=http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call|title=Draft technical corrigendum 2}}

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.{{Cite web|title=Built-in Functions — Python 3.9.0 documentation|url=https://docs.python.org/3/library/functions.html#filter|access-date=2020-10-28|website=docs.python.org}} 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 [https://doc.rust-lang.org/std/iter/trait.Iterator.html Iterator] and the filter method returns a new iterator; pred is a function (specifically [https://doc.rust-lang.org/std/ops/trait.FnMut.html FnMut]) that receives the iterator's item and returns a [https://doc.rust-lang.org/std/primitive.bool.html 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 R⁶RS

| (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[http://haskell.org/onlinereport/standard-prelude.html#$vdropWhile Haskell filter dropWhile] and partition[http://www.haskell.org/onlinereport/list.html#sect17.3 Haskell filter 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

Category:Higher-order functions

Category:Articles with example Haskell code