Comprehension with two variables - explanation needed

[Steven D'Aprano]

On Sun, 23 Nov 2014 08:45:39 -0800, Rustom Mody wrote:

> 2. "List comprehensions are syntactic sugar for for loops" Cannot
> technically quarrel with that as that is the position of the official
> docs.
> However to me it puts the cart before the horse. Its like saying that
> 
> def foo(x): return x+1
> 
> is just the same as
> 
>               0 LOAD_FAST                0 (x)
>               3 LOAD_CONST               1 (1)
>               6 BINARY_ADD
>               7 RETURN_VALUE
> 
> 
> (output of dis)


The two situations are not related. The output of dis is an 
implementation detail. Try running it under IronPython or Jython and see 
what you get. Even in CPython, it is still an implementation detail 
subject to change. Today dis() returns the above, tomorrow it may return:

              0 LOAD_GLOBAL              0 (x)
              3 INCREMENT
              5 RETURN_VALUE

(say), and the Python code remains the same even though the byte code is 
different.

Whereas the statement that "comprehensions are syntactic sugar for for-
loops" is a statement about the semantics of comprehensions. It's a 
language promise, part of the API of Python, and not subject to change 
without a period of deprecation.  It is a promise that

    [expression for name in sequence]

is closely equivalent to:

    for name in sequence:
        expression


(They are not *identical* because list comprehensions collect the result 
of expression into a list, set comprehensions collect them into a set, 
etc. But the actual looping part is the same.)


> 3. So how should one think of list comprehensions?
>    As a python/executable version of 'set-builder notation'
>    http://en.wikipedia.org/wiki/Set-builder_notation

For those who learned, and remember, set-builder notation, that is an 
excellent analogy.


> 4. Finally to the OP (assuming you wanted a prime-number generator)
> Heres a solution for your consideration.
> 
> First a one-line solution in haskell
> 
> sieve (p:xs)   =    p:sieve [x | x <- xs, x `mod` p /= 0]

Don't use that! That is a horribly inefficient way to generate primes.

Mathematically, it is a version of Euler's Sieve. It is sometimes wrongly 
described as "Sieve of Eratosthenes", but that is wrong. Due to it's 
horrible performance, Melissa O'Neill calls this the "Sleight on 
Eratosthenes":

http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Asymptotic behaviour of this is O(N**2/(log N)**2) which is worse than 
trial division and only *marginally* better than this stupidly naive 
version:

def primes0():
    i = 2
    yield i
    while True:
        i += 1
        composite = False
        for p in range(2, i):
            if i%p == 0:
                composite = True
        if not composite:  # It must be a prime.
            yield i



> Call with sieve [2..]
> 
> Now a pythonification of that
[...]





-- 
Steven