List comprehension 275744 226014375 2008-07-16T13:16:59Z Paddy3118 682261 [[WP:UNDO|Undid]] revision 225999164 Read the Talk page and the heading. It is not about map/filter/grep/... '''List comprehension''' is a [[Syntax of programming languages|syntactic]] construct available in some [[programming language]]s 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 (higher-order function)|map]] and [[Filter (higher-order function)|filter]] functions. Consider the following example in set builder notation. :<math>S=\{\,2\cdot x\mid x \in \mathbb{N},\ x^2>3\,\}</math> This can be read, "''S'' is the set of all ''2*x'' where ''x'' is an item in the set of natural numbers, for which ''x'' squared is greater than 3." In the example: * <math>x</math> is the variable representing members of an input set. * The input set is <math>\mathbb{N}</math>. * <math>x^2>3</math> is a [[Predicate (logic)|predicate]] function acting as a filter on members of the input set. * And <math>2\cdot x</math> is an output function producing members of the new set from members of the input set that satisfy the predicate function. The brackets contain the expression and the vertical bar and comma are separators. A '''list comprehension''' has the same syntactic components to represent generation of a list in order from an input [[List (computing)|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 (programming language)|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 <code>[0..]</code> represents <math>\mathbb{N}</math>, <code>x^2>3</code> represents the predicate, and <code>2*x</code> represents the output expression. '''List comprehensions''' give results in a defined order, (unlike the members of sets); and list comprehensions may [[Generator (computer science)|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]] (later 1960's) had a set formation construct, and the [[computer algebra system]] [[AXIOM]] (1973) has a similar construct that processes [[stream (computing)|stream]]s, but the first use of the term "comprehension" for such constructs was in Rod Burstall and John Darlington's description of their programming language [[NPL programming language|NPL]] from 1977. Comprehensions were proposed as a query notation for databases<ref>[http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=135271]</ref> and were implemented in the ''Kleisli'' database query language.<ref>[http://portal.acm.org/citation.cfm?id=351241&dl=ACM&coll=portal]</ref> == Examples in different programming languages == Note: while the original example denotes an infinite list, few languages can express that, so in those cases we show how to take a subset of <math>{0, 1, ..., 100}</math> rather than a subset of <math>\mathbb{N}</math>. === Boo === {{further|[[Boo (programming language)|Boo Programming Language for .NET/Mono]]}} List with all the doubles from 0 to 10 (exclusive) <source lang="python"> doubles = [i*2 for i in range(10)] </source> List with the names of the customers based on Rio de Janeiro <source lang="python"> rjCustomers = [customer.Name for customer in customers if customer.State == "RJ"] </source> === C# === {{further|[[C Sharp (programming language)#C.23_3.0_new_language_features|C# 3.0 Language Integrated Query]]}} <source lang="csharp"> var ns = from x in Enumerable.Range(0,100) where x*x > 3 select x*2; </source> The previous code is syntactic sugar for the following code written using lambda expressions: <source lang="csharp"> var ns = Enumerable.Range(0, 100) .Where(x => x*x > 3) .Select(x => x*2); </source> === Common Lisp === {{further|[[Common Lisp]]}} List comprehensions can be expressed with the <code>loop</code> macro's <code>collect</code> keyword. Conditionals are expressed with <code>if</code>, as follows: <source lang="lisp"> (loop for x from 0 to 100 if (> (* x x) 3) collect (* 2 x)) </source> === Erlang === {{further|[[Erlang (programming language)|Erlang]]}} L = lists:seq(0,100). S = [2*X || X <- L, X*X > 3]. === F# === {{further|[[F Sharp (programming language)|F#]]}} <source lang="ocaml"> { for x in 0 .. 100 when x*x > 3 -> 2*x } </source> Or, more correctly for floating point values <source lang="ocaml"> { for x in 0.0 .. 100.0 when x**2.0 > 3.0 -> 2.0*x } </source> === Haskell === {{further|[[Haskell (programming language)|Haskell]]}} 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] === JavaScript === {{further|[[JavaScript]]}} Borrowing from Python, JavaScript 1.7 and later have array comprehensions[http://developer.mozilla.org/en/docs/New_in_JavaScript_1.7]. Although this feature has been proposed for inclusion in the fourth edition [[ECMAScript]] standard, Mozilla is the only implementation that currently supports it. <source lang="javascript"> /* 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)] </source> JavaScript 1.8 adds Python-like generator expressions. === Nemerle === {{further|[[Nemerle]]}} <source lang="ocaml"> $[x*2 | x in [0 .. 100], x*x > 3] </source> === Perl === {{further|[[Perl]]}} List comprehensions are supported in Perl through the use of the ''List::Comprehensions'' [[CPAN]] module.<ref>[http://search.cpan.org/~ophiuci/List-Comprehensions-0.13/lib/List/Comprehensions.pm List::Comprehensions CPAN module]</ref> === Python === {{further|[[Python syntax and semantics#Generators|Python syntax and semantics: Generators]]}} The [[Python (programming language)|Python programming language]] has a corresponding syntax for expressing list comprehensions. The near-equivalent example in Python is as follows: <source lang="python"> S = [2*x for x in range(100) if x**2 > 3] </source> A '''generator expression''' may be used in Python 2.4 to achieve functional equivalence with ''S'' using a [[generator (computer science)|generator]] to iterate an infinite list: <source lang="python"> from itertools import count S = (2*x for x in count() if x**2 > 3) </source> === Scala === {{further|[[Scala (programming language)|Scala]]}} Using the for-comprehension: val s = for (x <- Stream.from(0); if x*x > 3) yield 2*x === Visual Prolog === {{further|[[Visual Prolog]]}} <font color="#008000">S</font> = <font color="#B9005C">[</font> <font color="#0000FF">2</font>*<font color="#008000">X</font> <font color="#B9005C">||</font> <font color="#008000">X</font> = list::getMember_nd<font color="#993300">(</font><font color="#008000">L</font><font color="#993300">)</font>, <font color="#008000">X</font>*<font color="#008000">X</font> &gt; <font color="#0000FF">3</font> <font color="#B9005C">]</font> === Windows PowerShell === {{further|[[Windows PowerShell]]}} <source lang="csharp"> $s = ( 0..100 | ? {$_*$_ -gt 3} | % {2*$_} ) </source> ==Monad comprehension== A [[monads in functional programming#do-notation|monad comprehension]] is a generalization of the list comprehension to other [[monads in functional programming]]. ==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. 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. ==See also== *[[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)]] ==Notes and references== {{reflist}} *[http://ftp.sunet.se/foldoc/foldoc.cgi?list+comprehension List Comprehension] in The Free On-line Dictionary of Computing, Editor Denis Howe. *Phil Trinder [http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=135271] 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. [http://citeseer.ist.psu.edu/wadler92comprehending.html Comprehending Monads]. Proceedings of the 1990 ACM Conference on LISP and Functional Programming, Nice. 1990. *Limsoon Wong [http://portal.acm.org/citation.cfm?id=351241&dl=ACM&coll=portal] 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 [http://haskell.org/onlinereport/exps.html#list-comprehensions 3.11 List Comprehensions]. *The Glorious Glasgow Haskell Compilation System User's Guide, chapter [http://www.haskell.org/ghc/docs/latest/html/users_guide/syntax-extns.html#parallel-list-comprehensions 7.3.4 Parallel List Comprehensions]. *The Hugs 98 User's Guide, chapter [http://cvs.haskell.org/Hugs/pages/users_guide/hugs-ghc.html#ZIP-COMPREHENSION 5.1.2 Parallel list comprehensions (a.k.a. zip-comprehensions)]. '''Python:''' * Python Reference Manual, chapter [http://www.python.org/doc/2.4.1/ref/lists.html 5.2.4 List displays]. * Python Enhancement Proposal [http://www.python.org/peps/pep-0202.html PEP 202: List Comprehensions]. * Python Reference Manual, chapter [http://www.python.org/doc/2.4.1/ref/genexpr.html 5.2.5 Generator expressions]. * Python Enhancement Proposal [http://python.org/peps/pep-0289.html PEP 289: Generator Expressions]. '''PostScript:''' * {{cite book | last = Systems | first = Adobe | authorlink = Adobe Systems | coauthors = | title = PostScript Language Reference Manual, Third Edition | publisher = [[Addison-Wesley]] | date = [[1999]]-02 | location = | pages = pp. 524–524 | url = http://www.adobe.com/products/postscript/pdfs/PLRM.pdf | doi = | id = 0-201-37922-8}} '''Common Lisp''' * [http://rali.iro.umontreal.ca/Publications/urls/LapalmeLispComp.pdf Implementation of a Lisp comprehension macro] by [http://www.iro.umontreal.ca/~lapalme/ Guy Lapalme] '''Axiom:''' *Axiom stream examples: [http://page.axiom-developer.org/zope/mathaction/Streams] ==External links== * SQL-like set operations with list comprehension one-liners in the [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/159974 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] [[Category:Programming constructs]] [[Category:Articles with example code]] [[Category:Articles with example C Sharp code]] [[Category:Articles with example Erlang code]] [[Category:Articles with example Haskell code]] [[Category:Articles with example Lisp code]] [[Category:Articles with example Python code]] [[Category:Articles with example Visual Prolog code]] [[fr:Compréhension de liste]] [[pt:List comprehension]]