Filter (higher-order function)
functional programming, filter is a higher-order functionthat 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 valuetrue.
In Haskell, the code example filter even [1..10] evaluates to the list 2, 4,…10 by applying the predicate
evento 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
evenreturns the boolean value false (with
function composition operator).
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]
Objective Caml, [http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
filter] in the
Objective Camlstandard library module
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
Common Lispprovides the functions
remove-if-not] in the
Common Lisp HyperSpec]
SRFI 1 provides an implementation of filter for the
Scheme programming language. [http://srfi.schemers.org/srfi-1/srfi-1.html#FilteringPartitioning
filter] in SRFI 1]
C++provides the algorithms
remove_if] and [http://www.sgi.com/tech/stl/remove_copy_if.html
remove_copy_if] in the SGI STL spec]
select:method for collections. Filter can also be realized using
list comprehensions in languages that support them.
filtercan be implemented like this: filter :: (a -> Bool) -> [a] -> [a] filter _  =  filter p (x:xs) | p x = x : filter p xs
otherwise = filter p xs
denotes the empty list, and
:denotes the concatenation operator used to create a new list from a given value and an existing list.
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. [http://haskell.org/onlinereport/standard-prelude.html#$vdropWhile
dropWhile] and [http://www.haskell.org/onlinereport/list.html#sect17.3
partition] ) are also common. A common
memory optimizationfor purely functionalprogramming languages is to have the input list and filtered result share the longest common tail ( tail-sharing).
Map (higher-order function)
Wikimedia Foundation. 2010.
Look at other dictionaries:
Fold (higher-order function) — In functional programming, fold, also known variously as reduce, accumulate, compress or inject, is a family of higher order functions that process a data structure in some order and build up a return value. Typically, a fold deals with two… … Wikipedia
Filter — may refer to: Chemistry, engineering and materials In chemistry, engineering, or household usage, a device to separate mixtures. See: * Filter (chemistry) * Water filter * Air filter * Oil filter * Pneumatic filter Optics and photography In… … Wikipedia
Filter design — is the process of designing a filter (in the sense in which the term is used in signal processing, statistics, and applied mathematics), often a linear shift invariant filter, which satisfies a set of requirements, some of which are contradictory … Wikipedia
Electronic filter — Electronic filters are electronic circuits which perform signal processing functions, specifically intended to remove unwanted signal components and/or enhance wanted ones. Electronic filters can be:*passive or active *analog or digital *discrete … Wikipedia
Butterworth filter — The Butterworth filter is one type of electronic filter design. It is designed to have a frequency response which is as flat as mathematically possible in the passband. Another name for them is maximally flat magnitude filters.The Butterworth… … Wikipedia
Low-pass filter — A low pass filter is a filter that passes low frequency signals but attenuates (reduces the amplitude of) signals with frequencies higher than the cutoff frequency. The actual amount of attenuation for each frequency varies from filter to filter … Wikipedia
Digital filter — A general finite impulse response filter with n stages, each with an independent delay, di, and amplification gain, ai. In electronics, computer science and mathematics, a digital filter is a system that performs mathematical operations on a… … Wikipedia
Elliptic filter — An elliptic filter (also known as a Cauer filter, named after Wilhelm Cauer) is an electronic filter with equalized ripple (equiripple) behavior in both the passband and the stopband. The amount of ripple in each band is independently adjustable … Wikipedia
Sallen–Key filter — A Sallen–Key filter is a type of active filter, particularly valued for its simplicity. The circuit produces a 2 pole (12 dB/octave) lowpass or highpass response using two resistors, two capacitors and (usually) a unity gain buffer amplifier.… … Wikipedia
Distributed element filter — Figure 1. A circuit featuring many of the f … Wikipedia