This is typically called a "bag". Maybe searching for that will help you find a recipe? On Tue, May 18, 2010 at 3:13 PM, Gustavo Narea <me@gustavonarea.net> 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.

This is the situation I have: I have a data structure that represents an arithmetic/boolean operation. Operations can be commutative, which means that the order of their operands don't change the result of the operation. This is, the following operations are equivalent:    operation(a, b, c) == operation(c, b, a) == operation(b, a, c)    operation(a, b, a) == operation(a, a, b) == operation(b, a, a)    operation(a, a) == operation(a, a)

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.

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.

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?

Cheers, -- Gustavo Narea <xri://=Gustavo>. | Tech blog: =Gustavo/(+blog)/tech  ~  About me: =Gustavo/about | _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/guido%40python.org

-- --Guido van Rossum (python.org/~guido)

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@python.org or comp.lang.python first, to see whether there is any enthusiasm from the wider Python community. -- Steven D'Aprano

Gustavo Narea <me@gustavonarea.net> writes:

I've been searching for a data structure like a tuple/list *but* unordered -- like a set, but duplicated elements shouldn't be removed.

By that description, you're looking for the “Bag” pattern. […]

A multiset is not exactly what I need: I still need to use the elements in the order they were given.

This appears to contradict your explicit request that the collection type be unordered. […]

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).

Okay, so you want something rather special; it would be misleading to call this an unordered type, since you *do* want ordering preserved. It's only the comparison operators that would ignore ordering. AFAIK you'll need to design and implement this yourself.

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?

Either way; but I think this discussion belongs on ‘python-ideas’ while the behaviour is still being designed. -- \ “On the internet you simply can't outsource parenting.” —Eliza | `\ Cussen, _Top 10 Internet Filter Lies_, The Punch, 2010-03-25 | _o__) | Ben Finney

Hello, Oleg.

class UnorderedList(list): def __eq__(self, other): if not isinstance(other, UnorderedList): return False return sorted(self) == sorted(other)

def __ne__(self, other): return not self.__eq__(other)

Do you need more than that?

Oleg.

That's what I had in mind. I think it'd be useful enough to go in the standard library. Now that there's a sample implementation, should I still try to demonstrate why I believe it's worth adding to the stdlib and get support? Cheers, - Gustavo. On Tue, May 18, 2010 at 11:13 PM, Gustavo Narea <me@gustavonarea.net> 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.

This is the situation I have: I have a data structure that represents an arithmetic/boolean operation. Operations can be commutative, which means that the order of their operands don't change the result of the operation. This is, the following operations are equivalent: operation(a, b, c) == operation(c, b, a) == operation(b, a, c) operation(a, b, a) == operation(a, a, b) == operation(b, a, a) operation(a, a) == operation(a, a)

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.

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.

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?

Cheers, -- Gustavo Narea <xri://=Gustavo>. | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about |

On Thu, 20 May 2010 08:40:25 pm Oleg Broytman wrote:

On Wed, May 19, 2010 at 09:56:03AM +0100, Gustavo Narea wrote:

...

I think it'd be useful enough to go in the standard library. Now that there's a sample implementation, should I still try to demonstrate why I believe it's worth adding to the stdlib and get support?

I think yes. How many developers would find it useful?..

Adding classes to the standard library doesn't come without cost. There's the maintenance and testing burden, and the cognitive burden of having to choose between similar classes with slight variations of behaviour. I don't think the benefit of this proposed subclass is great enough to outweigh the costs. It is a trivial subclass -- Oleg gave a seven line subclass of list -- with a fairly specialist use-case (it is a regular ordered list except for the purposes of equality comparisons). I don't believe it is a burden on developers to add it to their own application should they need it. -1 for this. If anyone wishes to support this proposal, please come up with a less misleading name than "UnorderedList". -- Steven D'Aprano

On 20/05/2010 17:02, geremy condra wrote:

On Wed, May 19, 2010 at 1:56 AM, Gustavo Narea<me@gustavonarea.net> wrote:

...

Hello, Oleg.

...

class UnorderedList(list): def __eq__(self, other): if not isinstance(other, UnorderedList): return False return sorted(self) == sorted(other)

def __ne__(self, other): return not self.__eq__(other)

Do you need more than that?

Oleg.

That's what I had in mind.

I think it'd be useful enough to go in the standard library. Now that there's a sample implementation, should I still try to demonstrate why I believe it's worth adding to the stdlib and get support?

Cheers,

- Gustavo.

I'm generally in favor of adding more data structures to Python, but I'm at best -0 on this. Besides being trivial to code and questionably useful, a much better implementation could be written using heap.

-1 from me, a trivial implementation of an uncommon use case. At this point the discussion belongs on python-ideas anyway. (The trouble with sorted is how it breaks with un-orderable types. There are at least two places now in the py3k standard library that have techniques for comparing sequences of heterogenous types - both prettyprint and unittest I believe. Perhaps a standard recipe for comparing or sorting such containers *does* belong somewhere more obvious.) All the best, Michael

Maybe with a better implementation I would go +0, but I'm hard pressed to see a case where this would be needed and could not be trivially written.

Geremy Condra _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/fuzzyman%40voidspace.org.u...

-- http://www.ironpythoninaction.com/ http://www.voidspace.org.uk/blog READ CAREFULLY. By accepting and reading this email you agree, on behalf of your employer, to release me from all obligations and waivers arising from any and all NON-NEGOTIATED agreements, licenses, terms-of-service, shrinkwrap, clickwrap, browsewrap, confidentiality, non-disclosure, non-compete and acceptable use policies (”BOGUS AGREEMENTS”) that I have entered into with your employer, its partners, licensors, agents and assigns, in perpetuity, without prejudice to my ongoing rights and privileges. You further represent that you have the authority to release me from any BOGUS AGREEMENTS on behalf of your employer.

Martin said:

Most definitely. Just in case it isn't clear: nobody else seems to think this is useful (let alone useful enough to go into the standard library). In addition, it's trivial to implement, more reason not to add it.

Yeah, fair enough. Thanks for your responses! :) -- Gustavo Narea <xri://=Gustavo>. | Tech blog: =Gustavo/(+blog)/tech ~ About me: =Gustavo/about |