Bill de hÓra: I think I figured out the list comprehensions thing…

Bill de hÓra: I think I figured out the list comprehensions thing…

I’ve been trying to understand this stuff myself, and Bill de hÓra’s post has prodded me to write this down so I won’t forget it again.

List comprehensions are really just syntatic sugar. And too much syntatic sugar can cause truth decay.

List comprehensions are forms in functional and related languages that allow you to generate an entire list with a description of the list. So, for example, I can get a list of the first 10 squares by:

[ 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.


Posted

in

by

Tags:

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *