List comprehension

From Free net encyclopedia

List comprehension is a programming language construct for list processing, analogous to the set-builder notation (set comprehension), that is, the mathematical notation such as the following:

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

For an example, in Haskell's list comprehension syntax, the example set-builder construct above would be written as: 

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

Here, the list [0..] represents N, and x^2>3 represents the conditional. It is clear that the two notations are nearly identical. The example could be read: "S is the list of all x where x is an item in the list of natural numbers, and x squared is greater than 3."


Contents

[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 already SETL had a similar construct. 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

Template:Further

In Haskell, list comprehensions can also be written as expressions involving the higher-order functions map and filter. For example, S above can also be written as 

S = filter (\x -> x^2 > 3) [0..]

However, Haskell's list comprehension syntax permits any number of comma-separated qualifiers after the pipe |. A qualifier can be a generator drawing items from a list, a guard doing filtering, or a local declaration using let. Certain lists are too complex to express by other means.

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

L = range(100) # lists in Python must be finite, this is from 0 to 99
S = [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 = (x for x in count() if x**2 > 3)
[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 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. 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 ressembles 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 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]

References

  • List Comprehension in The Free On-line Dictionary of Computing, Editor Denis Howe.
  • Philip Wadler [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:

Python:

Axiom:

  • Axiom stream examples: [5]
[edit]

External links

  • SQL-like set operations with list comprehension one-liners in the Python Cookbook
Retrieved from "http://www.netipedia.com/index.php/List_comprehension"