Recursive list comprehension in Python?

Yuval Adam picture Yuval Adam · Apr 14, 2010 · Viewed 17.6k times · Source

Is it possible to define a recursive list comprehension in Python?

Possibly a simplistic example, but something along the lines of:

nums = [1, 1, 2, 2, 3, 3, 4, 4]
willThisWork = [x for x in nums if x not in self] # self being the current comprehension

Is anything like this possible?

Answer

Alex Martelli picture Alex Martelli · Apr 14, 2010

No, there's no (documented, solid, stable, ...;-) way to refer to "the current comprehension". You could just use a loop:

res = []
for x in nums:
  if x not in res:
    res.append(x)

of course this is very costly (O(N squared)), so you can optimize it with an auxiliary set (I'm assuming that keeping the order of items in res congruent to that of the items in nums, otherwise set(nums) would do you;-)...:

res = []
aux = set()
for x in nums:
  if x not in aux:
    res.append(x)
    aux.add(x)

this is enormously faster for very long lists (O(N) instead of N squared).

Edit: in Python 2.5 or 2.6, vars()['_[1]'] might actually work in the role you want for self (for a non-nested listcomp)... which is why I qualified my statement by clarifying there's no documented, solid, stable way to access "the list being built up" -- that peculiar, undocumented "name" '_[1]' (deliberately chosen not to be a valid identifier;-) is the apex of "implementation artifacts" and any code relying on it deserves to be put out of its misery;-).