We are not going to change the implementation of sets so fundamentally, mostly because having O(1) behaviors is so nice (add, remove, membership check, etc).

What I want are such interfaces (no matter with standard set): class IDynSet: # "Dyn" means it have methods like ipop_both def ipop_both(self): if hasattr(self, 'pop_mutable'): elem = self.pop_mutable() elif hasattr(self, 'ipop_immutable'): elem, self = self.ipop_immutable() else: raise return elem, self class IMutableDynSet(IDynSet): def pop_mutable(self): return self.pop() class IImutableDynSet(IDynSet): def ipop_immutable(self): elem, new = self.ipop() # ipop not pop return elem, new