Filter (higher-order Function) - Implementation

Implementation

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. SRFI 1 provides an implementation of filter for the Scheme programming language. 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:

filter :: (a -> Bool) -> -> 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.

Filter in various languages

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)	Or, via list comprehension: (for 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. 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.
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:
Haskell	filter pred list	Or, via list comprehension:
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
Objective-C (Cocoa in Mac OS X 10.4+)		pred is an NSPredicate object, which may be limited in expressiveness
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)	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. This extension is already implemented by most of the Prolog systems.
Python	filter(func, list)	Or, via list comprehension: . In Python 3.x, 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
S/R	Filter(pred,array) 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