List comprehension

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.

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

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.

Contents

[edit] Translation into list functions

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.

[edit] History

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]

[edit] Forms of list comprehension

Note: while the original example denotes an infinite list, few languages can express that, so in most cases we show how to take a subset of 0,1,...,100 rather than a subset of \mathbb{N}.

[edit] In Haskell

Further information: Haskell

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.

[edit] In C#

Further information: C# 3.0 Language Integrated Query
var ns = from x in Enumerable.Range(0,100)
         where x*x > 3
         select x*2;

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

var ns = Enumerable.Range(0, 100)
        .Where(x => x*x > 3)
        .Select(x => x*2);

[edit] In Boo

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"]

[edit] In Common Lisp

Further information: Common Lisp

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

[edit] In Erlang

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

[edit] In F#

Further information: F#
{ 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 }

[edit] In JavaScript

Further information: JavaScript

Borrowing from Python, JavaScript 1.7 and later have array comprehensions[3]. Although this feature has been proposed for inclusion in the fourth edition ECMAScript standard, Mozilla is the only implementation that currently supports it.

/* There is no "range" function in JavaScript's standard
   library, so the application must provide it. */
function range(n) {
  for (var i = 0; i < n; i++)
    yield i;
}
 
[2 * x for (x in range(100)) if (x * x > 3)]

JavaScript 1.8 adds Python-like generator expressions.

[edit] In Nemerle

Further information: Nemerle
$[x*2 | x in [0 .. 100], x*x > 3]

[edit] In Perl

Further information: Perl

List comprehensions are supported in Perl through the use of the List::Comprehensions CPAN module.[3]

[edit] In Python

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:

S = [2*x for x in range(100) 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)

[edit] In Scala

Further information: Scala

Using the for-comprehension:

val s = for (x <- Stream.from(0); if x*x > 3) yield 2*x

[edit] In Visual Prolog

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

[edit] In Windows PowerShell

Further information: Windows PowerShell
$s = ( 0..100 | ? {$_*$_ -gt 3} | % {2*$_} )

[edit] Monad comprehension

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.

[edit] Parallel list comprehension

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.

[edit] See also

[edit] Notes and references

  1. ^ [1]
  2. ^ [2]
  3. ^ List::Comprehensions CPAN module
  • List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.
  • Phil Trinder [4] 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 [5] 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:

Python:

PostScript:

Common Lisp

Axiom:

  • Axiom stream examples: [6]

[edit] External links

Languages