A list comprehension is a syntactic construct available in some programming
languages for creating a list based on existing lists. It follows the form of
the mathematical set-builder notation as distinct from the use of map and filter
functions. Overview
Consider the following example in set-builder notation.
This can be read, " is the set of all numbers "2 times " where is an item in
the set of natural numbers, for which squared is greater than ."
The smallest natural number, x = 1, fails to satisfy the condition x2>3 so 2
·1 is not included in S. The next natural number, 2, does satisfy the
condition as does every other natural number. Thus S consists of 2 ·2, 2 ·3, 2
·4... so S = 4, 6, 8, 10,... ie, 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 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 and the comma are
separators. 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.
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: Here, the list [0..] represents , x^2>3
represents the predicate, and 2*x represents the output expression.
List comprehensions give results in a defined order; 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 SETL programming language had a set formation construct, and the computer
algebra system AXIOM has a similar construct that processes streams, but
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. Smalltalk block context messages which
constitute list comprehensions have been in that language since at least
Smalltalk-80. Burstall and Darlington's work with NPL
influenced many functional programming languages during the 1980s, but not all
included list comprehensions. An exception was the influential pure lazy
functional programming language Miranda, which was released in 1985. The
subsequently developed standard pure lazy functional language Haskell
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
The following provides a few examples of specific syntax used in programming
languages. Although the original example denotes an
infinite list, few languages can express that, so in some of those cases we show
how to take a subset of rather than a subset of .
= B-Prolog = A list of the form [T : E1 in D1, ...,
En in Dn, LocalVars, Goal] is interpreted as a list comprehension in
calls to @=/2 and constraints. A list comprehension is translated into a
foreach construct with an accumulator. = C# =
C# lazily generates results on demand. Results can be automatically processed
in parallel on a multi-core system using Parallel LINQ.
= Ceylon = { for if x * 2 }
= Clojure = Clojure generates infinite lazy
sequences. Use take to get the first N results from the infinite sequence.
An example without the infinite sequence:
= CoffeeScript = CoffeeScript brings list comprehensions
to JavaScript. = Common Lisp =
List comprehensions can be expressed with the loop macro's collect keyword.
Conditionals are expressed with if, as follows:
An infinite lazy sequence can be created in a variety of ways, such as the CLOS
object system or a yield macro. = Elixir =
The same example in Elixir: = Erlang =
The same example in Erlang: = F# =
The F# generator comprehension has the list comprehension syntax elements.
Generator comprehensions can be used to generate Lists, Sequences and Arrays.
Generators are of the form [for x in collection do ... yield expr] for lists
and seq {for x in collection do ... yield expr} for sequences. For example:
= Falcon = The "comp" generic method family
provides wide support for comprehension. For example, the "mfcomp" method can be
applied to an array: Falcon can also use functional
generators to provide input lists. For example, the following code uses a
continuation to create a set of pairs. Method "comp" was introduced in version
0.9.6, and methods "mcomp" and "mfcomp" in version 0.9.6.2.
= Groovy = Groovy supports list comprehension style
expressions for any kind of Java Collection including lists, sets, and
maps. The "it" variable is shorthand for the
implicit parameter to a closure. The above is equivalent to:
= Haskell = Please refer to the main example in the
overview. Here, the list [0..] generates natural
numbers one by one which get bound to variable x, x^2>3 represents the
predicate that either accepts or rejects a given variable's value, and 2*x
represents the result expression. There might be several generators and test
predicates in one list comprehension expression in Haskell, in effect
defining nested loops, e.g.: The above expression becomes
unproductive at some point, when new xs keep being generated only to be rejected
later on. This is so because any test can only reject a value it is given, not
any future ones. This can be dealt with using bounded list generators always or
by enclosing a generator inside a take or takeWhile call, limiting the number
of generated values. = Haxe =
Haxe 3 released with array and map comprehension.
However, Haxe 2's syntax required use of Lambda:
= JavaScript 1.7 = JavaScript 1.7 has array comprehensions.
The SpiderMonkey JavaScript engine of the popular Firefox browser from Mozilla
Foundation supports them. For example: The sequence of integers can be obtained
by prototyping the Number object, Or introducing a range function,
= Julia = Julia supports comprehensions using the
syntax: and multidimensional comprehensions
like: = Mathematica =
The Cases command with a RuleDelayed in the second argument provides a list
comprehension mechanism: Alternatively
= OCaml = - With Batteries
OCaml Batteries Included has uniform comprehension syntax for lists, arrays,
enumerations, lazy lists, sets, hashtables, etc.
Comprehension are of the form [? expression | x 3];
= Python = The Python programming language has a
corresponding syntax for expressing list comprehensions. The Python equivalent of
the above example is = Racket =
Racket provides functional versions of for-loops, which are essentially list
comprehension syntax: The imperative for can also be used,
combined with Racket's generator library to produce an infinite generator:
= Ruby = In the Ruby language you can use
multiple ways to simulate this function, for example:
Or you can define your own method: = Scala =
Using a for-expression: Using a collections:
= Scheme = Although there is no standard list
comprehension syntax in R5RS, many implementations provide an extension for
this. For example, in Chicken Scheme: There is also a portable library SRFI/42
"Eager Comprehensions", which in particular includes list comprehensions:
= SETL = = Smalltalk =
= SuperCollider = In SuperCollider list comprehensions are
implemented as Routines, whose results can be collected with the message 'all'.
A shortcut syntax is provided for defining list comprehensions, which
internally translates to a routine. = Visual Prolog =
Similar constructs = Monad comprehension =
In Haskell, a monad comprehension is a generalization of the list comprehension
to other monads in functional programming.
= Set comprehension = Version 3.x and 2.7 of the Python
language introduces syntax for set comprehensions. Similar in form to list
comprehensions, set comprehensions generate Python sets instead of lists.
Racket set comprehensions generate Racket sets instead of lists.
= Dictionary comprehension = Version 3.x and 2.7 of the Python
language introduced a new syntax for dictionary comprehensions, similar in
form to list comprehensions but which generate Python dicts instead of lists.
Racket hash table comprehensions generate Racket hash tables.
= Parallel list comprehension = The Glasgow Haskell Compiler has an
extension called parallel list comprehension that permits multiple
independent branches of qualifiers within the list comprehension syntax.
Whereas qualifiers separated by commas are dependent, qualifier branches
separated by pipes are evaluated in parallel.
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.
In Python we could do as follows: = 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.
In XPath, the expression: 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 statements are also used, which is
a more powerful comprehension construct. Here the XPath book is evaluated to
create a sequence; the where clause is a functional "filter", the order by sorts
the result, and the ... XML snippet is actually an anonymous function 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:
= LINQ in C# = C# 3.0 has a group of related features
called LINQ, which defines a set of query operators for manipulating object
enumerations. It also offers an alternative
comprehension syntax, reminiscent of SQL:
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 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 for execution
= C++ = C++ does not have any language features
directly supporting list comprehensions but operator overloading has been used
successfully to provide expressive syntax for "embedded" query DSLs.
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. There is some effort in providing C++
with list-comprehension constructs/syntax similar to the set
builder notation. In Boost.Range [1] library there is a
notion of adaptors [2] that can be applied to any range and do filtering,
transformation etc. With this library, the original Haskell example would look
like: Full example is here:
http:codepad.org/y4bpgLJu This implementation uses a macro and
overloads the > for X-Path's / separator. Interestingly, X-Path'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. See also
The SELECT statement together with its FROM and WHERE clauses in SQL
Programming language Mathematical notation
Monads in functional programming for monads and monadic notation in general
For other programming language constructs used to process sequences:
Generator Map
For other programming language constructs copied from the mathematical
notation: Guard
Pattern matching Operator
Notes and references List Comprehension in The Free On-line
Dictionary of Computing, Editor Denis Howe.
Trinder, Phil. "Comprehensions, a query notation for DBPLs". Proceedings of the
third international workshop on Database programming languages: bulk types &
persistent data, Nafplion, Greece. pp. 55–68.
Wadler, Philip. "Comprehending Monads". Proceedings of the 1990 ACM Conference
on LISP and Functional Programming, Nice.
Wong, Limsoon. "The Functional Guts of the Kleisli Query System". Proceedings
of the fifth ACM SIGPLAN international conference on Functional programming.
International Conference on Functional Programming. pp. 1–10.
= 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.
= OCaml = OCaml Batteries Included
Language extensions introduced in OCaml Batteries Included
= Python = Python Reference Manual, chapter 5.2.4
List displays. Python Enhancement Proposal PEP 202:
List Comprehensions. Python Reference Manual, chapter 5.2.5
Generator expressions. Python Enhancement Proposal PEP 289:
Generator Expressions. = Common Lisp =
Implementation of a Lisp comprehension macro by Guy Lapalme
= Clojure = Clojure API documentation - for macro
= Axiom = Axiom stream examples
External links 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