Filter (higher-order function)

Short description: 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`.

## Contents

* 1 Example
* 1.1 Visual example
* 2 Language comparison
* 3 Variants
* 4 See also
* 5 References

## 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)={True if x≡0(mod2)False if x≡1(mod2).

This function express that if x is even the return value is True, otherwise it's False. This is the predicate.

View of processing steps when applying filter function on a list

## Language comparison

Filter is a standard function for many programming languages, e.g., Haskell,[1] OCaml,[2] Standard ML,[3] or Erlang.[4] Common Lisp provides the functions `remove-if` and `remove-if-not`.[5] Scheme Requests for Implementation (SRFI) 1 provides an implementation of filter for the language Scheme.[6] C++ provides the algorithms `remove_if` (mutating) and `remove_copy_if` (non-mutating); C++11 additionally provides `copy_if` (non-mutating).[7] 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)/array`

`pred`{⍵/⍨⍺⍺ ⍵}`array` | The second example is an APL dop.
C# 3.0  | `ienum.Where(pred)`

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)[8]` | 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[5] in favor of the equivalent `remove-if` where the predicate is complemented.[9] 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`.[10]
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[11] the core standard contains closure application via `call/N`[12]
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.[13] 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`[14] and `partition`[15]) 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)
* List comprehension
* Guard (computing)

## References

1. ↑ `filter` in the Haskell Standard Prelude
2. ↑ `filter` in the OCaml standard library module `list`
3. ↑ "The List structure". The Standard ML Basis Library. http://www.standardml.org/Basis/list.html#SIG:LIST.filter:VAL. Retrieved 2007-09-25.
4. ↑ `filter/2` in the Erlang STDLIB Reference Manual documentation of the module `lists`
5. ↑ 5.0 5.1 Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT in the Common Lisp HyperSpec
6. ↑ `filter` in SRFI 1
7. ↑ `remove_if` and `remove_copy_if` in the SGI Standard Template Library (STL) spec
8. ↑ clojure.core/filter on ClojureDocs
9. ↑ Function COMPLEMENT in the Common Lisp HyperSpec
10. ↑ Function EVENP, ODDP in the Common Lisp HyperSpec
11. ↑ ISO/IEC 13211-1:1995/Cor 2:2012
12. ↑ "Draft technical corrigendum 2". http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call.
13. ↑ "Built-in Functions — Python 3.9.0 documentation". https://docs.python.org/3/library/functions.html#filter.
14. ↑ Haskell filter dropWhile
15. ↑ Haskell filter partition

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Filter (higher-order function). Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Filter_(higher-order_function)&oldid=262554"