newbie Q: sequence membership - Python

En Sat, 17 Nov 2007 04:02:12 -0300, saccade <trivik@gmail.com> escribió:

>>>> a, b = [], []
>>>> a.append(b)
>>>> b.append(a)
>>>> b in a
> True
>>>> a in a
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> RuntimeError: maximum recursion depth exceeded in cmp
>>>>
>>>> a is a[0]
> False
>>>> a == a[0]
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> RuntimeError: maximum recursion depth exceeded in cmp
>
> ----------
>
> I'm a little new to this language so my mental model on whats going on
> may need to be refined.
>
> I expect "a in a" to evaluate to "False". Since it does not it may be
> that while checking equality it uses "==" and not "is".

Exactly. Testing for equality appears to be the most wanted behavior, so
the language designers have chosen it.

> If that is the
> reason then the question becomes why doesn't "a == a[0]" evaluate to
> "False"?

The 'in' operator does something like this:

def __contains__(self, other):
for item in self:
if item==other:
return True
return False

(that is, a sequential scan). Note that it uses == to test for membership
(as you can read on http://docs.python.org/lib/typesseq.html). The '=='
operator for lists first compares their length, and being equal, then
compares their elements. In the 'a==b' case, both a and b have length 1,
so the next step is to compare a[0] (that is, b) with b[0] (that is, a).
Now we have to test b==a, which does the same thing again and again...
until the recursion limit is reached.

> As a side, and if that is the reason, is there a version of
> "in" that uses "is"? "a is in a" does not work.

You can write your own membership test based on identity ('is'):

def contains_by_identity(container, other):
return any(other is item for item in container)

--
Gabriel Genellina

On Nov 17, 6:02 pm, saccade <tri...@gmail.com> wrote:
> >>> a, b = [], []
> >>> a.append(b)
> >>> b.append(a)
> >>> b in a
> True
> >>> a in a
>
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> RuntimeError: maximum recursion depth exceeded in cmp
>
> >>> a is a[0]
> False
> >>> a == a[0]
>
> Traceback (most recent call last):
> File "<stdin>", line 1, in <module>
> RuntimeError: maximum recursion depth exceeded in cmp
>
> ----------
>
> I'm a little new to this language so my mental model on whats going on
> may need to be refined.

And that can be done by reading the fine manual, specifically
http://docs.python.org/ref/comparisons.html

This chapter contains 2 rules that are relevant to your questions:

R1: """ For the list and tuple types, x in y is true if and only if
there exists an index i such that x == y[i] is true. """ This might be
slightly clearer if read as "In the case of y being a tuple or list
(and x of course being any expression), x in y is true ...."

So that immediately tells you that it uses "x == y[i]", not "x is
y[i]".

R2: """ Tuples and lists are compared lexicographically using
comparison of corresponding elements. This means that to compare
equal, each element must compare equal and the two sequences must be
of the same type and have the same length. """

>
> I expect "a in a" to evaluate to "False". Since it does not it may be
> that while checking equality it uses "==" and not "is".

Yes, it uses "=="; see R1 above.

> If that is the
> reason then the question becomes why doesn't "a == a[0]" evaluate to
> "False"?

R1 says that you must evaluate a == a[0], but both are lists, so R2
says you must evaluate a[0] == a[0][0], but both of those are lists,
so you must evaluate a[0][0] == a[0][0][0] and so on ad infinitum.

So, you might ask, why do "a in b" and "b in a" both return True
(correctly)? That's because "a in b" needs to test "a == b[0]" and
that's the same as "a == a" and list comparison is smart enough to
make the cheap test "x is y[i]" first; a true value here means that
a less cheap (and possibly infinite) evaluation of "x == y[i]" can be
avoided.

> As a side, and if that is the reason, is there a version of
> "in" that uses "is"?

No. You could write your own, but it just doesn't appear practically
useful. For example,

x = string_extracted_from_file_or_db
y = ['1A', '9Z']

It's highly likely that when x == '1A', "x is_in y" is False --
because x and y[0] are different objects. Try explaining that to the
novices.

Worse: Consider z = ['A1', 'Z9']. It's highly likely that when x ==
'A1', "x is_in z" is True -- because an unguaranteed implementation-
dependent caper caches or "interns" some values, so that x and z[0]
are the same object. Try explaining that to the novices!!

Do you have a use case for that?

> "a is in a" does not work.

Correct, it's not valid syntax.

HTH,
John

On Nov 17, 3:40 am, "Gabriel Genellina" <gagsl-...@yahoo.com.ar>
wrote:
>
> You can write your own membership test based on identity ('is'):
>
Thank you for the practical (usable) advice and explanation of the
'==' operator.



On Nov 17, 4:35 am, John Machin <sjmac...@lexicon.net> wrote:
>
> And that can be done by reading the fine manual, specifically
>
This is true. I was being lazy by posting but have been pleasantly
surprised by the detailed responses. For the most, Python's beautiful
syntax has thus far required minimal thought of me. Programs feel more
like pseudo code than code and I may have gotten carried away.



On Nov 17, 4:35 am, John Machin <sjmac...@lexicon.net> wrote:
>
> Worse: Consider z = ['A1', 'Z9']. It's highly likely that when x ==
> 'A1', "x is_in z" is True -- because an unguaranteed implementation-
> dependent caper caches or "interns" some values, so that x and z[0]
> are the same object. Try explaining that to the novices!!
>
I am not a programmer so I feel odd commenting about language design
decisions. When my Prof. introduced python the first question that
popped into mind was that since "x=9; y=9; print x is y and x == y"
prints "True" is there a way to change the value of 9? He said that
was silly but after class showed me that statements "True = []" work
but suggested it was harmless and not quite a bug.

So if I am permitted to think of integers as immutable objects with
predefined labels (i.e. the integers used in the text of the program
code) that cannot de or re referenced then what a similar treatment of
characters will look like seams to be an arbitary (a design) decition.

In this vein it seams reasonable to expect 'a'[0] and 'ba'[1] to refer
to the same object. If one follows the convention used with integers
(9 and 9 refer to the same object) then 'ab' and 'ab' would be the
same. An equally reasonable assumption would be that 'ab' and 'ab' are
two different sequences and so not equal (I do not see the problem
here).

Actually this is what you said is left up to the implementation. '=='
seams to add a lot of power but I am not sure where or how (except as
a shortcut in the very special case of strings). Pardon the babble.



On Nov 17, 4:35 am, John Machin <sjmac...@lexicon.net> wrote:
>
> Do you have a use case for that?
>
I have a list of lists and want to see if another list is a member of
it. The content of the lists and the way they are related to each
other changes from program to program.

On Nov 19, 12:32 am, saccade <tri...@gmail.com> wrote:

> I am not a programmer so I feel odd commenting about language design
> decisions. When my Prof. introduced python the first question that
> popped into mind was that since "x=9; y=9; print x is y and x == y"
> prints "True" is there a way to change the value of 9? He said that
> was silly but after class showed me that statements "True = []" work
> but suggested it was harmless and not quite a bug.
>
> So if I am permitted to think of integers as immutable objects with
> predefined labels (i.e. the integers used in the text of the program
> code) that cannot de or re referenced then what a similar treatment of
> characters will look like seams to be an arbitary (a design) decition.
>
> In this vein it seams reasonable to expect 'a'[0] and 'ba'[1] to refer
> to the same object. If one follows the convention used with integers
> (9 and 9 refer to the same object) then 'ab' and 'ab' would be the
> same. An equally reasonable assumption would be that 'ab' and 'ab' are
> two different sequences and so not equal (I do not see the problem
> here).

The problem is with side-effets. With "pure" code, your reasoning
would be sound; but given that side-effects may alter the execution
path, ab[@T1] and ab[@T2] may _not_ refer to the same object. This
observation, is, of course, highly superfluous.

Regards,
Jordan

>
> On Nov 17, 4:35 am, John Machin <sjmac...@lexicon.net> wrote:
>> Worse: Consider z = ['A1', 'Z9']. It's highly likely that when x ==
>> 'A1', "x is_in z" is True -- because an unguaranteed implementation-
>> dependent caper caches or "interns" some values, so that x and z[0]
>> are the same object. Try explaining that to the novices!!
>>
> I am not a programmer so I feel odd commenting about language design
> decisions. When my Prof. introduced python the first question that
> popped into mind was that since "x=9; y=9; print x is y and x == y"
> prints "True" is there a way to change the value of 9? He said that
> was silly but after class showed me that statements "True = []" work
> but suggested it was harmless and not quite a bug.
>
> So if I am permitted to think of integers as immutable objects with
> predefined labels (i.e. the integers used in the text of the program
> code) that cannot de or re referenced then what a similar treatment of
> characters will look like seams to be an arbitary (a design) decition.

You are permitted to think as you will :-) However an integer object in
general has no predefined label. It may have multiple names, or no name
at all.

a = 4567; b = a; assert b is a

a = 2000; b = 1000 + 1000 # can assert b == a, can't assert b is a

You are approaching this from the wrong end. Briefly: Everything about
== works as expected. It is quite possible for a == b to be true but a
is b to be false. This is a non-arbitrary design decision. One fact that
I didn't tell you: Integers in range(-1, 101) are interned in the
CPython implementation, similar to the string interning that you
mentioned. For your wishes to come true, *every* value would have to be
interned. This is impractical.

>
> In this vein it seams reasonable to expect 'a'[0] and 'ba'[1] to refer
> to the same object.

> If one follows the convention used with integers
> (9 and 9 refer to the same object) then 'ab' and 'ab' would be the
> same. An equally reasonable assumption would be that 'ab' and 'ab' are
> two different sequences and so not equal (I do not see the problem
> here).
>
> Actually this is what you said is left up to the implementation. '=='
> seams to add a lot of power but I am not sure where or how (except as
> a shortcut in the very special case of strings). Pardon the babble.

Look at it this way: "==" (same value) is what one normally needs. The
utility of "is" (same object) is much smaller.

>
>
> On Nov 17, 4:35 am, John Machin <sjmac...@lexicon.net> wrote:
>> Do you have a use case for that?
>>
> I have a list of lists and want to see if another list is a member of
> it. The content of the lists and the way they are related to each
> other changes from program to program.

I meant "What practical use do you have for two mutually recursive
cursive lists?".

En Mon, 19 Nov 2007 03:32:12 -0300, saccade <trivik@gmail.com> escribió:

> So if I am permitted to think of integers as immutable objects with
> predefined labels (i.e. the integers used in the text of the program
> code) that cannot de or re referenced then what a similar treatment of
> characters will look like seams to be an arbitary (a design) decition.
>
> In this vein it seams reasonable to expect 'a'[0] and 'ba'[1] to refer
> to the same object. If one follows the convention used with integers
> (9 and 9 refer to the same object) then 'ab' and 'ab' would be the
> same. An equally reasonable assumption would be that 'ab' and 'ab' are
> two different sequences and so not equal (I do not see the problem
> here).

Note that the fact that integers are immutable means that Python *could*
share the same integer object any time that integer appears on the
program. For mutable objects --lists by example-- this is not possible
because different instances of the "same" list may be changed
independently.
In the following example, both x and y *could* refer to the same object,
but they don't:

py> x=1000
py> y=1000
py> x is y
False

In contrast, small integers are shared:

py> x=10
py> y=10
py> x is y
True

So immutability is a *necessary* condition for literals to be shared (in
the Python object model), but it's not *sufficient*.

--
Gabriel Genellina