From Wikipedia, the free encyclopedia

List comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It is analogous to the mathematical set-builder notation (set comprehension.) Consider the following example.

This can be read, "S is the list of all 2*x where x is an item in the list of natural numbers, and x squared is greater than 3." In Haskell's list comprehension syntax, this set-builder construct would be written similarly, as:

s = [ 2*x | x <- [0..], x^2 > 3 ] 

Here, the list [0..] represents N, and x^2>3 represents the conditional.

The following equations suffice to define list comprehensions (in Haskell's syntax). Metavariables are written in red.

[ expr | True ] = [ expr ]

[ expr | qual ] = [ e | qual, True ]

[ expr | bool, Quals ] = if bool then [ expr | Quals ] else []

[ expr | pat <- list, Quals ] = let f pat = [ expr | Quals ]
                                    f _   = []
                                in concatMap f list

[ expr | let decls, Quals ] = let decls
                              in [ expr | Quals ]

where expr ranges over expressions, pat over patterns, list over list-valued expressions, bool over boolean expressions, decls over declaration lists, qual over qualifiers, and Quals over sequences of qualifiers. f is a fresh variable.

A qualifier is either a generator drawing items from a list, a guard doing filtering, or a local declaration using let.

The function concatMap applies a function to each element of a list in order to obtain a list of lists, which it then concatenates.

The earliest reference to the list comprehension notation is in Rod Burstall and John Darlington's description of their programming language, NPL from 1977, but SETL already had a similar construct.^{[citation needed]} In the computer algebra system AXIOM, a similar construct processes streams.

Comprehensions were proposed as a query notation for databases [1] and were implemented in the Kleisli database query language [2].

In Haskell, list comprehensions can be rewritten as expressions involving the higher-order functions map and filter along with concat which concatenates a list of lists, or directly in terms of concatMap. For example, S above can be written directly as a list comprehension:

s = [ 2*x | x <- [0..], x^2 > 3] 

or in terms of map and filter:

s = map (2*) (filter (\x -> x^2 > 3) [0..])

or using a direct translation in terms of concatMap:

s = concatMap (\x -> if x^2 > 3 then [2*x] else []) [0..]

An example of a list comprehension using multiple generators:

pyth = [(x,y,z) | x <- [1..20], y <- [x..20], z <- [y..20], x^2 + y^2 == z^2]

which in terms of concatMap translates to the equivalent of:

pyth = concatMap
        (\x -> concatMap 
           (\y -> concatMap
              (\z -> if x^2 + y^2 == z^2 
                        then [(x,y,z)] 
                        else [])
              [y..20])
           [x..20])
        [1..20]

As can be seen from this example, list comprehensions can be a much more concise way to express certain lists.

Further information: C# 3.0 Language Integrated Query

var L = Enumerable.Range(0,100);
var S = from x in L where Math.Pow(x, 2)>3 select 2*x;

The previous code is syntactic sugar for the following code written using lambda expressions:

var L = Enumerable.Range(0, 100);   
var S = L.Where(x=>Math.Pow(x,2)>3).Select(x=>2*x);

Further information: Boo Programming Language for .NET/Mono

List with all the doubles from 0 to 10 (exclusive)

doubles = [i*2 for i in range(10)]

List with the names of the customers based on Rio de Janeiro

rjCustomers = [customer.Name for customer in customers if customer.State == "RJ"]

List comprehensions can be expressed with the loop macro's collect keyword. Conditionals are expressed with if, as follows:

(loop for x from 0 to 100 if (> (* x x) 3) collect (* 2 x))

L = lists:seq(0,100).
S = [2*X || X <- L, X*X > 3].

Further information: F# Programming Language

{ for x in 0..100 when x*x > 3 -> 2*x }

Or, more correctly for floating point values

{ for x in 0.0 .. 100.0 when x**2.0 > 3.0 -> 2.0*x }

Further information: Nemerle

$[x*2 | x in [0 .. 100], x*x > 3]

List comprehensions are supported in Perl through the use of a CPAN module, List::Comprehensions.

Further information: Python syntax and semantics: Generators

The Python programming language has a corresponding syntax for expressing list comprehensions. The near-equivalent example in Python is as follows:

L = range(100)   # Finite list from 0 to 99, since values are computed up-front.
S = [2*x for x in L if x**2 > 3]

A generator expression may be used in Python 2.4 to achieve functional equivalence with S using a generator to iterate an infinite list:

from itertools import count
S = (2*x for x in count() if x**2 > 3)

Using the for-comprehension:

val s = for (val x <- List.range(0, 100); x*x > 3) yield 2*x

S = [ 2*X || X = list::getMember_nd(L), X*X > 3 ]

Monad comprehension is a generalization of list comprehension to other monads in functional programming. The list comprehension syntax can be understood as operations in a monad, for the earlier example written in the monadic do-notation:

do x <- [0..]
   guard (x^2 > 3)
   return (2*x)

The use of guard requires that the monad has the additional operation mzero. Otherwise, the list comprehension becomes a do-block, each qualifier becomes an operation, and the result item is moved from the front to the final return operation.

Sometime before the Haskell 98 standard the list comprehension syntax was first generalized to monad comprehension but then specialized back as it caused type ambiguity: ['c'] wouldn't mean a list of one element, the character c, but the result of return 'c' in any monad.

The Glasgow Haskell Compiler 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, qualifier branches separated by pipes are evaluated in parallel. First consider the following list comprehension with conventional dependent qualifiers:

[(x,y) | x <- a, y <- b]

This takes items from lists a and b and produces a list of pairs of the items. For each item from a, each item from b is drawn in turn to get all combinations of the items. This specific case is the Cartesian product from set theory and relational algebra.

Now consider the following list comprehension with independent qualifiers provided by the extension:

[(x,y) | x <- a | y <- b]

The difference is that this doesn't produce all combinations. Instead, the first branch produces one item in turn from a and the second branch from b, and the result is a pairing of each item from a with one item from b. This resembles a zipper in aligning the items from the two lists.

Considering a rewrite to higher-order functions, parallel comprehension adds zipWith to the earlier map and filter. The example parallel comprehension could simply be rewritten as follows:

zipWith (,) a b

In the general case, each parallel branch is rewritten into a separate list comprehension, the result lists are zipped into an aligned list, and an outer list comprehension turns it into the result list.

• 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 (computer science)
  • Map (higher-order function)
• For other programming language constructs copied from the mathematical notation:
  • Guard (computing)
  • Pattern matching
  • Operator (programming)

• List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.
• Phil Trinder [3] Comprehensions, a query notation for DBPLs, Proceedings of the third international workshop on Database programming languages : bulk types & persistent data: bulk types & persistent data, Nafplion, Greece, Pages 55-68, 1992.
• Philip Wadler. Comprehending Monads. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990.
• Limsoon Wong [4] The Functional Guts of the Kleisli Query System, International Conference on Functional Programming, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, Pages 1-10, 2000.

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

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.

PostScript:

• Systems, Adobe (1999-02). PostScript Language Reference Manual, Third Edition. Addison-Wesley, pp. 524–524. 0-201-37922-8. 

Common Lisp

• Implementation of a Lisp comprehension macro by Guy Lapalme

Axiom:

• Axiom stream examples: [5]

• SQL-like set operations with list comprehension one-liners in the Python Cookbook
• http://lambda-the-ultimate.org/classic/message11326.html - Discussion on list comprehensions in Scheme and related constructs
• http://langexplr.blogspot.com/2007/02/list-comprehensions-across-languages_18.html - List Comprehensions across languages