Functional python -- why does only one of these generators require list() to work?

Question

In computing the Chinese Remainder theorem from a vector of tuples (residue, modulus) the following code fails :

c = ((1,5),(3,7),(11,13),(19,23))

def crt(c):
        residues, moduli = zip(*c)
        N = product(moduli)
        complements = (N/ni for ni in moduli)
        scaled_residues = (product(pair) for pair in zip(residues,complements))
        inverses = (modular_inverse(*pair) for pair in zip(complements,moduli))
        si = (product(u) for u in zip(scaled_residues,inverses))
        result = sum(si) % N
        return result

Giving the result as 0 ( I guess the generated iterables are empty ). Yet the following code works perfectly :

def crt(c):
        residues, moduli = zip(*c)
        N = product(moduli)
        complements = list((N/ni for ni in moduli)) # <-- listed
        scaled_residues = (product(pair) for pair in zip(residues,complements))
        inverses = (modular_inverse(*pair) for pair in zip(complements,moduli))
        si = (product(u) for u in zip(scaled_residues,inverses))
        result = sum(si) % N
        return result

Which yields (a) correct result of 8851.

Why should I have to list( one of the first generators? Adding list to any subsequent generator does not change the fail (0) result. Only listing this first generator produces the correct result. What is going on here ?

Could this be the same problem? http://stackoverflow.com/questions/11210300/why-does-zip-drop-the-values-of-my-generator — Alex L, Feb 01 '13 at 06:40
perhaps you could print `zip(residues,complements)` and then `zip(complements,moduli)` before iterating through? — Alex L, Feb 01 '13 at 06:42
@AlexL yes, the first zip using complements gives the correct list, but the second one is empty...since complements is exhausted by then. It makes sense that complements should be a list -- or just put a generator inside each call to zip that requires those complements. — Cris Stringfellow, Feb 01 '13 at 06:52
I think it's better to write `[N/ni for ni in moduli]` instead `list((N/ni for ni in moduli))` — Denis Nikanorov, Feb 01 '13 at 07:39

Janne Karila · Accepted Answer · 2013-02-01T06:57:38.313

6

You iterate twice over complements. You can only iterate once over a generator expression.

If you are on Python 2.x, zip(residues,complements) will consume complements and there is nothing left for zip(complements,moduli). On Python 3.x zip is a generator itself and the problem appears later in the code, when sum() actually runs the generators. It would pull two items from complements for each iteration.

edited Feb 01 '13 at 06:57

answered Feb 01 '13 at 06:43

Janne Karila

24,266
6
53
94

Boom! That's it! I forgot that about generators. Is this **single use** quality of generators the same in other functional languages that have them...possibly Scala or Haskell? – Cris Stringfellow Feb 01 '13 at 06:49
by later in the code, what do you mean -- zip is also a generator? – Cris Stringfellow Feb 01 '13 at 06:53
I am guessing that this is why functional programming is called functional. If I broke up the above function into smaller functions instead of assigning generators to variables, the functions could call the generators when needed and there would be no exhaustion. – Cris Stringfellow Feb 01 '13 at 06:55

score 0 · Answer 2 · answered Feb 01 '13 at 07:03

For reference based on the suggestions in the answer I reimplemented the code in the question as follows:

def complements(moduli,N):
        return (N/ni for ni in moduli)

def scaled_residues(residues,complements):
        return (product(pair) for pair in zip(residues,complements))

def inverses(complements,moduli):
        return (modular_inverse(*pair) for pair in zip(complements,moduli))

def crt_residue_terms(scaled_residues,inverses):
        return (product(u) for u in zip(scaled_residues,inverses))

 def crt(c):   
    residues, moduli = zip(*c)
    N = product(moduli)
    return sum(
            crt_residue_terms(
                    scaled_residues(residues,complements(moduli,N)),
                    inverses(complements(moduli,N),moduli)
            )) % N

It now produces the correct result of 8851 without using any lists. Cool.

Note that contrary to popular belief, generator expressions are not always more efficient than lists. If you are iterating over small sets, often the memory trade-off is not worth. — Paulo Scardine, Feb 01 '13 at 07:09

Functional python -- why does only one of these generators require list() to work?

2 Answers2