# List Comprehension

List comprehensions are a feature of many modern FunctionalProgrammingLanguages. Subject to certain rules, they provide a succinct notation for GeneratingElements? in a list.

A list comprehension is SyntacticSugar for a combination of applications of the functions concat, map and filter. http://foldoc.doc.ic.ac.uk/foldoc/foldoc.cgi?query=list+comprehension

Derives from "set comprehensions" in math. http://mathworld.wolfram.com/AxiomofSubsets.html

While reading the entry about Axiomatic Set Theory in The Encyclopedia of Philosophy (Collier-Macmillan, ISBN 0028949900 ) a few months ago, I suddenly grokked ListComprehension.

Expresses a new list as a (potentially complex) function of the old list. For example:

``` [x * 2 - 7 for x in range(27)]
```
or tuples expressing (some) integer products with an odd factor and an even factor:

``` [(x, y, x*y) for x in range(6) for y in range(4) if (x+y)%2]
```
or a table of sines and cosines:

``` [(sin(rad), cos(rad)) for rad in [math.radians(deg) for deg in range(360)]]
```
Pretty straightforward, and the compiler is free to make all sorts of optimizations that I don't have to think about.

Now if we could do reductions in as simple a syntax as we do mapping and filtering, you'd have another beast altogether. I'm not sure what you'd call it.

Would some people call it the AplLanguage? ;->

In APL the reduce operation is an operator followed by a slash, for instance Lisp's reduce-by-addition is "+/", e.g. "+/ 1 2 3 4 5" yields 15. Or "*/ 2 3 5" yields 30.

Methinks this is called folding (Haskell example):
``` foldl op acc [] = acc
foldl op acc (x:xs) = foldl op (op acc x) xs
-- e.g. foldl (+) 0 [1..5] == 15; foldl (*) 1 [2, 3, 5] == 30

```
Or did you mean a different kind of list reduction?

The list comprehension syntax for the ErlangLanguage is described here: http://www.erlang.org/doc/r8b/doc/extensions/list_comprehensions.html

``` pyth1(N) ->
[{A,B,C} ||
A <- lists:seq(1,N),
B <- lists:seq(1,N-A+1),
C <- lists:seq(1,N-A-B+2),
A+B+C =< N,
A*A+B*B == C*C ].
```

The PythonLanguage version of this is:

``` def pyth(on):
return [(a,b,c)
for a in range(1,on)
for b in range(1,on-a+1)
for c in range(1,on-b-a+2)
if a+b+c <= on and a**2 + b**2 == c**2]
```
As of version 2.4, Python now has GeneratorComprehension?'s, which return a generator instead of a list. A generator comprehension is created by using parenthesis instead of square brackets. Still not quite as nice syntactically as full blown LazyEvaluation (which requires no list/generator distinction) but still fairly handy.

The HaskellLanguage version of this is:

``` pyth n = [ ( a, b, c ) | a <- [1..n],
b <- [1..n-a+1],
c <- [1..n-a-b+2],
a + b + c <= n,
a^2 + b^2 == c^2 ]

```
This, not terribly surprising, turns out to be equivalent to this monadic code:

``` import Control.Monad

pyth n = do a <- [1..n]
b <- [1..n-a+1]
c <- [1..n-a-b+2]
guard (a + b + c <= n)
guard (a^2 + b^2 == c^2)
return (a, b, c)
```

In CsharpLanguage, it looks like this:

```  IEnumerable<Tuple<int,int,int>> pyth(int n) {
return from a in Enumerable.Range(1, n)
from b in Enumerable.Range(1, n - a + 1)
from c in Enumerable.Range(1, n - a - b + 2)
where a + b + c <= n
where a * a + b * b == c * c
select Tuple.Create(a, b, c);
}

```

The XqueryLanguage version looks like this:

```  declare function pyth(\$n) {
for \$a in 1 to \$n
for \$b in 1 to \$n - \$a + 1
for \$c in 1 to \$n - \$a - \$b + 2
where \$a + \$b + \$c le \$n
and \$a * \$a + \$b * \$b eq \$c * \$c
return (\$a,\$b,\$c)
};

```
Because lists get flattened, an element around the projection is needed to be able to deconstruct later on:

```  declare function pyth(\$n) {
for \$a in 1 to \$n
for \$b in 1 to \$n - \$a + 1
for \$c in 1 to \$n - \$a - \$b + 2
where \$a + \$b + \$c le \$n
and \$a * \$a + \$b * \$b eq \$c * \$c
return <rec a=\$a, b=\$b, c=\$c/>
};
```

SchemeLanguage has this via http://srfi.schemers.org/srfi-42/srfi-42.html

In ScalaLanguage, it looks like this:

```  def pyth(N: Int): List[(Int, Int, Int)] =
for(a <- (1 to N).toList;
b <- (1 to (N - a + 1));
c <- (1 to (N - a - b + 1));
if(a + b + c < N);
if(a * a + b * b == c * c))
yield (a, b, c)
```

For this in CeePlusPlus using the BoostLambdaLibrary see VariadicFunctoidsInCpp.
See HigherOrderFunction MapFunction FilterFunction
CategoryLanguageFeature CategoryFunctionalProgramming

View edit of March 30, 2012 or FindPage with title or text search