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