Welcome, guest | Sign In | My Account | Store | Cart
7

Sometimes you want to have a list comprehension refer to itself, but you can't because it isn't bound to a name until after it is fully constructed. However, the interpreter creates a secret name that only exists while the list is being built. That name is (usually) "_[1]", and it refers to the bound method "append" of the list. This is our back door to get at the list object itself.

Python, 70 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# Remove duplicates from a list:
>>> L = [1,2,2,3,3,3]
>>> [x for x in L if x not in locals()['_[1]'].__self__]
[1,2,3]


# That's a bit ugly, so let's encapsulate it in a function.
# Be carefull with nested list comprehensions. The inner one is
# called "_[2]" (or "_[3]", and so on if you nest them deeply).
def thislist():
    """Return a reference to the list object being constructed by the
    list comprehension from which this function is called. Raises an
    exception if called from anywhere else.
    """
    import sys
    d = sys._getframe(1).f_locals
    nestlevel = 1
    while '_[%d]' % nestlevel in d:
        nestlevel += 1
    return d['_[%d]' % (nestlevel - 1)].__self__

# More readable now:
>>> L = [1,2,2,3,3,3]
>>> [x for x in L if x not in thislist()]
[1,2,3]


# At any given point in the construction, the list is a fully functional
# list object. You can even call mutating methods on it.
# For example:

# Remove duplicates from a list, retaining only the *last* item from 
# each equivalency class:
>>> L = ['ab','a'+'b']
>>> map(id, L)
[16333632, 16332416]
>>> L2 = [x for x in L if x not in thislist() \
                        or not thislist().remove(x)]
>>> L2
['ab']
>>> map(id, L2) # make sure it worked...
[16332416]


# Another example: Finding prime numbers (Python 2.3+)
import itertools, sys, math

def primes_less_than(N):
    return [p for p in itertools.chain([2],xrange(3,N,2))
            if 0 not in itertools.imap(lambda x:p%x,
                                       itertools.takewhile(
                                           lambda v:v <= math.sqrt(p),
                                           thislist() ))]

def first_N_primes(N):
    return [p for p in itertools.takewhile(lambda _,L=thislist():len(L) < N,
                                           itertools.chain([2],xrange(3,sys.maxint,2)))
            if 0 not in itertools.imap(lambda x:p%x,
                                       itertools.takewhile(
                                           lambda v:v <= math.sqrt(p),
                                           thislist()))]

# For lazy typists:
plt = primes_less_than
fnp = first_N_primes

>>> plt(20)
[2, 3, 5, 7, 11, 13, 17, 19]
>>> fnp(10)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

While list comprehensions look a little like magic, the bytecode generated for them is quite mundane - create an empty list, give its append method a temporary name in the locals dictionary, append items one at a time, and then delete the name. This all happens, conceptually, between the [ and the ] that denote the list comprehension.

The temporary name assigned is "_[1]" (or "_[2]" for a nested list comprehension). Since this is not a syntactically valid Python identifier, we cannot refer to it directly - we need to access it as locals()['_[1]']. Then we just use the bound method's __self__ attribute to get at the list object itself.

This lets us do all sorts of neat party tricks, like performing "if" tests that involve looking at the items that have already been added to the list - or even modifying or deleting them. This is just what the doctor ordered for finding primes in a one-liner - for each odd number we need to test whether it is divisible by any prime number less than or equal to the square root of the number being tested. Since we already have all the smaller primes stored, and, with our new parlour trick, have access to them, this test is a breeze and requires no auxiliary storage.

Note that while the prime number functions above are pretty fast for one-liners (plt(100000) takes 7 seconds on my machine, timed with the ultra-accurate "counting-in-my-head" method), they are nowhere near as fast as the Sieve of Eratosthenes method (recipe 117119). However, they are much, much sexier. ;)

And now for the big "but"... It should come as no surprise to anyone that this is a totally undocumented, seat-of-your-pants exploitation of an implementation detail of the Python interpreter. There is absolutely no guarantee that this will continue to work in any future Python release. In fact I only know for sure that it works in Python 2.2.2 and 2.3b1. Beyond that you're on your own.

Finally, as an aside, let me just say: itertools rules!

>>> 1 in itertools.imap(lambda x:1/x, [1,0]) # Look Ma, no ZeroDivisionError!
True
(Lazy evaluation makes the primality tests *way* more efficient.)

4 comments

Jay Parlar 9 years, 4 months ago  # | flag

Try this instead (in Python2.4)

[x for x in L if x not in locals()["_[1]"]]
Christos Georgiou 8 years, 4 months ago  # | flag

This secret? There is no official or underground plan to stop this secret from functioning in 2.x (for any x > 3).

BTW, another way to find similar secrets (ie depending on the C implementation and not guaranteed to work on Jython, IronPython, PyPy etc):

import dis

dis.dis(compile("your expression here","","eval")

eg.

dis.dis(compile("[x*2 for x in range(4)]","","eval")

secretly provided to you by the dis module :)

If you provide a block of statements instead of an expression, secretly substitute "exec" for "eval" in the examples above.

Andreas Schöller 8 years, 3 months ago  # | flag

still does in 2.4. Hi, this one

>>> L = [1,2,2,3,3,3]
>>> [x for x in L if x not in locals()['_[1]']]
[1,2,3]

works for me. Same with the thislist()-function - i just left the .__self__

greets, andreas

Curtis Sandoval 4 years, 3 months ago  # | flag

I realise that it is not the point, but in this example, doing a unique works faster if you do something like {}.fromkeys(L).keys().

Add a comment

Sign in to comment

Created by Chris Perkins on Sun, 8 Jun 2003 (PSF)
Python recipes (4237)
Chris Perkins's recipes (5)

Required Modules

  • (none specified)

Other Information and Tasks