1

I've seen this question before, but it only deals with recursions that are linear in nature. I'm looking for something more general.

Suppose I have the following code

n = 10
num_bits = [0]
for i in range(n):
    nums_bits.append(num_bits[i>>1]+i%2)

This code will compute num_bits, a 11 element array of value with num_bits[i] representing the number of bits it takes to represent i.

Is it possible to write this as a list comprehension? Something like this doesn't work

num_bits = [0]*11
num_bits = [num_bits[i>>1]+i%2 for i in range(11)]

since the comprehension doesn't update the value of num_bits in the middle of evaluation. Is there a canonical way to do something like this, besides a for loop?

P.S. I'm aware there are other ways to solve this problem: I'm just using it as a vehicle to understand Python's features better.

Edit: To summarize, I'd like to know what the proper way of generating lists of values that are dependent on previous values is. For a simpler example, consider the Fibonacci Numbers

fibonacci = [0,1]
for i in range(10):
    fibonacci.append(fibonacci[-1]+fibonacci[-2])

Is there a way to generate these numbers in a comprehension? If not, what tools are there for this other than for loops (or are for/while loops my only option)?

Rushabh Mehta
  • 1,529
  • 1
  • 13
  • 29
  • 1
    I'm not sure using a feature not as intended is the best way to understand it. – Scott Hunter Mar 01 '22 at 14:53
  • @ScottHunter Fair, although I was curious as to whether there is a canonical way to evaluate recursions like this. Generators aren't great since they don't benefit from memoization. I didn't find anything in itertools that helps either. – Rushabh Mehta Mar 01 '22 at 14:55
  • Your first block of code is in error. – Scott Hunter Mar 01 '22 at 14:58
  • Can you simplify the example? Do you just want an example comprehension (or generator) that works with both a current and prior value? – JonSG Mar 01 '22 at 15:00
  • @JonSG Essentially. A comprehension that can reference prior values. – Rushabh Mehta Mar 01 '22 at 15:00
  • 1
    `fibonacci = [0,1]; deque((fibonacci.append(fibonacci[-1]+fibonacci[-2]) for _ in range(10)), maxlen=0)` fills the list consuming the generator and discarding the result (an empty queue, it's the fastest recommended way to consume an iterator) – Pynchia Mar 01 '22 at 15:15
  • Do you want it as an answer? It would take me today to 10K points! :D – Pynchia Mar 01 '22 at 15:17
  • [Each time](https://stackoverflow.com/questions/47722712/use-map-for-functions-that-does-not-return-a-value) someone asks how to use `map` [only for side effects](https://stackoverflow.com/questions/14447560/side-effects-in-python-map-python-do-block) or a [comprehension only for side effects](https://stackoverflow.com/questions/5753597/is-it-pythonic-to-use-list-comprehensions-for-just-side-effects), the *strong* consensus is that this is anti-Pythonic and unrecommended. As such, I'd advise against solutions to your problem that rely on side-effect-only generators or comprehensions. – kcsquared Mar 01 '22 at 15:40
  • @kcsquared Makes sense. I guess I was hoping for some itertools optimized solutions, but I guess there aren't any. – Rushabh Mehta Mar 01 '22 at 16:29

2 Answers2

1

No.

There is no nice way to do this with a list comprehension, and that is not what they’re for. The purpose of list comprehensions is to offer a more readable alternative to maps and filters, and this isn’t that, so it’s not possible to do this in a sensible way.

LeopardShark
  • 3,820
  • 2
  • 19
  • 33
1

Given it is not a piece of code I'd recommend, for the reasons discussed in the comments above and in the other answer, this comprehension should be faster than the for loop:

fibonacci = [0,1]
deque((fibonacci.append(fibonacci[-1]+fibonacci[-2]) for _ in range(10)), maxlen=0)

as it fills the list consuming the generator and discarding the result (an empty queue, it's the fastest recommended way to consume an iterator)

It produces:

>>> fibonacci
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
Pynchia
  • 10,996
  • 5
  • 34
  • 43
  • 1
    When I find myself resorting to indexes it signals it's the wrong way to do it in Python. I do think there should be a better way to do it – Pynchia Mar 01 '22 at 15:24