classification
Title: collections.abc.OrderedMapping
Type: enhancement Stage:
Components: Library (Lib) Versions:
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: abarnert, brett.cannon, jab, rhettinger, vstinner
Priority: normal Keywords: patch

Created on 2016-12-08 23:00 by jab, last changed 2016-12-21 16:23 by jab. This issue is now closed.

Files
File name Uploaded Description Edit
jab-orderedmapping-1.patch jab, 2016-12-08 23:00 review
jab-orderedmapping-2.patch jab, 2016-12-08 23:34 review
Messages (7)
msg282742 - (view) Author: Joshua Bronson (jab) * Date: 2016-12-08 23:00
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
msg282744 - (view) Author: Joshua Bronson (jab) * Date: 2016-12-08 23:34
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``.
msg282761 - (view) Author: Joshua Bronson (jab) * Date: 2016-12-09 05:18
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?
msg282763 - (view) Author: Joshua Bronson (jab) * Date: 2016-12-09 05:33
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.
msg282892 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-12-11 00:55
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.
msg282895 - (view) Author: Joshua Bronson (jab) * Date: 2016-12-11 02:42
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.
msg283766 - (view) Author: Joshua Bronson (jab) * Date: 2016-12-21 16:23
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.
History
Date User Action Args
2016-12-21 16:23:27jabsetnosy: + brett.cannon, vstinner
messages: + msg283766
2016-12-11 02:42:36jabsetnosy: + abarnert
messages: + msg282895
2016-12-11 00:55:59rhettingersetstatus: open -> closed
resolution: rejected
messages: + msg282892
2016-12-10 01:40:23rhettingersetassignee: rhettinger
2016-12-09 15:36:53gvanrossumsetnosy: - gvanrossum
2016-12-09 05:33:44jabsetmessages: + msg282763
2016-12-09 05:18:30jabsetmessages: + msg282761
2016-12-08 23:34:00jabsetfiles: + jab-orderedmapping-2.patch

messages: + msg282744
2016-12-08 23:00:34jabcreate