[Python-Dev] re: I think my set module is ready for prime time

Greg Ewing greg@cosc.canterbury.ac.nz
Tue, 23 Jan 2001 17:46:26 +1300 (NZDT)

Greg Wilson <gvwilson@nevex.com>:

> an efficient implementation capable of
> handling mutable values (i.e. one that would allow things like sets of
> sets)

I suspect that such a thing is impossible. To avoid a
linear search you have to take advantage of some kind
of hashing or ordering, which you can't do if your
objects can change their values out from under you.

Also, there's nothing to stop someone from mutating
two previously unequal elements so that they're equal.
Then you have a "set" with two identical elements,
which isn't a set any more, it's just a collection.

So, I submit that the very concept of a set only
makes sense for immutable values.

Greg Ewing, Computer Science Dept, +--------------------------------------+
University of Canterbury,	   | A citizen of NewZealandCorp, a	  |
Christchurch, New Zealand	   | wholly-owned subsidiary of USA Inc.  |
greg@cosc.canterbury.ac.nz	   +--------------------------------------+