A list comprehension is a syntactic construct ailable in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set-builder notation (set comprehension) as distinct from the use of map and filter functions.
Overview[edit]Consider the following example in mathematical set-builder notation.
S = { 2 ⋅ x ∣ x ∈ N , x 2 > 3 } {\displaystyle S=\{2\cdot x\mid x\in \mathbb {N} ,\ x^{2}>3\}}
or often
S = { 2 ⋅ x : x ∈ N , x 2 > 3 } {\displaystyle S=\{2\cdot x:x\in \mathbb {N} ,\ x^{2}>3\}}
This can be read, " S {\displaystyle S} is the set of all numbers "2 times x {\displaystyle x} " SUCH THAT x {\displaystyle x} is an ELEMENT or MEMBER of the set of natural numbers ( N {\displaystyle \mathbb {N} } ), AND x {\displaystyle x} squared is greater than 3 {\displaystyle 3} ."
is the set of all numbers "2 times
x
{\displaystyle x}
" SUCH THAT
x
{\displaystyle x}
), AND
x
{\displaystyle x}
."
The smallest natural number, x = 1, fails to satisfy the condition x2>3 (the condition 12>3 is false) so 2 ·1 is not included in S. The next natural number, 2, does satisfy the condition (22>3) as does every other natural number. Thus x consists of 2, 3, 4, 5... Since the set S consists of all numbers "2 times x" it is given by S = {4, 6, 8, 10,...}. S is, in other words, the set of all even numbers greater than 2.
In this annotated version of the example:
S = { 2 ⋅ x ⏟ output expression ∣ x ⏟ variable ∈ N ⏟ input set , x 2 > 3 ⏟ predicate } {\displaystyle S=\{\underbrace {2\cdot x} _{\color {Violet}{\text{output expression}}}\mid \underbrace {x} _{\color {Violet}{\text{variable}}}\in \underbrace {\mathbb {N} } _{\color {Violet}{\text{input set}}},\ \underbrace {x^{2}>3} _{\color {Violet}{\text{predicate}}}\}} x {\displaystyle x} is the variable representing members of an input set. N {\displaystyle \mathbb {N} } represents the input set, which in this example is the set of natural numbers x 2 > 3 {\displaystyle x^{2}>3} is a predicate expression acting as a filter on members of the input set. 2 ⋅ x {\displaystyle 2\cdot x} is an output expression producing members of the new set from members of the input set that satisfy the predicate expression. { } {\displaystyle \{\}} braces indicate that the result is a set ∣ {\displaystyle \mid } , {\displaystyle ,} the vertical bar is read as "SUCH THAT". The bar and the colon ":" are used interchangeably. commas separate the predicates and can be read as "AND".
x
{\displaystyle x}
is a predicate expression acting as a filter on members of the input set.
2
⋅
x
{\displaystyle 2\cdot x}
is an output expression producing members of the new set from members of the input set that satisfy the predicate expression.
{
}
{\displaystyle \{\}}
braces indicate that the result is a set
∣
{\displaystyle \mid }
,
{\displaystyle ,}
the vertical bar is read as "SUCH THAT". The bar and the colon ":" are used interchangeably.
commas separate the predicates and can be read as "AND".
A list comprehension has the same syntactic components to represent generation of a list in order from an input list or iterator:
A variable representing members of an input list. An input list (or iterator). An optional predicate expression. And an output expression producing members of the output list from members of the input iterable that satisfy the predicate.The order of generation of members of the output list is based on the order of items in the input.
In Haskell's list comprehension syntax, this set-builder construct would be written similarly, as:
s = [ 2*x | x 3 ]Here, the list [0..] represents N {\displaystyle \mathbb {N} } , x^2>3 represents the predicate, and 2*x represents the output expression.
List comprehensions give results in a defined order (unlike the members of sets); and list comprehensions may generate the members of a list in order, rather than produce the entirety of the list thus allowing, for example, the previous Haskell definition of the members of an infinite list.
History[edit]The existence of related constructs predates the use of the term "List Comprehension". The SETL programming language (1969) has a set formation construct which is similar to list comprehensions. E.g., this code prints all prime numbers from 2 to N:
print([n in [2..N] | ∀ m in {2..n - 1} | n mod m > 0]);The computer algebra system Axiom (1973) has a similar construct that processes streams.
The first use of the term "comprehension" for such constructs was in Rod Burstall and John Darlington's description of their functional programming language NPL from 1977. In his retrospective "Some History of Functional Programming Languages",[1] Did Turner recalls:
NPL was implemented in POP2 by Burstall and used for Darlington’s work on program transformation (Burstall & Darlington 1977). The language was first order, strongly (but not polymorphically) typed, purely functional, call-by-value. It also had "set expressions" e.g.,
setofeven (X) (for*/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y)) '((1 3) (1 4) (1 5) (2 3) (2 4) (2 5) (3 3) (3 4) (3 5) (4 3) (4 4) (4 5) (5 3) (5 4) (5 5)) > (for/list ([x (in-range 1 6)] [y (in-range 3 6)]) (list x y)) '((1 3) (2 4) (3 5))In Python, we could do as follows:
>>> # regular list comprehension >>> a = [(x, y) for x in range(1, 6) for y in range(3, 6)] [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ... >>> >>> # parallel/zipped list comprehension >>> b = [x for x in zip(range(1, 6), range(3, 6))] [(1, 3), (2, 4), (3, 5)]In Julia, practically the same results can be achieved as follows:
# regular array comprehension >>> a = [(x, y) for x in 1:5 for y in 3:5] # parallel/zipped array comprehension >>> b = [x for x in zip(1:3, 3:5)]with the only difference that instead of lists, in Julia, we he arrays.
XQuery and XPath[edit]Like the original NPL use, these are fundamentally database access languages.
This makes the comprehension concept more important, because it is computationally infeasible to retrieve the entire list and operate on it (the initial 'entire list' may be an entire Extensible Markup Language (XML) database).
In XPath, the expression:
/library/book//paragraph[@style='first-in-chapter']is conceptually evaluated as a series of "steps" where each step produces a list and the next step applies a filter function to each element in the previous step's output.[4]
In XQuery, full XPath is ailable, but FLWOR statements are also used, which is a more powerful comprehension construct.[5]
for $b in //book where $b[@pages x * x > 3).Select(x => x * 2);It also offers an alternative comprehension syntax, reminiscent of Structured Query Language (SQL):
var s = from x in Enumerable.Range(0, 100) where x * x > 3 select x * 2;LINQ provides an ability over typical list comprehension implementations. When the root object of the comprehension implements the IQueryable interface, rather than just executing the chained methods of the comprehension, the entire sequence of commands are converted into an abstract syntax tree (AST) object, which is passed to the IQueryable object to interpret and execute.
This enables many things, including for the IQueryable to:
Rewrite an incompatible or inefficient comprehension Translate the AST into another query language (e.g., SQL) to execute C++[edit]C++ has no language features directly supporting list comprehensions, but operator overloading (e.g., overloading |, >>, >>=) has been used successfully to provide expressive syntax for "embedded" query domain-specific languages (DSL). Alternatively, list comprehensions can be constructed using the erase–remove idiom to select elements in a container and the STL algorithm for_each to transform them.
#include #include #include using namespace std; template C comprehend(C&& source, const P& predicate, const T& transformation) { // initialize destination C d = forward(source); // filter elements d.erase(remove_if(begin(d), end(d), predicate), end(d)); // apply transformation for_each(begin(d), end(d), transformation); return d; } int main() { list range(10); // range is a list of 10 elements, all zero iota(begin(range), end(range), 1); // range now contains 1, 2, ..., 10 list result = comprehend( range, [](int x) { return x * x 3 ) | transformed(ret( _1*2 )) This[6] implementation uses a macro and overloads the > book_ >> author_ >> name_); // Equivalent X-Path: "catalog//name" std::vector author_names = evaluate(root, catalog_ >> DescendantsOf(catalog_, name_)); // Equivalent X-Path: "catalog//author[country=="England"]" std::vector author_names = evaluate(root, catalog_ >> DescendantsOf(catalog_, author_) >> Select(author_, [](const author & a) { return a.country() == "England"; }) >> name_); See also[edit] Set-builder notation The SELECT statement together with its FROM and WHERE clauses in SQL Notes and references[edit] ^ Turner, Did (2012). "Some history of functional programming languages" (PDF). International Symposium on Trends in Functional Programming. Berlin, Heidelberg: Springer. pp. 1–20. ^ Comprehensions, a query notation for DBPLs ^ The functional guts of the Kleisli query system ^ "2.1 Location Steps". XML Path Language (XPath). W3C. 16 November 1999. Archived from the original on 9 December 2012. Retrieved 24 December 2008. ^ "XQuery FLWOR Expressions". W3Schools. Archived from the original on 2011-10-08. ^ "Single-variable List Comprehension in C++ using Preprocessor Macros". Archived from the original on 2011-08-21. Retrieved 2011-01-09. ^ "C++ list comprehensions". Archived from the original on 2017-07-07. Retrieved 2011-01-09. ^ "Language for Embedded Query and Trersal (LEESA)". List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe. Wadler, Philip (1990). "Comprehending Monads". Proceedings of the 1990 ACM Conference on LISP and Functional Programming. Nice. External links[edit] SQL-like set operations with list comprehension one-liners in the Python Cookbook Discussion on list comprehensions in Scheme and related constructs List Comprehensions across languages Axiom[edit] Further information: Axiom (computer algebra system) and Axiom Axiom stream examples Clojure[edit] Further information: Clojure Clojure API documentation - for macro Common Lisp[edit] Further information: Common Lisp Implementation of a Lisp comprehension macro by Guy Lapalme Haskell[edit] Further information: Haskell The Haskell 98 Report, chapter 3.11 List Comprehensions. The Glorious Glasgow Haskell Compilation System User's Guide, chapter 7.3.4 Parallel List Comprehensions. The Hugs 98 User's Guide, chapter 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions). OCaml[edit] Further information: OCaml OCaml Batteries Included Language extensions introduced in OCaml Batteries Included Python[edit] Further information: Python (programming language) and Python The Python Tutorial, List Comprehensions. Python Language Reference, List displays. Python Enhancement Proposal PEP 202: List Comprehensions. Python Language Reference, Generator expressions. Python Enhancement Proposal PEP 289: Generator Expressions.