[Python-Dev] Re: set() and frozenset()

[David Eppstein]

In article <001401c3aba5$28a8a3c0$183ac797 at oemcomputer>,
 "Raymond Hettinger" <raymond.hettinger at verizon.net> wrote:

> The C implementation of sets is now ready for your experimentation and
> comment.  If fulfills most of Greg's proposal at:
> http://www.python.org/peps/pep-0218.html
...
> The differences from sets.py are:
> 
> . The containers are now named set() and frozenset().  The lowercase
> convention is used to make the names consistent with other builtins like
> list() and dict().  User feedback said that the name ImmutableSet was
> unwieldy (?sp), so frozenset() was chosen as a more succinct
> alternative.

I for one found it difficult to remember whether it was Immutable or 
Immutible.

> . There is no automatic conversion from the mutable type to the
> non-mutable type.  User feedback revealed that this was never needed.

More than never needed, I would find it confusing to put a set into a 
dictionary or whatever and then find that some other object has been put 
there in its place.

> Also, removing it simplified the code considerably.  The result is more
> straight-forward and a lot less magical.  David Eppstein provided code
> examples demonstrating that set() and frozenset() are just right for
> implementing common graph algorithms and NFA/DFAs.  

Well, I used Set and ImmutableSet, but yes, they're very useful.
Thanks to Raymond for adding the backward compatibility to Python 2.2 
needed for me to try this out.

FWIW, I wrote another one yesterday, using a set partition refinement 
technique for recognizing chordal graphs; the code is at 
http://www.ics.uci.edu/~eppstein/PADS/Chordal.py, with subroutines in 
LexBFS.py, PartitionRefinement.py, and Sequence.py. The same partition 
refinement technique shows up in other algorithms including DFA 
minimization and would be quite painful without sets.

Sets seems to me to be as fundamental a data structure as lists and 
dictionaries, and I'm enthusiastic about this becoming built in and 
faster. I would have liked to see {1,2,3} type syntax for sets, but the 
set/frozenset issue makes that a little problematic and perhaps the new 
iterator expressions make it unnecessary.

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science