12

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)]
Jason S
  • 184,598
  • 164
  • 608
  • 970

3 Answers3

23

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)

Stefan Pochmann
  • 27,593
  • 8
  • 44
  • 107
  • 1
    Holy hell that's sneaky. – juanpa.arrivillaga Dec 13 '17 at 22:45
  • 5
    While this is probably the cleanest, best-encapsulated form of state variables in a list comprehension I've seen (no leakage of the state variable into the surrounding scope, at least on Python 3), there's still a reason I didn't post anything like this: every instance of this kind of code on Stack Overflow, getting upvotes, increases the risk that people will think this kind of thing is a good idea and actually use it in their code. – user2357112 Dec 13 '17 at 23:18
  • @user2357112 Better now? :-) – Stefan Pochmann Dec 13 '17 at 23:19
  • 1
    @juanpa.arrivillaga Just figured out another neat way, it just doesn't have that required format with `xrange` at the end: `[q.append(f(x)) or x for q in [[x]] for x in q if len(q) <= n]`. Which one is sneakier? :-) – Stefan Pochmann Dec 29 '17 at 22:23
  • A little late but could anyone provide some insight as to why using code like this would be bad practice? – evantkchong Apr 17 '19 at 08:26
  • 1
    @evantkchong: Comprehensions and generator expressions are functional constructs (as in functional programming). They're intended to consume an input iterable, an item at a time, applying a filter and/or transform per item, with no side-effects or behaviors dependent on any mutable state aside from the item itself. Reasonable people expect them to behave this way, and every violation of that rule makes your code harder to read (a problem even if these conventions didn't exist, because forcing mutable state into the function gets *ugly* as you can see) and harder to maintain. – ShadowRanger Nov 15 '22 at 21:28
  • 1
    Functional programming tends to avoid mutable state entirely; obviously Python isn't a functional programming language, but the conventions around functional constructs exist for a reason, to make code behave in a predictable manner without every reader having to look for "gotchas". Even for expert Python programmers (I consider myself one), it takes *far* longer to parse this monstrosity than it would to read any reasonable listcomp. – ShadowRanger Nov 15 '22 at 21:30
6

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.

user2357112
  • 260,549
  • 28
  • 431
  • 505
4

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]
tobias_k
  • 81,265
  • 12
  • 120
  • 179
  • While I consider using `itertools.accumulate` for this to be ugly, recurrence relations are explicitly listed as a use case in the [`accumulate` docs](https://docs.python.org/3/library/itertools.html#itertools.accumulate), with example code. – user2357112 Dec 13 '17 at 22:51
  • @StefanPochmann Good point, fixed, but that makes it even uglier. – tobias_k Dec 14 '17 at 08:43
  • @tobias_k Well then make it *prettier* instead :-). If you followed the documentation, you'd use `repeat(x, n)`. And since you're willing to create a list, you could simply use `[x] * n`. – Stefan Pochmann Dec 14 '17 at 10:01
  • For `reduce` you could also use `lst.__iadd__([f(lst[-1])])`, though I prefer the `append`+`or lst` (despite it being three characters longer! :-) – Stefan Pochmann Dec 14 '17 at 22:43
  • Ha, how about: `reduce(lambda lst, _: lst.append(f(lst[-1])) or lst, [[x]] * n)`. I actually laughed about this one... using the common `[[x]] * n` 2D-list gotcha... but it's ok here because the repeated references are ignored... I think that's just beautiful. – Stefan Pochmann Dec 14 '17 at 22:58