Filter (higher-order function)
In functional programming, filter is a higher-order function that processes a data structure (typically 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 |
[edit] 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).
[edit] Implementation
Filter is a standard function for many programming languages, e.g. Haskell,[1] Objective Caml,[2] Standard ML,[3] or Erlang.[4] Common Lisp provides the functions remove-if and remove-if-not.[5] SRFI 1 provides an implementation of filter for the Scheme programming language.[6] 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) | p x = x : filter p xs
| otherwise = filter p xs
Here, [] denotes the empty list, and : denotes the concatenation operator used to create a new list from a given value and an existing list.
| Language | Filter | Notes |
|---|---|---|
| C# 3.0 | ienum.Where(pred) | Where is an extension method ienum is an IEnumerable Similarly in all .NET languages |
| Clojure | (filter predicate list)[7] | 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.[8] 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.[9] |
| D | std.algorithm.filter!(pred)(list) | |
| Erlang | lists:filter(Fun, List) | Or, via list comprehension: [ X || X <- List, Fun(X) ] |
| Haskell | filter pred list | 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) |
| JavaScript 1.6 | 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 |
| OCaml, Standard ML | List.filter pred list | |
| PHP | array_filter(array, pred) | |
| Perl | grep block list grep expr, list |
|
| Prolog | filter(+Closure,+List,-List) | The possibility to apply closures is not yet part of the ISO core standard, but there is currently a corrigendum around that proposes an appropriate extension [10]. This extension is already implemented by most of the Prolog systems. |
| Python | filter(func, list) | Or, via list comprehension: [x for x in list if pred(x)] |
| Ruby | enum.find_all {block} enum.select {block} |
enum is an Enumeration |
| 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) | |
| Smalltalk | aCollection select: aBlock |
[edit] Variants
Filter creates its result without modifying the original list. Many programming languages also provide variants that destructively modify the list argument instead for performance reasons. Other variants of filter (like e.g. 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).
[edit] References
- ^
filterin the Haskell Standard Prelude - ^
filterin the Objective Caml standard library modulelist - ^ "The List structure". The Standard ML Basis Library. http://www.standardml.org/Basis/list.html#SIG:LIST.filter:VAL. Retrieved 2007-09-25.
- ^
filter/2in the Erlang STDLIB Reference Manual documentation of the modulelists - ^ a b Function REMOVE, REMOVE-IF, REMOVE-IF-NOT, DELETE, DELETE-IF, DELETE-IF-NOT in the Common Lisp HyperSpec
- ^
filterin SRFI 1 - ^ clojure.core/filter on ClojrueDocs
- ^ Function COMPLEMENT in the Common Lisp HyperSpec
- ^ Function EVENP, ODDP in the Common Lisp HyperSpec
- ^ http://www.complang.tuwien.ac.at/ulrich/iso-prolog/dtc2#call
[edit] See also
| This computer science article is a stub. You can help Wikipedia by expanding it. |