List comprehensions in Python with mutable state b

问题:

I have something which is an awful lot like a list comprehension in Python, except that it shares mutable state between iterations. Is there any way to do it with a list comprehension?

def f(x):
    """ 5-bit LFSR """
    return (x >> 1) ^ (0x12*(x&1))

def batch(f, x, n):
    result = [x]
    for _ in xrange(1,n):
        x = f(x)
        result.append(x)
    return result

batch(f, 1, 5)

which returns [1, 18, 9, 22, 11]. Here the important thing is the batch function, not f(x) which is here just a simple example to illustrate the issue.

Alternatively I could implement using a generator:

def batch(f, x, n):
    yield x
    for _ in xrange(1,n):
        x = f(x)
        yield x

list(batch(f, 1, 5))

But it smells a little awkward. What I'm looking for is something like this...

batch = [??? for _ in xrange(n)]

回答1:

No. Deliberately no. Eventually they put in itertools.accumulate, which is the closest thing to an Officially Recommended way to implement recurrence relations in a functional manner, but it doesn't exist on 2.7. You could copy the "roughly equivalent to" Python implementation from the docs if you want.

回答2:

Is there any way to do it with a list comprehension?

What I'm looking for is something like this...

batch = [??? for _ in xrange(n)]

Sure, no problem:

>>> x = 1
>>> n = 5
>>> [prev.append(f(prev[0])) or prev.pop(0) for prev in [[x]] for _ in xrange(n)]
[1, 18, 9, 22, 11]

Note: This is a bad idea. ^{_{(I pretty much only did this because user2357112 said there is no way)}}

回答3:

You could do this in a single line, using e.g. reduce (or functools.reduce in Python 3):

>>> f = lambda x: (x >> 1) ^ (0x12*(x&1))
>>> x, n = 1, 5
>>> functools.reduce(lambda lst, _: lst + [f(lst[-1])], range(1, n), [x])
[1, 18, 9, 22, 11]

But this is not only ugly, but also inefficient, as it will create a new list in each iteration. Or in a similar fashion to Stefan's approach, without creating intermediate lists:

>>> functools.reduce(lambda lst, _: lst.append(f(lst[-1])) or lst, range(1, n), [x])
[1, 18, 9, 22, 11]

Or, as already hinted in the other answer, you could use itertools.accumulate, which is a lot better, but still a bit of a mis-use, as it actually expects a binary function, whereas here we use neither the second parameter, nor the actual iterable passed into the function, except for the very first value.

>>> list(itertools.accumulate([x] * n, lambda y, _: f(y)))
[1, 18, 9, 22, 11]