List comprehension

Template:Short description 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 (set comprehension) as distinct from the use of map and filter functions.

Overview

Consider the following example in mathematical set-builder notation.

<math>S=\{2\cdot x\mid x \in \mathbb{N},\ x^2>3\}</math>

or often

<math>S=\{2\cdot x : x \in \mathbb{N},\ x^2>3\}</math>

This can be read, "<math>S</math> is the set of all numbers "2 times <math>x</math>" SUCH THAT <math>x</math> is an ELEMENT or MEMBER of the set of natural numbers (<math>\mathbb{N}</math>), AND <math>x</math> squared is greater than <math>3</math>."

The smallest natural number, x = 1, fails to satisfy the condition x²>3 (the condition 1²>3 is false) so 2 ·1 is not included in S. The next natural number, 2, does satisfy the condition (2²>3) as does every other natural number. Thus x consists of 2, 3, 4, 5... Since the set Template:Var 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:

<math>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}}}\}</math>

• <math>x</math> is the variable representing members of an input set.
• <math>\mathbb{N}</math> represents the input set, which in this example is the set of natural numbers
• <math>x^2>3</math> is a predicate expression acting as a filter on members of the input set.
• <math>2\cdot x</math> is an output expression producing members of the new set from members of the input set that satisfy the predicate expression.
• <math>\{\}</math> braces indicate that the result is a set
• <math>\mid</math> <math>,</math> 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: <syntaxhighlight lang="haskell"> s = [ 2*x | x <- [0..], x^2 > 3 ] </syntaxhighlight>

Here, the list [0..] represents <math>\mathbb{N}</math>, 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 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 Template:Var:

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",<ref>Template:Cite conference</ref> 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 includes many of Miranda's features, including list comprehensions.

Comprehensions were proposed as a query notation for databases<ref>Comprehensions, a query notation for DBPLs</ref> and were implemented in the Kleisli database query language.<ref>The functional guts of the Kleisli query system</ref>

Similar constructs

Monad comprehension

In Haskell, a monad comprehension is a generalization of the list comprehension to other monads in functional programming.

Set comprehension

The Python language introduces syntax for set comprehensions starting in version 2.7. Similar in form to list comprehensions, set comprehensions generate Python sets instead of lists. <syntaxhighlight lang="python"> s: set[str] = {v for v in "ABCDABCD" if v not in "CB"} print(s)

1. prints {'A', 'D'}

print(type(s))

1. prints <class 'set'>

</syntaxhighlight>

Racket set comprehensions generate Racket sets instead of lists. <syntaxhighlight lang="scheme"> (for/set ([v "ABCDABCD"] #:unless (member v (string->list "CB")))

        v))

</syntaxhighlight>

Dictionary comprehension

The Python language introduced a new syntax for dictionary comprehensions in version 2.7, similar in form to list comprehensions but which generate Python dicts instead of lists. <syntaxhighlight lang="python"> s: dict[str] = {key: val for key, val in enumerate("ABCD") if val not in "CB"} print(s)

1. prints {0: 'A', 3: 'D'}

</syntaxhighlight>

Racket hash table comprehensions generate Racket hash tables (one implementation of the Racket dictionary type). <syntaxhighlight lang="scheme"> (for/hash ([(val key) (in-indexed "ABCD")]

          #:unless (member val (string->list "CB")))
 (values key val))

</syntaxhighlight>

Parallel list comprehension

The Glasgow Haskell Compiler has an extension named parallel list comprehension (also called 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 refers to no form of multithreadedness: it merely means that the branches are zipped). <syntaxhighlight lang="haskell"> -- regular list comprehension a = [(x,y) | x <- [1..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)] </syntaxhighlight>

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. <syntaxhighlight lang="scheme"> > (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)) </syntaxhighlight>

In Python, we could do as follows: <syntaxhighlight lang="python">

1. regular list comprehension

a: list[tuple[int, int]] = [(x, y) for x in range(1, 6) for y in range(3, 6)] print(a)

1. prints [(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), ...
2. parallel/zipped list comprehension

b: list[tuple[int, int]] = [x for x in zip(range(1, 6), range(3, 6))] print(b)

1. prints [(1, 3), (2, 4), (3, 5)]

</syntaxhighlight>

In Julia, practically the same results can be achieved as follows: <syntaxhighlight lang="julia">

1. regular array comprehension

a::Vector{Tuple{Int, Int}} = [(x, y) for x in 1:5 for y in 3:5]

1. parallel/zipped array comprehension

b::Vector{Tuple{Int, Int}} = [x for x in zip(1:3, 3:5)] </syntaxhighlight> 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 Extensible Markup Language (XML) database).

In XPath, the expression: <syntaxhighlight lang="xquery"> /library/book//paragraph[@style='first-in-chapter'] </syntaxhighlight> 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.<ref>Template:Cite web</ref>

In XQuery, full XPath is available, but FLWOR statements are also used, which is a more powerful comprehension construct.<ref>Template:Cite web</ref> <syntaxhighlight lang="xquery"> for $b in //book where $b[@pages < 400] order by $b//title return

 <shortBook>
   <title>{$b//title}</title>
   <firstPara>{($book//paragraph)[1]}</firstPara>
 </shortBook>

</syntaxhighlight> 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 Template:Tag 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: <syntaxhighlight lang="xquery"> map(

 newXML(shortBook, newXML(title, $1.title), newXML(firstPara, $1...))
 filter(
   lt($1.pages, 400),
   xpath(//book)
 )

) </syntaxhighlight>

LINQ in C#

C# 3.0 has a group of related features named Language Integrated Query (LINQ), which defines a set of query operators for manipulating object enumerations.

<syntaxhighlight lang="csharp"> IEnumerable<int> s = Enumerable.Range(0, 100).Where(x => x * x > 3).Select(x => x * 2); </syntaxhighlight>

It also offers an alternative comprehension syntax, reminiscent of Structured Query Language (SQL):

<syntaxhighlight lang="csharp"> IEnumerable<int> s = from x in Enumerable.Range(0, 100) where x * x > 3 select x * 2; </syntaxhighlight>

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++

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. <syntaxhighlight lang="cpp"> import std;

using std::vector;

template <typename Collection, typename Pred, typename Trans> Collection comprehend(Collection&& source, const Pred& predicate, const Trans& transformation) {

   // initialize destination
   Collection d = std::forward<C>(source);

   // filter elements
   d.erase(std::ranges::remove_if(d, predicate), d.end());

   // apply transformation
   std::ranges::for_each(d, transformation);

   return d;

}

int main(int argc, char* argv[]) {

   vector<int> range(10);
   // range is a list of 10 elements, all zero
   std::ranges::iota(range, 1);
   // range now contains 1, 2, ..., 10

   vector<int> result = comprehend(
       range,
       [](int x) -> bool { return x * x <= 3; },
       [](int& x) -> void { x *= 2; }
   );
   // result now contains 4, 6, ..., 20

} </syntaxhighlight>

Using std::views, this can instead be written as:

<syntaxhighlight lang="cpp"> import std;

using std::vector; using std::ranges::to; using std::views::filter; using std::views::transform;

int main(int argc, char* argv[]) {

   vector<int> range(10);
   // range is a list of 10 elements, all zero
   std::ranges::iota(range, 1);
   // range now contains 1, 2, ..., 10

   vector<int> result = range
       | filter([](int x) -> bool { return x * x > 3; })
       | transform([](int x) -> int { return x * 2; })
       | to<vector>();

} </syntaxhighlight>

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 (using Boost.Lambda [3] for anonymous filtering and transforming functions) (Full example):

<syntaxhighlight lang="cpp"> counting_range(1,10) | filtered( _1*_1 > 3 ) | transformed(ret<int>( _1*2 )) </syntaxhighlight>

• This<ref>Template:Cite web</ref> implementation uses a macro and overloads the << operator. It evaluates any expression valid inside an 'if', and any variable name may be chosen. It is not threadsafe, however. Usage example:

<syntaxhighlight lang="cpp"> using std::vector;

vector<int> a(10); vector<double> b;

std::ranges::iota(a, 1);

b << list_comprehension(3.1415 * x, x, a, x * x > 3) </syntaxhighlight>

• This<ref>Template:Cite web</ref> implementation provides head/tail slicing using classes and operator overloading, and the | operator for filtering lists (using functions). Usage example:

<syntaxhighlight lang="cpp"> using std::vector;

bool even(int x) {

   return x % 2 == 0; 

} bool x2(int& x) {

   x *= 2; 
   return true; 

}

vector<int> l(10); vector<int> t; int x = 0; int y = 0;

std::ranges::iota(l, 1);

(x, t) = l | x2; (t, y) = t;

t = l < 9; t = t < 7 | even | x2; </syntaxhighlight>

• Language for Embedded Query and Traversal (LEESA<ref>Template:Cite web</ref>) 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.

<syntaxhighlight lang="xml"> <catalog>

 <book>
   <title>Hamlet</title>
   <price>9.99</price>
   <author>
     <name>William Shakespeare</name>
     <country>England</country>
   </author>
 </book>
 <book>...</book>

... </catalog> </syntaxhighlight> 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. <syntaxhighlight lang="cpp"> using std::vector;

// declared variables Catalog catalog; Book book; Author author; Name name;

// Equivalent X-Path: "catalog/book/author/name" vector<Name> authorNames = evaluate(root, catalog >> book >> author >> name);

// Equivalent X-Path: "catalog//name" std::vector<Name> authorNames = evaluate(root, catalog >> descendantsOf(catalog, name));

// Equivalent X-Path: "catalog//author[country=="England"]" vector<name> authorNames = evaluate(root, catalog >> descendantsOf(catalog, author)

                       >> select(author, [](const Author& a) -> bool { return a.country() == "England"; })
                       >> name);

</syntaxhighlight>

See also

• Set-builder notation
• The SELECT statement together with its FROM and WHERE clauses in SQL

Notes and references

• List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.
• Template:Cite conference

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

Axiom

• Axiom stream examples

Clojure

• Clojure API documentation - for macro

Common Lisp

• Implementation of a Lisp comprehension macro by Guy Lapalme

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

• OCaml Batteries Included
• Language extensions introduced in OCaml Batteries Included

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.