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

EditText of this page (last edited March 30, 2012) or FindPage with title or text search