List Comprehension

view on wiki.c2.com
last modified: March 30, 2012

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

Loading...