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.

Derives from "set comprehensions" in math.

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:

 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

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