473,241 Members | 1,629 Online

# Semantics of ==

Still trying to understand "=="... It appears as if two equal objects
can become unequal if you perform the same operations on them:
l=[1]
s=l
l.append(s)
w=[1]
r=[1,w]
w.append(r)
s [1, [...]] w [1, [1, [...]]] s==w True

Note that they're equal, yet are printed differently.
s[0]=2
w[0]=2
s==w

False

All of a sudden they have become unequal.

Axel
Jul 18 '05 #1
26 1807
"Axel Boldt" <ax*******@yahoo.com> wrote in message
Still trying to understand "=="... It appears as if two equal objects
can become unequal if you perform the same operations on them:
>>> l=[1]
>>> s=l
>>> l.append(s)
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s [1, [...]] >>> w [1, [1, [...]]] >>> s==w True

Note that they're equal, yet are printed differently.
>>> s[0]=2
>>> w[0]=2
>>> s==w

False

All of a sudden they have become unequal.

Axel

You've got a recursive structure! I originally thought
that the [...] was something you'd done to the printout,
but it isn't.

I think the original True is a bug. It's getting confused
by the recursion.

John Roth
Jul 18 '05 #2
Axel Boldt wrote:
Still trying to understand "=="... It appears as if two equal objects
can become unequal if you perform the same operations on them:
>>> l=[1]
>>> s=l
>>> l.append(s)
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s [1, [...]] >>> w [1, [1, [...]]] >>> s==w True
You're creating recursive lists (which is extremely rare in the real
world; I've never seen anyone create a self-referencing list in
real-life code. Tree structures and even recursive data structures are
one thing, but you're considering a very weird corner case here.
Note that they're equal, yet are printed differently.

That's fine. 1 and 1.0 are printed differently (and even are of
different types) but they're equal. If you try running through the
element-wise algorithm that Python uses to determine equality of lists,
you'll see that they are in fact equal at this point. The first element
is 1, the second element is a list whose first element is 1, the second
element of that list is a list whose first element is 1, ad infinitum.
>>> s[0]=2
>>> w[0]=2
>>> s==w False

All of a sudden they have become unequal.

Because now they really are not equal. Show them:
s [2, [...]] w [2, [1, [...]]]

The [...] doesn't indicate which sublist is recursively contained, so
you have to dig deeper:
s[1] [2, [...]] w[1][1]

[2, [1, [...]]]

So s is

[2, [2, [2, [2, ...]]]]

but w is

[2, [1, [2, [1, ...]]]]

Despite both recursing, it's clear that these lists are not element-wise
equal, and so Python is completely right in saying they're not.

Again, though, real-world creation of self-referencing lists is
extremely rare at best.

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Here day fights with night.
-- (the last words of Victor Hugo)
Jul 18 '05 #3
John Roth wrote:

"Axel Boldt" <ax*******@yahoo.com> wrote in message
Still trying to understand "=="... It appears as if two equal objects
can become unequal if you perform the same operations on them:
>>> l=[1]
>>> s=l
>>> l.append(s)
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s

[1, [...]]
>>> w

[1, [1, [...]]]
>>> s==w

True

Note that they're equal, yet are printed differently.
>>> s[0]=2
>>> w[0]=2
>>> s==w

False

All of a sudden they have become unequal.

Axel

You've got a recursive structure! I originally thought
that the [...] was something you'd done to the printout,
but it isn't.

I think the original True is a bug. It's getting confused
by the recursion.

Nah, Python's completely right here.

That the original s and w have extra finite elements doesn't make them
unequal. Follow Python's elementwise equality algorithm down and you'll
see they must be equal. The original s is
l = [1]
s = l
l.append(s)
s [1, [...]]

so it is

[1, [1, [1, [1, [1, ...]]]]]

The original w is
w = [1]
r = [1, w]
w.append(r)
w [1, [1, [...]]]

so it is also

[1, [1, [1, [1, [1, ...]]]]]

The real weirdness you reach is when the recursive sublists are not
appended, but prepended:
a = [1]
a.insert(0, a)
a

[[...], 1]

Here you could never even resolve a first element for comparison!

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Here day fights with night.
-- (the last words of Victor Hugo)
Jul 18 '05 #4
John Roth wrote:
>>> l=[1]
>>> s=l
>>> l.append(s)
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s [1, [...]]
>>> w

[1, [1, [...]]]
>>> s==w

True
You've created two cyclic data structures. The ==
operator happens to regard them as equal, but they're
not identical, since they have different structures.
The first one is a list which refers directly to
itself, and the second contains another list which
refers back to the first list.
>>> s[0]=2
>>> w[0]=2
>>> s==w

False
If you print out s and w at this point:
s [2, [...]] w [2, [1, [...]]]

They're now different in a way that == can see, so
it says they're not equal.
It appears as if two equal objects
can become unequal if you perform the same operations on them

Since the objects weren't really the same to begin with,
performing "the same operation" on them isn't entirely
possible.

By the way, it's not unusual for two objects that are not
identical to nevertheless compare ==, e.g.
5 == 5.0

True

even though one is an integer and the other is a float.
Generally, == means that the *value* of two objects is
"equivalent" in some sense. What sense that is depends
on the types of the objects.

The == machinery for lists happens to include some
heuristics which attempt to make sense of cyclic
structures. As you've seen, however, the results can be
a bit confusing, and mightn't be what you want in some
cases. Probably it's best to avoid applying == to cyclic
structures if you can.

--
Greg Ewing, Computer Science Dept,
University of Canterbury,
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg

Jul 18 '05 #5
At some point, ax*******@yahoo.com (Axel Boldt) wrote:
Still trying to understand "=="... It appears as if two equal objects
can become unequal if you perform the same operations on them:
>>> l=[1]
>>> s=l
>>> l.append(s)
You're building a cyclic list: l contains a reference to itself.
General advice: don't do that unless you know what you're doing.
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s [1, [...]] >>> w [1, [1, [...]]] >>> s==w True

Note that they're equal, yet are printed differently.

Element-by-element, they're equal, yes.
>>> s[0]=2
>>> w[0]=2
>>> s==w

False

All of a sudden they have become unequal.

That's b/c s originally looked like this if we expand out the
recursion a few more levels:
[1, [1, [1, [1, [...]]]]]
where each sub-list is also s.

w also looks like
[1, [1, [1, [1, [...]]]]]
where the *second* sub-list is w.

Set the first elements to 2:

s is now:
[2, [2, [2, [2, ...]]]]
w is now:
[2, [1, [2, [1, ...]]]]

See? The second sub-list of w is not w, so it wasn't changed.

--
|>|\/|<
/--------------------------------------------------------------------------\
|David M. Cooke
|cookedm(at)physics(dot)mcmaster(dot)ca
Jul 18 '05 #6
On Tue, Mar 16, 2004 at 07:07:27PM -0500, John Roth wrote:
"Axel Boldt" <ax*******@yahoo.com> wrote in message
>>> s

[1, [...]]
>>> w

[1, [1, [...]]]
>>> s==w

True

[...]
I think the original True is a bug. It's getting confused
by the recursion.

I don't think it's a bug. In what sense are they unequal? Both variables
are a sequence of two elements, the integer 1, and a sequence that's equal
to the outer sequence (i.e. s==s[1] is True, as Python will tell you).
Every element of the sequence s is equal to the corresponding element of the
sequence w, as far as I can see, even though there is infinite recursion.

Python is behaving exactly as I would expect it to. (Although in the face
of such pathological data structures, I wouldn't mind terribly much if it
didn't...)

-Andrew.
Jul 18 '05 #7

"Axel Boldt" <ax*******@yahoo.com> wrote in message
Still trying to understand "=="...
means equal in value as defined be Python and user code
It appears as if two equal objects
can become unequal if you perform the same operations on them:
>>> l=[1]
>>> s=l
>>> l.append(s)
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s [1, [...]] >>> w [1, [1, [...]]] >>> s==w True

Note that they're equal, yet are printed differently.

This is routine:
print 0, 0.0, 0==0.0 0 0.0 1 1.0 == .999999999999999999999999999999999999 1

Equal in value != equal in internal structure.
>>> s[0]=2
>>> w[0]=2
>>> s==w False

All of a sudden they have become unequal.

1 == 1.0 but type(1) != type(1.0). Okay, that's cheating, so
1|1 1 1.0|1 Traceback (most recent call last):
File "<stdin>", line 1, in ?
TypeError: unsupported operand type(s) for |: 'float' and 'int'

Doing same thing to equals has different results. Or
a=12345678909876
b=float(a)
a*a, b*b (152415787745757059730335376L, 1.5241578774575706e+026)

now unequal to human eye, but
a*a == b*b

1

due to conversion of a*a to float(a*a) for comparison.

Terry J. Reedy

Jul 18 '05 #8
Erik Max Francis wrote:

You're creating recursive lists (which is extremely rare in the real
world; I've never seen anyone create a self-referencing list in
real-life code. Tree structures and even recursive data structures are
one thing, but you're considering a very weird corner case here.

Actually they are not that seldom. I have made several. But off course
when I got my recursive code debugged they where gone
;-)
regards Max M
Jul 18 '05 #9
Erik Max Francis <ma*@alcyone.com> wrote
Axel Boldt wrote:
>>> l=[1]
>>> s=l
>>> l.append(s)
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s [1, [...]] >>> w [1, [1, [...]]] >>> s==w

True

If you try running through the
element-wise algorithm that Python uses to determine equality of lists,
you'll see that they are in fact equal at this point.

I couldn't find that algorithm in the language reference, only in 5.9:
"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."

That definition doesn't seem to fully specify equality of list values:
to determine whether s==w, I first note that they both have length 2
and both have 1 as their first element, the second element of s is a
pointer to s, the second element of w is a two-element list, with
first element 1 and second element a pointer to w. So now I have to
determine whether s is equal to the two element list with first
element 1 and second element a pointer to w. They both have two
elements, they both share the first element 1, the second element of s
is a pointer to s, the second element of the other list is a pointer
to w. Now I'm back where I started: I have to test whether s==w. So
the definition in the language reference is circular and both
conclusions s==w and s!=w are consistent with it. I hope that the
actual result received, i.e. s==w, is not implementation dependent?

It now appears to me that there are four levels of equality in Python:

a is b => pickle.dumps(a)==pickle.dumps(b) => repr(a)==repr(b) => a==b

and none of the arrows can be reversed in general. I suppose I had
naively assumed the last three to be equivalent. Is there a string
function analogous to pickle.dumps or repr which only takes values
into account, not internal structure? Such a function could be useful
for hashing the values of mutables.

Axel
Jul 18 '05 #10
Andrew Bennetts <an***************@puzzling.org> writes:
On Tue, Mar 16, 2004 at 07:07:27PM -0500, John Roth wrote:
"Axel Boldt" <ax*******@yahoo.com> wrote in message

[...]
>>> s
[1, [...]]
>>> w
[1, [1, [...]]]
>>> s==w
True

[...]

I think the original True is a bug. It's getting confused
by the recursion.

I don't think it's a bug. In what sense are they unequal? Both variables
are a sequence of two elements, the integer 1, and a sequence that's equal
to the outer sequence (i.e. s==s[1] is True, as Python will tell you).
Every element of the sequence s is equal to the corresponding element of the
sequence w, as far as I can see, even though there is infinite recursion.

Python is behaving exactly as I would expect it to. (Although in the face
of such pathological data structures, I wouldn't mind terribly much if it
didn't...)

It will raise RuntimeError (or somesuch) in Python 2.4.

Cheers,
mwh

--
#ifndef P_tmpdir
printf( "Go buy a better computer" );
exit( ETHESKYISFALLINGANDIWANTMYMAMA );
-- Dimitri Maziuk on writing secure code, asr
Jul 18 '05 #11

"Axel Boldt" <ax*******@yahoo.com> wrote in message
That definition doesn't seem to fully specify equality of list values:
to determine whether s==w, I first note that they both have length 2
and both have 1 as their first element, the second element of s is a
pointer to s, the second element of w is a two-element list, with
first element 1 and second element a pointer to w. So now I have to
determine whether s is equal to the two element list with first
element 1 and second element a pointer to w. They both have two
elements, they both share the first element 1, the second element of s
is a pointer to s, the second element of the other list is a pointer
to w. Now I'm back where I started: I have to test whether s==w. So
the definition in the language reference is circular and both
conclusions s==w and s!=w are consistent with it. I hope that the
actual result received, i.e. s==w, is not implementation dependent?

You could try old versions if you have access back far enough ;-).

I vaguely remember a discussion on PyDev list, some years ago, of
'equality' of infinite recursive structures. I believe there was a change
in the direction of simplicity and robustness to the current algorithm from
a more ambitious algorithm that might have detected s != w -- but which
sometimes had problems. For dicts at least, a finite printout (instead of
infinite looping requiring a keyboard interrupt) is an innovation since
1.4.

Terry J. Reedy

Jul 18 '05 #12
"Terry Reedy" <tj*****@udel.edu> wrote
I vaguely remember a discussion on PyDev list, some years ago, of
'equality' of infinite recursive structures. I believe there was a change
in the direction of simplicity and robustness to the current algorithm from
a more ambitious algorithm that might have detected s != w -- but which

Nowadays, an equality test which detects difference of s and w could
be defined by comparing the strings pickle.dumps(s) and
pickle.dumps(w).

Axel
Jul 18 '05 #13
Axel Boldt wrote:
I couldn't find that algorithm in the language reference, only in 5.9:
"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."

That definition doesn't seem to fully specify equality of list values:
...
Sure it does; the rule can be used recursively. As I indicated,
according to its definition, your s and w are clearly equal despite
being infinite and having different internal representations. == has to
do with value, not identity.
I hope that the
actual result received, i.e. s==w, is not implementation dependent?
They're also equal in Jython. It wouldn't surprise me if you could find
an implementation where they might not compare equal, because this is
such a pathological case. As I indicated before, I've never seen anyone
use a self-referencing list in any real-world code, ever.
It now appears to me that there are four levels of equality in Python:

a is b => pickle.dumps(a)==pickle.dumps(b) => repr(a)==repr(b) => a==b

and none of the arrows can be reversed in general. I suppose I had
naively assumed the last three to be equivalent.
__eq__ and __repr__ can be overridden to do whatever the programmer
wants, so why would you think the last three would be equivalent?

repr(a) == repr(b) is certainly not equivalent to a == b. Consider the
default repr of an arbitrary class, which will only be equal to another
object if a is b -- that is, if they represent the same object. Beyond
that, it's up to the programmer to make custom types behave how he or
she would like with respect to equality and repr.
Is there a string
function analogous to pickle.dumps or repr which only takes values
into account, not internal structure?

How can you define the value of an arbitrary object without reference to
its internal structure?

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Liberty is the right to do whatever the law permits.
-- Charles Louis Montesquieu
Jul 18 '05 #14
Axel Boldt wrote:
Nowadays, an equality test which detects difference of s and w could
be defined by comparing the strings pickle.dumps(s) and
pickle.dumps(w).

But this is a good indication that pickle.dumps(a) == pickle.dumps(b) is
_not_ equivalent to a == b, since your s and w self-referencing lists
are a good example of where the internal structure of the two lists is
not identical but they _are_ equal according to Python's definition of
sequence comparison, as I demonstrated earlier.

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Liberty is the right to do whatever the law permits.
-- Charles Louis Montesquieu
Jul 18 '05 #15
Erik Max Francis <ma*@alcyone.com>
Axel Boldt wrote:
I couldn't find that algorithm in the language reference, only in 5.9:
"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."

That definition doesn't seem to fully specify equality of list values:
...

Sure it does; the rule can be used recursively.

....and then it can run into an infinite loop. I explained that for the
example s==w in the part you deleted. The recursion does not always
have a base case; the rule does not always give a definite truth
value.
I hope that the
actual result received, i.e. s==w, is not implementation dependent?

They're also equal in Jython. It wouldn't surprise me if you could find
an implementation where they might not compare equal, because this is
such a pathological case.

.... i.e. such a fun case. If there really is an implementation
dependency hidden in something as fundamental as == for lists, that'd
better be mentioned in the language reference.
Is there a string
function analogous to pickle.dumps or repr which only takes values
into account, not internal structure?

How can you define the value of an arbitrary object without reference to
its internal structure?

Well, you claim that s and w have the same value yet different
internal structure, so you must work with some definition of "value"
that's different from internal structure. I don't know what it is, and
the language reference doesn't fully specify it.

I.e., I'm interesting in a function val : lists -> strings with the
property val(l1) == val(l2) iff l1 == l2. That would also considerably
clarify the semantics of == for lists, which I still don't understand.

Axel
Jul 18 '05 #16
Axel Boldt wrote:
...and then it can run into an infinite loop. I explained that for the
example s==w in the part you deleted. The recursion does not always
have a base case; the rule does not always give a definite truth
value.
But the == operator doesn't run into an infinite loop, so this is much
... i.e. such a fun case. If there really is an implementation
dependency hidden in something as fundamental as == for lists, that'd
better be mentioned in the language reference.
I don't know what you're talking about here. The behavior you saw with
your s == w example is completely consistent with Python's definition of
equality and Python's definition of equal sequences. You have some
Python.
How can you define the value of an arbitrary object without
reference to
its internal structure?

Well, you claim that s and w have the same value yet different
internal structure, so you must work with some definition of "value"
that's different from internal structure. I don't know what it is, and
the language reference doesn't fully specify it.

1 and 1.0 have different internal structure, but they're equal. This is
an obvious existence proof that Python simply does not follow the
equivalence that you're thinking of.

Equality does _not_ indicate equivalence in internal structure in
Python. This is especially true in Python where users can define their
own equality behavior, so you can make it whatever you want -- you can
make your own instance that compares equal (or unequal) with absolutely
everything. If 1 == 1.0 didn't convince you, surely this will convince
you that equality and equivalence in internal structure are not related
in Python.
I.e., I'm interesting in a function val : lists -> strings with the
property val(l1) == val(l2) iff l1 == l2. That would also considerably
clarify the semantics of == for lists, which I still don't understand.

Why are you interested in such a function?

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ I do not promise to consider race or religion in my appointments.
I promise only that I will not consider them. -- John F. Kennedy
Jul 18 '05 #17
Axel Boldt wrote:
Like I said, it would clarify the semantics of == for lists. Another
use would be to hash on values of lists.

What part of the semantics are you unclear about? Two sequences are
equal if they are element-wise equal. That is the definition that
people rely on, that's the definition that the interpreter uses, and
that definition is even consistent with the behavior you saw with the
self-referencing lists which for some reason surprised you.

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Whoever named it necking was a poor judge of anatomy.
-- Groucho Marx
Jul 18 '05 #18
[Axel Boldt]
>>> l=[1]
>>> s=l
>>> l.append(s)
>>> w=[1]
>>> r=[1,w]
>>> w.append(r)
>>> s [1, [...]] >>> w [1, [1, [...]]] >>> s==w True

Note that they're equal, yet are printed differently.
>>> s[0]=2
>>> w[0]=2
>>> s==w

False

All of a sudden they have become unequal.
[John Roth] You've got a recursive structure! I originally thought
that the [...] was something you'd done to the printout,
but it isn't.

I think the original True is a bug. It's getting confused
by the recursion.

Armin Rigo found and fixed this for Py2.4:

Python 2.4a0 (#46, Mar 23 2004, 01:55:44) [MSC v.1200 32 bit (Intel)] on win32
<snipped>
s [1, [...]] w [1, [1, [...]]] s==w

Traceback (most recent call last):
File "<pyshell#9>", line 1, in -toplevel-
s==w
RuntimeError: maximum recursion depth exceeded in cmp
Raymond Hettinger
Jul 18 '05 #19
>>>>> "Raymond" == Raymond Hettinger <py****@rcn.com> writes:

Raymond> [Axel Boldt]
> >>> l=[1] > >>> s=l > >>> l.append(s) > >>> w=[1] > >>> r=[1,w] >
>>> w.append(r) > >>> s [1, [...]] > >>> w [1, [1, [...]]] > >>>

s==w > True
>
> Note that they're equal, yet are printed differently.
>
> >>> s[0]=2 > >>> w[0]=2 > >>> s==w > False
>
> All of a sudden they have become unequal.
Raymond> [John Roth]
You've got a recursive structure! I originally thought that the [...]
was something you'd done to the printout, but it isn't.

I think the original True is a bug. It's getting confused by the
recursion.

Raymond> Armin Rigo found and fixed this for Py2.4:

Raymond> Python 2.4a0 (#46, Mar 23 2004, 01:55:44) [MSC v.1200 32 bit
Raymond> (Intel)] on win32 <snipped> s Raymond> [1, [...]] w Raymond> [1, [1, [...]]] s==w

Raymond> Traceback (most recent call last): File "<pyshell#9>", line 1,
Raymond> in -toplevel- s==w RuntimeError: maximum recursion depth
Raymond> exceeded in cmp

I'm confused... what makes the new behaviour more "correct" than the original?

Regards,
Isaac.
Jul 18 '05 #20
Erik Max Francis <ma*@alcyone.com> wrote
What part of the semantics are you unclear about? Two sequences are
equal if they are element-wise equal.
That definition is circular.
That is the definition that people rely on,
Yes.
that's the definition that the interpreter uses,
No.
and that definition is even consistent with the behavior you saw with the
self-referencing lists which for some reason surprised you.

Yes, s==w is consistent with the definition, but s!=w would also have
been consistent with it.

Consider for instance the following definition:
* all strings and numbers are called "well-founded"
* a list is called well-founded if and only if all its elements are
well-founded.

l=[]
l.append(l)
Is l well-founded? Both answers "yes" and "no" are consistent with the
above definition. If you write a program to determine whether a given
list is well-founded, it will run into an infinite loop. Similarly, if
you try to write a program implementing the above simple-minded
definition of list-equality, it'll run into an infinite loop. Since
Python does not run into an infinite loop, it must use a different
definition.

Axel
Jul 18 '05 #21
>>>>> "Axel" == Axel Boldt <ax*******@yahoo.com> writes:

Axel> l=[] l.append(l) Is l well-founded? Both answers "yes" and "no"
Axel> are consistent with the above definition. If you write a program
Axel> to determine whether a given list is well-founded, it will run
Axel> into an infinite loop.

That depends on how you write the program. I can easily give you a program
that will tell you either this is or is not, depending on whether you like
it one way or the other---provided that I have a little bit of memory to
play with, or I'm allowed to look at my own back-trace.

Regards,
Isaac.
Jul 18 '05 #22
Axel Boldt wrote:
Erik Max Francis <ma*@alcyone.com> wrote
What part of the semantics are you unclear about? Two sequences are
equal if they are element-wise equal.
That definition is circular.

No, because presumably you already understand what equality means for
two non-sequence objects.
and that definition is even consistent with the behavior you saw
with the
self-referencing lists which for some reason surprised you.

Yes, s==w is consistent with the definition, but s!=w would also have
been consistent with it.

your examples was completely consistent with this definition, whether
you realize it or not. The cases that you thought shouldn't have been
equal were in fact equal, and the cases that you thought should have
been equal weren't, in fact, equal. I and several others carefully
demonstrated this to you, but you ignored us so that you could continue
ranting that Python's list equality is broken, when there is no evidence
that it is.
Consider for instance the following definition:
* all strings and numbers are called "well-founded"
* a list is called well-founded if and only if all its elements are
well-founded.

l=[]
l.append(l)
Is l well-founded? Both answers "yes" and "no" are consistent with the
above definition.

No they aren't, since l's first element is a list, not a string or
number.

What is the point of this definition?

--
__ Erik Max Francis && ma*@alcyone.com && http://www.alcyone.com/max/
/ \ San Jose, CA, USA && 37 20 N 121 53 W && &tSftDotIotE
\__/ Drifting from woman-who-tries misconstrued / Shifting to
woman-wise -- Lamya
Jul 18 '05 #23
Erik Max Francis <ma*@alcyone.com> wrote
Axel Boldt wrote:
Erik Max Francis <ma*@alcyone.com> wrote
What part of the semantics are you unclear about? Two sequences are
equal if they are element-wise equal.
That definition is circular.

No, because presumably you already understand what equality means for
two non-sequence objects.

Yes, but a list can contain other lists, and even itself, as elements.
So in order to understand what equality for lists means, according to
the above definition, you already need to understand what equality for
lists means. That's what makes the definition circular. I thought we
had clarified that much a week ago.
Consider for instance the following definition:
* all strings and numbers are called "well-founded"
* a list is called well-founded if and only if all its elements are
well-founded.

l=[]
l.append(l)
Is l well-founded? Both answers "yes" and "no" are consistent with the
above definition.

No they aren't, since l's first element is a list, not a string or
number.

The above definition does not require that the first element of a
well-founded list be a string or number. It could also be a
well-founded list.
What is the point of this definition?

To show how easy it is to give circular definitions (and
non-terminating recursive functions) when dealing with lists.

Axel
Jul 18 '05 #24
On Mon, Mar 29, 2004 at 04:26:34AM -0800, Axel Boldt wrote:
Erik Max Francis <ma*@alcyone.com> wrote
Axel Boldt wrote:
Erik Max Francis <ma*@alcyone.com> wrote

> What part of the semantics are you unclear about? Two sequences are
> equal if they are element-wise equal.

That definition is circular.

No, because presumably you already understand what equality means for
two non-sequence objects.

Yes, but a list can contain other lists, and even itself, as elements.
So in order to understand what equality for lists means, according to
the above definition, you already need to understand what equality for
lists means. That's what makes the definition circular. I thought we
had clarified that much a week ago.

No, it makes the definition recursive. There's a difference.

-Andrew.
Jul 18 '05 #25
On 3/29/04 4:26 AM, "Axel Boldt" <ax*******@yahoo.com> wrote:

[snip]
Consider for instance the following definition:
* all strings and numbers are called "well-founded"
* a list is called well-founded if and only if all its elements are
well-founded.

l=[]
l.append(l)
Is l well-founded? Both answers "yes" and "no" are consistent with the
above definition.

No they aren't, since l's first element is a list, not a string or
number.

The above definition does not require that the first element of a
well-founded list be a string or number. It could also be a
well-founded list.

Seems to me that the example given makes it clear that l is not
well-founded. Look at it step by step:

(1) >>> l = []

at this stage, l is *not* well-founded, since it's a list with no elements,
and the definition explicitly states that a well-founded list is a list
containing all and only well-founded elements, and the only thing other than
lists that can be well-founded are strings and numbers.

(2) >>> l.append(l)

at this stage, l is *still* not well-founded, since all it contains is a
list that we've already seen is not well-founded (cf. the original
definition)...
Fred.

Jul 18 '05 #26

"Fred Mailhot" <fr**********@videotron.ca> wrote in message
news:BC8F332F.130C3%fr**********@videotron.ca...
Consider for instance the following definition:
* all strings and numbers are called "well-founded"
* a list is called well-founded if and only if all its elements are
well-founded.
Seems to me that the example given makes it clear that l is not
well-founded.

No. In my experience, the standard interpretation of such definitions is
that the empty list (in this case) 'trivially satisfies' the condition
precisely because it has no elements to check for conformance.

In pure set theory, sets only have sets as members. The empty set
'trivially satifies' this condition, to use the standard catchphrase.
Authors vary on whether this sort of this is said explicitly or not.

Terry J. Reedy

Jul 18 '05 #27

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 10 by: Stefan Höhne | last post by: Hi, as I recon, std::vector::clear()'s semantics changed from MS VC++ 6.0 to MS' DOT.NET - compiler. In the 6.0 version the capacity() of the vector did not change with the call to... 0 by: Karl Smith | last post by: Headless wrote in reply to Christoph Paeper : > Semantically this is 100% identical to: > Semantically
this
is 100% identical... 4 by: David Rasmussen | last post by: The problem comes up in all sorts of contexts. But here is an example: We want to model the basics of chess, maybe for making a chess program, or maybe just to make an interactive board or ... ... 2 by: maxw_cc | last post by: Hi to all of you, I was wondering what the Semantics part in C standard is really for? What should be on the constraints part and what should be on the semantics part? Is the implementation... 21 by: Paul Steckler | last post by: Here's some code that's giving me differing results, depending on the compiler. typedef foo { int A,B; } FOO; int main() { 1 by: Doug Wyatt | last post by: So I'll preface this with the fact that I'm a UNIX developer by training and have just recently gotten in to C# development on Windows. I'm basically running in to a problem whereby I suspect... 14 by: Dan Jacobson | last post by: How is this for correct HTML 4.01 headers?: