What about the following compromise: there are two set types, ImmutableSet and MutableSet, with a common supertype Set. ImmutableSet adds __hash__, while MutableSet adds insert and remove, to the common core of methods inherited from Set, such as __contains__ and __iter__.
Since it's apparently too wild an idea to say "adapt to protocol" when one means "adapt to protocol", at least for the next few releases (and that, in the optimistic hypothesis that my future rewrite of the adaptation PEP is favorably received), there will of course need to arise yet another special purpose way to express this same general idea, such as:
class MutableSet(Set): ... def insert(self, item): try: item = item.asSetItem() except AttributeError: pass self.data[item] = True
def asSetItem(self): return ImmutableSet(self)
or the like.
This would run into similar problems as the PEP's auto-freeze approach when using "s1 in s2". If s1 is a mutable set, this creates an immutable copy for the test and then throws it away. The PEP's problem is that it's too easy to accidentally freeze a set; the problem with your proposal is "merely" one of performance. Yet I think both are undesirable, although I still prefer your solution.
--Guido van Rossum (home page: http://www.python.org/%7Eguido/)