Month: February 2006

[ x * x | x [1,4,9,16,25,36,49,64,81,100]

That gives me a list of the squares of x, where x is an element of the list of integers from 1 to 10. I can also add some more qualifiers, like

[ x * x | x 3]

[16,25,36,49,64,81,100]

[i * j | i 5]

[5,8,10,9,12,15,8,12,16,20,5,10,15,20,25]

This is all pretty neat, but what does it really mean?

You ‘normally’ think of drawing a variable from each of the generating lists, with the right most one varying most quickly, and skipping if the variables fail to meet the condition. This provides a natural analogue to the looping constructs in most programming languages.

for (int i = 1; i 
 for (int j = 1; j 
      if ((i + j) > 5) {
            list.push(i*j);
        }
    }
}

That close, natural, analogue can be a code smell in functional programming. It may be an indication that you’re thinking of the problem in terms of loops, updating variables, etc.

The intent of list comprehension is to simulate loops and conditions, but it can be defined in terms of map and list concat. (As far as I can tell, this is due to P. Wadler, in Simon Peyton-Jones’s The Implementation of Functional Programming Languages )

[t | x   map (\x -> t) u
[t | p, q]    ==>  concat [ [t | q] | p ]
[t | b ]      ==>  if (b) then [t] else []

Note that the two qualifications p and q are reversed when translated.

concat will take the results of the simplified comprehension and concatenate all of the resulting lists together, eliminating empty lists.

Lets take the first, simple, example:

[ x * x | x that translates to:

map (\x -> x * x) [1..10]

The next example

[ x * x | x 3]

takes a few more steps

concat [ [x * x | x> 3] | x
concat ( map (\x -> [x * x | x>3]) [1..10] )

concat (map (\x -> (if (x>3) then [x*x] else [])) [1..10])

In this case, the list comprehension is more concise. On the other hand, the expanded version is a bit more suggestive. Particularly if I’m willing for it not to be a lambda expression.