Python conversion madness

Question

I have a code understanding problem related to python:

def convex_hull(pts):
    """Returns the points on the convex hull of pts in CCW order."""
    for m in (2 ** (2 ** t) for t in xrange(len(pts))):
        hulls = [_graham_scan(pts[i:i + m]) for i in xrange(0, len(pts), m)]
//more code

I can't figure out how are those two 'for' supposed to work.

Sadly the command reference doesn't show such an usage example, and I can't really tell if it -really- means that one for is the left side assignment of the other?

Additionally, what could the bottom assignment possibly mean? Does the 'for' statement return a value?!?!

Thanks and sorry for the beginner question.

Answer 1

To understand this code, you first need to understand list comprehensions and generator expressions. Here is a an example of a simple list comprehension:

>>> [str(i) for i in range(5)]
['0', '1', '2', '3', '4']

As you can see, this one line does the equivalent of the following regular for loop:

lst = []
for i in range(5):
    lst.append(str(i))

Basically, it is a shorthand for creating lists. Generator expressions are similar except that instead of returning a list they return a generator which will yield the same values as a list comprehension, without actually creating the full list. This is more efficient when you are just going to loop through the values.

Now that the background is out of the way, here is how you could expand that code using regular for loops:

def convex_hull(pts):
    """Returns the points on the convex hull of pts in CCW order."""
    for t in xrange(len(pts)):
        m = 2 ** (2 ** t)
        hulls = []
        for i in xrange(0, len(pts), m):
            hulls.append(_graham_scan(pts[i:i + m]))
    # more code

As for your comment, pts[i:i + m] is taking a slice of the list from index i up to index i + m, you can basically read slices like this:

[first index to include : first index to exclude : step]

This answer has a pretty good explanation with some examples.