[Python-Dev] Unordered tuples/lists

[Steven D'Aprano]

On Wed, 19 May 2010 08:13:42 am Gustavo Narea wrote:
> Hello, everybody.
>
> I've been searching for a data structure like a tuple/list *but*
> unordered -- like a set, but duplicated elements shouldn't be
> removed. I have not even found a recipe, so I'd like to write an
> implementation and contribute it to the "collections" module in the
> standard library.
[...]
> So, I need a type to store the arguments/operands so that if two of
> these collections have the same elements with the same multiplicity,
> they are equivalent, regardless of the order.

If I've understood your requirements, this should probably do it:

# Untested.
class MyCounter(collections.Counter):
    def __eq__(self, other):
        try:
            other = other.items()
        except AttributeError:
            return False
        return sorted(self.items()) == sorted(other)
    def __ne__(self, other):
        return not self == other


> A multiset is not exactly what I need: I still need to use the
> elements in the order they were given. For example, the logical
> conjuction (aka "and" operator) has a left and right operands; I need
> to evaluate the first/left one and, if it returned True, then call
> the second/right one. They must not be evaluated in a random order.

These requirements seem specialised enough to me that I expect it would 
be wasteful to add your class to the standard library. It's not quite 
an OrderedMultiSet (perhaps built on an OrderedDict), but a MultiSet 
that sometimes behaves as ordered and sometimes doesn't.


> To sum up, it would behave like a tuple or a list, except when it's
> compared with another object: They would be equivalent if they're
> both unordered tuples/lists, and have the same elements. There can be
> mutable and immutable editions (UnorderedList and UnorderedTuple,
> respectively).
>
> I will write a PEP to elaborate on this if you think it'd be nice to
> have. Or, should I have written the PEP first?

Neither. I think you will need to demonstrate the need for these first. 
The Python standard library doesn't generally add data types on the 
basis of theoretical nice-to-have, or even for a single person's 
use-case (unless that person is Guido *wink*). Your first step should 
be to publish the classes somewhere else. If they are small enough, the 
Python recipes on ActiveState would be good, otherwise PyPI. 

If there is a demonstrated need for these classes, and you (or somebody 
else) is willing to maintain them, then they may be added to the 
collections module (perhaps for Python 3.3, since I think 3.2 and 2.7 
are in feature-freeze).

I suggest you also take this idea to python-list at python.org or 
comp.lang.python first, to see whether there is any enthusiasm from the 
wider Python community.



-- 
Steven D'Aprano