List comprehensions on:  
[Wikipedia]  
[Google]  
[Amazon]
A list comprehension is a
syntactic
In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure (constituency), ...
construct available in some
programming language
A programming language is a system of notation for writing computer programs. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
s for creating a list based on existing
lists
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby unio ...
. It follows the form of the mathematical ''
set-builder notation
In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy.
Defining ...
'' (''set comprehension'') as distinct from the use of
map
A map is a symbolic depiction emphasizing relationships between elements of some space, such as objects, regions, or themes.
Many maps are static, fixed to paper or some other durable medium, while others are dynamic or interactive. Although ...
and
filter
Filter, filtering or filters may refer to:
Science and technology
Computing
* Filter (higher-order function), in functional programming
* Filter (software), a computer program to process a data stream
* Filter (video), a software component tha ...
functions.
Overview
Consider the following example in
set-builder notation
In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy.
Defining ...
.
:
or often
:
This can be read, "
is the set of all numbers "2 times
" SUCH THAT
is an ELEMENT or MEMBER of the set of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s (
), AND
squared is greater than
."
The smallest natural number, x = 1, fails to satisfy the condition x
2>3 (the condition 1
2>3 is false) so 2 ยท1 is not included in S. The next natural number, 2, does satisfy the condition (2
2>3) as does every other natural number. Thus x consists of 2, 3, 4, 5... Since the set consists of all numbers "2 times x" it is given by S = . S is, in other words, the set of all even numbers greater than 2.
In this annotated version of the example:
:
*
is the variable representing members of an input set.
*
represents the input set, which in this example is the set of natural numbers
*
is a
predicate
Predicate or predication may refer to:
* Predicate (grammar), in linguistics
* Predication (philosophy)
* several closely related uses in mathematics and formal logic:
**Predicate (mathematical logic)
**Propositional function
**Finitary relation, o ...
expression acting as a filter on members of the input set.
*
is an output expression producing members of the new set from members of the input set that satisfy the predicate expression.
*
braces indicate that the result is a set
*
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
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby union ...
or
iterator
In computer programming, an iterator is an object that enables a programmer to traverse a container, particularly lists. Various types of iterators are often provided via a container's interface. Though the interface and semantics of a given iterat ...
:
* 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 = x <- x^2 > 3 ">.. x^2 > 3
Here, the list
../code> represents , 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
The existence of related constructs predates the use of the term "List Comprehension". The SETL
SETL (SET Language) is a very high-level programming language based on the mathematical theory of sets. It was originally developed by (Jack) Jacob T. Schwartz at the New York University (NYU) Courant Institute of Mathematical Sciences in the ...
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 :
print( _in_ _in_[2..N">_forall_m_in__.html" ;"title="..N.html" ;"title="..N.html" ;"title=" in _in_[2..N">_forall_m_in__">_n_mod_m_>_0;
The_computer_algebra_system_
_in_[2..N">_forall_m_in__">_n_mod_m_>_0;
The_computer_algebra_system_Axiom_(computer_algebra_system)">AXIOM
_
An_axiom,_postulate,_or_assumption_is_a__statement_that_is_taken_to_be_true,_to_serve_as_a_premise_or_starting_point_for_further_reasoning_and_arguments._The_word_comes_from_the_Ancient_Greek_word__(),_meaning_'that_which_is_thought_worthy_or_f_...
_(1973)_has_a_similar_construct_that_processes_stream_(computing).html" "title="Axiom_(computer_algebra_system).html" "title="..N"> in [2..N"> forall m in "> n mod m > 0;
The computer algebra system Axiom (computer algebra system)">AXIOM
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or f ...
(1973) has a similar construct that processes stream (computing)">stream
A stream is a continuous body of water, body of surface water Current (stream), flowing within the stream bed, bed and bank (geography), banks of a channel (geography), channel. Depending on its location or certain characteristics, a stream ...
s.
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 programming language, NPL from 1977. In his retrospective "Some History of Functional Programming Languages", [
David Turner recalls:
In a footnote attached to the term "list comprehension", Turner also notes
Burstall and Darlington's work with NPL influenced many functional programming languages during the 1980s, but not all included list comprehensions. An exception was Turner's influential, pure, lazy, functional programming language
Miranda, released in 1985. The subsequently developed standard pure lazy functional language
Haskell
Haskell () is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research and industrial applications, Haskell has pioneered a number of programming lan ...
includes many of Miranda's features, including list comprehensions.
Comprehensions were proposed as a query notation for databases and were implemented in the ''
Kleisli'' database query language.
Examples in different programming languages
Similar constructs
Monad comprehension
In Haskell, a
monad comprehension is a generalization of the list comprehension to other
monads in functional programming
In functional programming, a monad is a software design pattern with a structure that combines program fragments ( functions) and wraps their return values in a type with additional computation. In addition to defining a wrapping monadic type, m ...
.
Set comprehension
Version 3.x and 2.7 of the Python language introduces syntax for
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
comprehensions. Similar in form to list comprehensions, set comprehensions generate Python sets instead of lists.
>>> s =
>>> print(s)
>>> type(s)
>>>
Racket set comprehensions generate Racket sets instead of lists.
(for/set ( "ABCDABCD"#:unless (member v (string->list "CB")))
v))
Dictionary comprehension
Version 3.x and 2.7 of the Python language introduced a new syntax for
dictionary
A dictionary is a listing of lexemes from the lexicon of one or more specific languages, often arranged alphabetically (or by radical and stroke for ideographic languages), which may include information on definitions, usage, etymologies ...
comprehensions, similar in form to list comprehensions but which generate Pytho
dictsinstead of lists.
>>> s =
>>> s
>>>
Racket hash table comprehensions generate Racket hash tables (one implementation of the Racket dictionary type).
(for/hash ( val key) (in-indexed "ABCD") #:unless (member val (string->list "CB")))
(values key val))
Parallel list comprehension
The
Glasgow Haskell Compiler
The Glasgow Haskell Compiler (GHC) is an open-source native code compiler for the functional programming language Haskell.
It provides a cross-platform environment for the writing and testing of Haskell code and it supports numerous extensions, ...
has an extension called parallel list comprehension (also known as zip-comprehension) that permits multiple independent branches of qualifiers within the list comprehension syntax.
Whereas qualifiers separated by commas are dependent ("nested"), qualifier branches separated by pipes are evaluated in parallel (this does not refer to any form of multithreadedness: it merely means that the branches are
zipped
A zipper, zip, fly, or zip fastener, formerly known as a clasp locker, is a commonly used device for binding together two edges of fabric or other flexible material. Used in clothing (e.g. jackets and jeans), luggage and other bags, camping ...
).
-- regular list comprehension
a = x <- _y_<-_[3..5">..5_y_<-_[3..5
--_[(1,3),(1,4),(1,5),(2,3),(2,4)_...
--_zipped_list_comprehension
b_=_ _y_<-_[3..5">..5_y_<-_[3..5
--_[(1,3),(1,4),(1,5),(2,3),(2,4)_...
--_zipped_list_comprehension
b_=_[(x,y)_">_(x,y)_<-_zip_[1..5[3..5.html" ;"title="x,y)_.html" ;"title="..5.html" ;"title="..5 y <- [3..5">..5 y <- [3..5
-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...
-- zipped list comprehension
b = [(x,y) "> (x,y) <- zip [1..5[3..5">x,y)_.html" ;"title="..5.html" ;"title="..5 y <- [3..5">..5 y <- [3..5
-- [(1,3),(1,4),(1,5),(2,3),(2,4) ...
-- zipped list comprehension
b = [(x,y) "> (x,y) <- zip [1..5[3..5
-- [(1,3),(2,4),(3,5)]
-- parallel list comprehension
c = [(x,y) , x <- [1..5] , y <- [3..5
-- [(1,3),(2,4),(3,5)]
Racket's comprehensions standard library contains parallel and nested versions of its comprehensions, distinguished by "for" vs "for*" in the name. For example, the vector comprehensions "for/vector" and "for*/vector" create vectors by parallel versus nested iteration over sequences. The following is Racket code for the Haskell list comprehension examples.
> (for*/list ( (in-range 1 6) (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 ( (in-range 1 6) (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) >> b = 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).html" ;"title=" for x in zip(range(1, 6), 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)"> for x in zip(range(1, 6), 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 have arrays.
XQuery and XPath
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 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.
In XQuery, full XPath is available, but
FLWOR
The programming language XQuery defines FLWOR (pronounced 'flower') as an expression that supports iteration and binding of variables to intermediate results. FLWOR is an acronym: FOR, LET, WHERE, ORDER BY, RETURN. FLWOR is loosely analogous to ...
statements are also used, which is a more powerful comprehension construct.
for $b in //book
where $b pages < 400order by $b//title
return
Here the XPath //book is evaluated to create a sequence (aka list); the where clause is a functional "filter", the order by sorts the result, and the XML snippet is actually an
anonymous function
In computer programming, an anonymous function (function literal, lambda abstraction, lambda function, lambda expression or block) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to ...
that builds/transforms XML for each element in the sequence using the 'map' approach found in other functional languages.
So, in another functional language the above FLWOR statement may be implemented like this:
map(
newXML(shortBook, newXML(title, $1.title), newXML(firstPara, $1...))
filter(
lt($1.pages, 400),
xpath(//book)
)
)
LINQ in C#
C# 3.0 has a group of related features called
LINQ
Language Integrated Query (LINQ, pronounced "link") is a Microsoft .NET Framework component that adds native data querying capabilities to .NET languages, originally released as a major part of .NET Framework 3.5 in 2007.
LINQ extends the langu ...
, which defines a set of query operators for manipulating object enumerations.
var s = Enumerable.Range(0, 100).Where(x => x * x > 3).Select(x => x * 2);
It also offers an alternative comprehension syntax, reminiscent of SQL:
var s = from x in Enumerable.Range(0, 100) where x * x > 3 select x * 2;
LINQ provides a capability 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
In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of text (often source code) written in a formal language. Each node of the tree denotes a construct occurring ...
(AST) object, which is passed to the IQueryable object to interpret and execute.
This allows, amongst other things, for the IQueryable to
* rewrite an incompatible or inefficient comprehension
* translate the AST into another query language (e.g. SQL) for execution
C++
C++ does not have any language features directly supporting list comprehensions but
operator overloading
In computer programming, operator overloading, sometimes termed ''operator ad hoc polymorphism'', is a specific case of polymorphism, where different operators have different implementations depending on their arguments. Operator overloading is ...
(e.g., overloading
,
,
>>
,
>>=
) has been used successfully to provide expressive syntax for "embedded" query
domain-specific language
A domain-specific language (DSL) is a computer language specialized to a particular application domain. This is in contrast to a general-purpose language (GPL), which is broadly applicable across domains. There are a wide variety of DSLs, ranging f ...
s (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)
int main()
There is some effort in providing C++ with list-comprehension constructs/syntax similar to the set builder notation.
* In
Boost. Rang
library there is a notion of adaptor
that can be applied to any range and do filtering, transformation etc. With this library, the original Haskell example would look like (using Boost.Lambd
for anonymous filtering and transforming functions)
Full example:
counting_range(1,10) , filtered( _1*_1 > 3 ) , transformed(ret( _1*2 ))
* This implementation uses a macro and overloads the << operator. It evaluates any expression valid inside an 'if', and any variable name may be chosen. It's not
thread safety, threadsafe, however. Usage example:
list N;
list S;
for (int i = 0; i < 10; i++)
N.push_back(i);
S << list_comprehension(3.1415 * x, x, N, x * x > 3)
* This implementation provides head/tail slicing using classes and operator overloading, and the , operator for filtering lists (using functions). Usage example:
bool even(int x)
bool x2(int &x)
list l, t;
int x, y;
for (int i = 0; i < 10; i++)
l.push_back(i);
(x, t) = l , x2;
(t, y) = t;
t = l < 9;
t = t < 7 , even , x2;
* Language for Embedded Query and Traversal (LEESA
) is an embedded DSL in C++ that implements X-Path-like queries using operator overloading. The queries are executed on richly typed xml trees obtained using xml-to-c++ binding from an XSD. There is absolutely no string encoding. Even the names of the xml tags are classes and therefore, there is no way for typos. If a LEESA expression forms an incorrect path that does not exist in the data model, the C++ compiler will reject the code.
Consider a catalog xml.
Hamlet
9.99
William Shakespeare
England
...
...
LEESA provides
>>
for XPath's / separator. XPath's // separator that "skips" intermediate nodes in the tree is implemented in LEESA using what's known as Strategic Programming. In the example below, catalog_, book_, author_, and name_ are instances of catalog, book, author, and name classes, respectively.
// Equivalent X-Path: "catalog/book/author/name"
std::vector author_names =
evaluate(root, catalog_ >> book_ >> author_ >> name_);
// Equivalent X-Path: "catalog//name"
std::vector author_names =
evaluate(root, catalog_ >> DescendantsOf(catalog_, name_));
// Equivalent X-Path: "catalog//author "England"">ountry"England"
std::vector author_names =
evaluate(root, catalog_ >> DescendantsOf(catalog_, author_)
>> Select(author_, [](const author & a) )
>> name_);
See also
* Set-builder notation
* The Select (SQL), SELECT statement together with its FROM and WHERE clauses in
SQL
Notes and references
List Comprehensionin The Free On-line Dictionary of Computing, Editor Denis Howe.
* {{cite conference , first = Philip , last = Wadler , url = http://citeseer.ist.psu.edu/wadler92comprehending.html , title = Comprehending Monads , book-title = Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice , year = 1990
External links
* SQL-like set operations with list comprehension one-liners in th
Python Cookbook*
ttp://langexplr.blogspot.com/2007/02/list-comprehensions-across-languages_18.html List Comprehensions across languages
Axiom
Axiom stream examples
Clojure
Clojure API documentation - ''for'' macro
Common Lisp
Implementation of a Lisp comprehension macroby Guy Lapalme
Haskell
* The Haskell 98 Report, chapte
* The Glorious Glasgow Haskell Compilation System User's Guide, chapte
* The Hugs 98 User's Guide, chapte
OCaml
OCaml Batteries Included
Python
* The Python Tutorial
* Python Language Reference
* Python Enhancement Proposa
* Python Language Reference
* Python Enhancement Proposa
Programming constructs
Articles with example code
Articles with example Haskell code
Articles with example Python (programming language) code
Articles with example Racket code