Recursive list comprehension in Python?

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?

Solution 1:

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;-).

Solution 2:

Actually you can! This example with an explanation hopefully will illustrate how.

define recursive example to get a number only when it is 5 or more and if it isn't, increment it and call the 'check' function again. Repeat this process until it reaches 5 at which point return 5.

print [ (lambda f,v: v >= 5 and v or f(f,v+1))(lambda g,i: i >= 5 and i or g(g,i+1),i) for i in [1,2,3,4,5,6] ]

result:

[5, 5, 5, 5, 5, 6]
>>> 

essentially the two anonymous functions interact in this way:

let f(g,x) = {  
                 expression, terminal condition
                 g(g,x), non-terminal condition
             }

let g(f,x) = {  
                 expression, terminal condition
                 f(f,x), non-terminal condition
             }

make g,f the 'same' function except that in one or both add a clause where the parameter is modified so as to cause the terminal condition to be reached and then go f(g,x) in this way g becomes a copy of f making it like:

f(g,x) = {  
                 expression, terminal condition
                 {
                    expression, terminal condition,
                    g(g,x), non-terminal codition
                 }, non-terminal condition
             }

You need to do this because you can't access the the anonymous function itself upon being executed.

i.e

(lambda f,v: somehow call the function again inside itself )(_,_)

so in this example let A = the first function and B the second. We call A passing B as f and i as v. Now as B is essentially a copy of A and it's a parameter that has been passed you can now call B which is like calling A.

This generates the factorials in a list

print [ (lambda f,v: v == 0 and 1 or v*f(f,v-1))(lambda g,i: i == 0 and 1 or i*g(g,i-1),i) for i in [1,2,3,5,6,7] ]

[1, 2, 6, 120, 720, 5040]
>>> 

Solution 3:

Starting Python 3.8, and the introduction of assignment expressions (PEP 572) (:= operator), which gives the possibility to name the result of an expression, we could reference items already seen by updating a variable within the list comprehension:

# items = [1, 1, 2, 2, 3, 3, 4, 4]
acc = []; [acc := acc + [x] for x in items if x not in acc]
# acc = [1, 2, 3, 4]

This:

• Initializes a list acc which symbolizes the running list of elements already seen
• For each item, this checks if it's already part of the acc list; and if not:
  • appends the item to acc (acc := acc + [x]) via an assignment expression
  • and at the same time uses the new value of acc as the mapped value for this item