collections.abc.OrderedMapping

[jab]

BPO	28912
Nosy	@brettcannon, @rhettinger, @vstinner, @jab
Files	jab-orderedmapping-1.patch jab-orderedmapping-2.patch

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2016-12-11.00:55:59.152>
created_at = <Date 2016-12-08.23:00:34.284>
labels = ['type-feature', 'library']
title = 'collections.abc.OrderedMapping'
updated_at = <Date 2016-12-21.16:23:27.448>
user = 'https://github.com/jab'

bugs.python.org fields:

activity = <Date 2016-12-21.16:23:27.448>
actor = 'jab'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2016-12-11.00:55:59.152>
closer = 'rhettinger'
components = ['Library (Lib)']
creation = <Date 2016-12-08.23:00:34.284>
creator = 'jab'
dependencies = []
files = ['45804', '45805']
hgrepos = []
issue_num = 28912
keywords = ['patch']
message_count = 7.0
messages = ['282742', '282744', '282761', '282763', '282892', '282895', '283766']
nosy_count = 5.0
nosy_names = ['brett.cannon', 'rhettinger', 'vstinner', 'jab', 'abarnert']
pr_nums = []
priority = 'normal'
resolution = 'rejected'
stage = None
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue28912'
versions = []

[jab]

Since code can be clearer than prose, I just sketched this idea out in the attached patch. Please take a look at it as a minimum demonstration of the concept.

Rationale:

The Python standard library provides collections.OrderedDict, along with several ABCs which OrderedDict extends, such as collections.abc.Mapping and (as of 3.6) collections.abc.Reversible, to enable better composability and interoperability.

Currently there is no collections.abc.OrderedMapping ABC, but I wonder if there should be. OrderedMapping could provide a concrete, generic implementation of eq, that performed an order-sensitive comparison when passed another OrderedMapping, while performing an order-insensitive comparison when passed an unordered Mapping. Then OrderedDict could derive from OrderedMapping, inheriting its generic eq implementation, rather than implementing its own eq method. Currently, OrderedDict's own eq implementation does isinstance(other, OrderedDict) to decide whether to perform an order-sensitive comparison, which thwarts interoperability. OrderedMapping could also derive from Reversible, signaling that classes that extend it implement reversed.

The interoperability gain here is not just theoretical. Several packages are published on PyPI which would be able to interoperate better if they could all extend a common OrderedMapping interface. Grant Jenks' sortedcontainers.SortedDict[1] and my own bidict.OrderedBidict[2] are two particularly popular examples.

Thanks for your consideration, and look forward to your feedback.

[1] http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html
[2] https://bidict.readthedocs.io/en/dev/other-bidict-types.html#orderedbidict

[jab]

This patch improves the OrderedMapping.eq implementation to be more generic in the case that other is an unordered Mapping of the same length as self.

[jab]

Come to think of it, to be exact, rather than extending Reversible, OrderedMapping could extend a narrower interface, something like collections.abc.Ordered, along with extending Mapping. (Reversible implies Ordered, but Ordered does not imply Reversible: a singly-linked list is Ordered but not Reversible, for example.)

I guess we don't currently have Ordered because it wouldn't necessarily add any abstractmethods beyond what Iterable already provides. But it could provide a generic, concrete __eq__ implementation, something like:

class Ordered(Iterable):
    def __eq__(self, other):
        if not isinstance(other, Ordered):
            return NotImplemented
        return all(i == j for (i, j) in zip(self, other))

which is not something that any existing collections.abc Iterable currently provides.

Even if an Ordered interface that's totally empty were available in the standard library, then Iterables across diparate codebases could opt into extending it as a standard signal that they iterate over their elements in a well-defined order, and could participate in other polymorphic code. Currently we have no such standard signal, do we?

[jab]

I only just found the "[Python-ideas] Adding collections.abc.Ordered" thread at https://mail.python.org/pipermail/python-ideas/2015-November/037146.html - sorry for not seeing it sooner. Looking forward to catching up on what I missed.

[rhettinger]

Thank you for the link, it was nice to see Guido's reasons for giving a -0 on the proposal. I would add that I haven't see any code in the wild that would benefit from testing isinstance(m, OrderedMapping) and taking some different action depending on the result.

Grant's sortedcollection is more sequence-like than mapping-like and the bidict has its own interesting properties and neither are substitutable for an OrderedDict. In other words, the only properties these cluster on is the ordered equality feature. IMO, that particular feature hasn't established itself as being valuable (we don't see much use of it with the existing ordered dicts, and likewise in the database world, table equivalence based on exact order rather than content equivalence is uncommon).

Given the limited utility, I am going to decline the proposal. It is an interesting idea but I believe it that it would clutter the module, slightly drowning-out the ABCs that have more broad and established utility.

One other thought is that the proposed OrderedMapping ABC might not fit well in a possible future Python where the behavior Python 3.6 ordered-and-compact dicts becomes guaranteed but where we retain the traditional unordered equality comparison.

[jab]

Sorry to hear but thanks for the consideration. To follow up on your comments:

nice to see Guido's reasons for giving a -0 on the proposal.

(Guido was giving his -0 on a proposal for collections.abc.Ordered, whereas the main proposal here is collections.abc.OrderedMapping, sorry if that was confusing.)

I would add that I haven't see any code in the wild that would benefit from testing isinstance(m, OrderedMapping) and taking some different action depending on the result.

Just to give you another data point, bidict.orderedbidict has been released into the wild for a little over 10 months, and people are using it. OrderedMapping would give users the following benefits:

>> noble = orderedbidict([(2, 'helium'), (10, 'neon'), (18, 'argon')])

>>> b = bidict(noble)  # Discards the order.
>>> b  # Calls BidictBase.__repr__.
bidict({10: 'neon', 18: 'argon', 2: 'helium'})

>>> noble  # Also calls BidictBase.__repr__.
orderedbidict([('Cairo', 'Egypt'), ('Lima', 'Peru'), ('Tokyo', 'Japan')])

>> # i.e. BidictBase.__repr__ interrogates isinstance(self, OrderedMapping)
>> # to reflect any ordering correctly in the string representation.

>>> # OrderedMapping.__eq__ also checks isinstance(other, OrderedMapping)
>>> # to conditionally turn on order-sensitivity:
>>> noble == collections.OrderedDict(noble.items())
True
>>> noble == collections.OrderedDict(reversed(noble.items()))
False
>>> noble == dict(reversed(noble.items()))  # order-insensitive
True

(collections.OrderedDict and sortedcontainers.SortedDict could reap these same benefits from an OrderedMapping class.)

Grant's sortedcollection is more sequence-like than mapping-like and the bidict has its own interesting properties and neither are substitutable for an OrderedDict.

Hm, I don't quite follow this. OrderedDict, SortedDict, and orderedbidict are all OrderedMappings, and should therefore be passable to any function that expects an OrderedMapping.

This part I do follow:

In other words, the only properties these cluster on is the ordered equality feature. IMO, that particular feature hasn't established itself as being valuable.... It is an interesting idea but I believe it that it would clutter the module, slightly drowning-out the ABCs that have more broad and established utility.

But based on this rationale, I would have thought Reversible wouldn't have been added. It was only after I found https://bugs.python.org/issue25987 the other day and saw that Reversible will be in 3.6 that I thought OrderedMapping had a case of similar strength, and so it seemed worth taking the time to try to contribute it for 3.7.

In any case, thanks again for your consideration, and if you have any further thoughts to share, it'd be much appreciated.

[jab]

For the record, it looks like Victor Stinner suggested doing this in https://mail.python.org/pipermail/python-dev/2016-September/146349.html

Brett Cannon replied in https://mail.python.org/pipermail/python-dev/2016-September/146350.html to suggest adding "ordered mapping" to the glossary instead. I took a quick look at https://docs.python.org/3.6/glossary.html and don't see it there.