**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Filter (higher-order function)

Summary

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.
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).
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 :
This function express that if is even the return value is , otherwise it's . This is the predicate.
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.
Scheme Requests for Implementation (SRFI) 1 provides an implementation of filter for the language Scheme.
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) -> [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).

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (6)

Related concepts (15)

CS-119(k): Information, Computation, Communication

D'une part, le cours aborde: (1) la notion d'algorithme et de représentation de l'information, (2) l'échantillonnage d'un signal et la compression de données et (3) des aspects
liés aux systèmes: ordi

CS-214: Software construction

Learn how to design and implement reliable, maintainable, and efficient software using a mix of programming skills (declarative style, higher-order functions, inductive types, parallelism) and
fundam

CS-628: Interactive Theorem Proving CS

A hands-on introduction to interactive theorem proving, proofs as programs, dependent types, and to the Coq proof assistant. Come learn how to write bug-free code!

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. 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, ...

Julia is a high-level, general-purpose dynamic programming language. Its features are well suited for numerical analysis and computational science. Distinctive aspects of Julia's design include a type system with parametric polymorphism in a dynamic programming language; with multiple dispatch as its core programming paradigm. Julia supports concurrent, (composable) parallel and distributed computing (with or without using MPI or the built-in corresponding to "OpenMP-style" threads), and direct calling of C and Fortran libraries without glue code.

In many programming languages, map is the name of a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called apply-to-all when considered in functional form. The concept of a map is not limited to lists: it works for sequential containers, tree-like containers, or even abstract containers such as futures and promises. Suppose we have a list of integers [1, 2, 3, 4, 5] and would like to calculate the square of each integer.

Related lectures (45)

Avoiding Variable CaptureCS-210: Functional programming

Explores variable capture in higher-order functions and the importance of variable renaming.

Higher-Order Functions Using Naive SubstitutionsCS-210: Functional programming

Explores higher-order functions, environments, evaluation using substitution, and examples like twice factorial.

Combinatorial Search and For-ExpressionsCS-210: Functional programming

Explores combinatorial search and introduces for-expressions as a more intuitive way to manipulate lists in Scala.