<div dir="ltr">You know, I can think up several use cases for the case-insensitive idea.<div><br></div><div>Not sure if I missed something, but there should be a function to retrieve the original key from the modified. i.e.:</div>
<div><br></div><div>>>> mydict['SomeStr'] = 5</div><div>>>> mydict.get_key('somestr')</div><div>'SomeStr'</div><div>>>> </div></div><div class="gmail_extra"><br><br><div class="gmail_quote">
On Fri, Sep 13, 2013 at 1:40 PM, Antoine Pitrou <span dir="ltr"><<a href="mailto:solipsis@pitrou.net" target="_blank">solipsis@pitrou.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Hello,<br>
<br>
Following the python-dev discussion, I've written a PEP to recap the<br>
proposal and the various arguments. It's inlined below, and it will<br>
probably appear soon at <a href="http://www.python.org/dev/peps/pep-0455/" target="_blank">http://www.python.org/dev/peps/pep-0455/</a>, too.<br>
<br>
Regards<br>
<br>
Antoine.<br>
<br>
<br>
PEP: 455<br>
Title: Adding a key-transforming dictionary to collections<br>
Version: $Revision$<br>
Last-Modified: $Date$<br>
Author: Antoine Pitrou <<a href="mailto:solipsis@pitrou.net">solipsis@pitrou.net</a>><br>
Status: Draft<br>
Type: Standards Track<br>
Content-Type: text/x-rst<br>
Created: 13-Sep-2013<br>
Python-Version: 3.4<br>
Post-History:<br>
<br>
<br>
Abstract<br>
========<br>
<br>
This PEP proposes a new data structure for the ``collections`` module,<br>
called "TransformDict" in this PEP. This structure is a mutable mapping<br>
which transforms the key using a given function when doing a lookup, but<br>
retains the original key when reading.<br>
<br>
<br>
Rationale<br>
=========<br>
<br>
Numerous specialized versions of this pattern exist. The most common<br>
is a case-insensitive case-preserving dict, i.e. a dict-like container<br>
which matches keys in a case-insensitive fashion but retains the<br>
original casing. It is a very common need in network programming, as<br>
many protocols feature some arrays of "key / value" properties in their<br>
messages, where the keys are textual strings whose casing isn't<br>
relevant.<br>
<br>
Another common request is an identity dict, where keys are matched<br>
according to their respective id()s instead of normal matching.<br>
<br>
Both are instances of a more general pattern, where a given<br>
transformation function is applied to keys when looking them up: that<br>
function being ``str.lower`` in the former example and the built-in<br>
``id`` function in the latter.<br>
<br>
(it can be said that the pattern *projects* keys from the user-visible<br>
set onto the internal lookup set, hence this PEP's title)<br>
<br>
<br>
Semantics<br>
=========<br>
<br>
TransformDict is a ``MutableMapping`` implementation: it faithfully<br>
implements the well-known API of mutable mappings, as ``dict`` itself<br>
and other dict-like classes in the standard library. Therefore, this<br>
PEP won't rehash the semantics of most TransformDict methods.<br>
<br>
The transformation function needn't be bijective, it can be strictly<br>
surjective as in the case-insensitive example::<br>
<br>
>>> d = TransformDict(str.lower)<br>
>>> d['SomeKey'] = 5<br>
>>> d['somekey']<br>
5<br>
>>> d['SOMEKEY']<br>
5<br>
<br>
TransformDict retains the first key used when creating an entry::<br>
<br>
>>> d = TransformDict(str.lower)<br>
>>> d['SomeKey'] = 1<br>
>>> d['somekey'] = 2<br>
>>> list(d.items())<br>
[('SomeKey', 2)]<br>
<br>
The original keys needn't be hashable, as long as the transformation<br>
function returns a hashable one::<br>
<br>
>>> d = TransformDict(id)<br>
>>> l = [None]<br>
>>> d[l] = 5<br>
>>> l in d<br>
True<br>
<br>
Constructor<br>
-----------<br>
<br>
As shown in the example aboves, creating a TransformDict requires<br>
passing the key transformation function as the first argument (much<br>
like creating a ``defaultdict`` requires passing the factory function<br>
as first argument).<br>
<br>
The constructor also takes other optional arguments which can be used<br>
to initialize the TransformDict with certain key-value pairs. Those<br>
optional arguments are the same as in the ``dict`` and ``defaultdict``<br>
constructors::<br>
<br>
>>> d = TransformDict(str.lower, [('Foo': 1)], Bar=2)<br>
>>> sorted(d.items())<br>
[('Bar', 2), ('Foo', 1)]<br>
<br>
<br>
Alternative proposals and questions<br>
===================================<br>
<br>
Retaining the last original key<br>
-------------------------------<br>
<br>
Most python-dev respondents found retaining the first user-supplied key<br>
more intuitive than retaining the last. Also, it matches the dict<br>
object's own behaviour when using different but equal keys::<br>
<br>
>>> d = {}<br>
>>> d[1] = 'hello'<br>
>>> d[1.0] = 'world'<br>
>>> d<br>
{1: 'world'}<br>
<br>
Furthermore, explicitly retaining the last key in a first-key-retaining<br>
scheme is still possible using the following approach::<br>
<br>
d.pop(key, None)<br>
d[key] = value<br>
<br>
while the converse (retaining the first key in a last-key-retaining<br>
scheme) doesn't look possible without rewriting part of the container's<br>
code.<br>
<br>
Using an encoder / decoder pair<br>
-------------------------------<br>
<br>
Using a function pair isn't necessary, since the original key is<br>
retained by the container. Moreover, an encoder / decoder pair would<br>
require the transformation to be bijective, which prevents important<br>
use cases like case-insensitive matching.<br>
<br>
Providing a transformation function for values<br>
----------------------------------------------<br>
<br>
Dictionary values are not used for lookup, their semantics are totally<br>
irrelevant to the container's operation. Therefore, there is no point<br>
in having both an "original" and a "transformed" value: the transformed<br>
value wouldn't be used for anything.<br>
<br>
Providing a specialized container, not generic<br>
----------------------------------------------<br>
<br>
It was asked why we would provide the generic TransformDict construct<br>
rather than a specialized case-insensitive dict variant. The answer<br>
is that it's nearly as cheap (code-wise and performance-wise) to provide<br>
the generic construct, and it can fill more use cases.<br>
<br>
<br>
Implementation<br>
==============<br>
<br>
A patch for the collections module is tracked on the bug tracker at<br>
<a href="http://bugs.python.org/issue18986" target="_blank">http://bugs.python.org/issue18986</a>.<br>
<br>
<br>
Existing work<br>
=============<br>
<br>
Case-insensitive dicts are a popular request:<br>
<br>
*<br>
<a href="http://twistedmatrix.com/documents/current/api/twisted.python.util.InsensitiveDict.html" target="_blank">http://twistedmatrix.com/documents/current/api/twisted.python.util.InsensitiveDict.html</a><br>
* <a href="https://mail.python.org/pipermail/python-list/2013-May/647243.html" target="_blank">https://mail.python.org/pipermail/python-list/2013-May/647243.html</a><br>
* <a href="https://mail.python.org/pipermail/python-list/2005-April/296208.html" target="_blank">https://mail.python.org/pipermail/python-list/2005-April/296208.html</a><br>
* <a href="https://mail.python.org/pipermail/python-list/2004-June/241748.html" target="_blank">https://mail.python.org/pipermail/python-list/2004-June/241748.html</a><br>
* <a href="http://bugs.python.org/msg197376" target="_blank">http://bugs.python.org/msg197376</a><br>
* <a href="http://stackoverflow.com/a/2082169" target="_blank">http://stackoverflow.com/a/2082169</a><br>
* <a href="http://stackoverflow.com/a/3296782" target="_blank">http://stackoverflow.com/a/3296782</a><br>
* <a href="http://code.activestate.com/recipes/66315-case-insensitive-dictionary/" target="_blank">http://code.activestate.com/recipes/66315-case-insensitive-dictionary/</a><br>
* <a href="https://gist.github.com/babakness/3901174" target="_blank">https://gist.github.com/babakness/3901174</a><br>
* <a href="http://www.wikier.org/blog/key-insensitive-dictionary-in-python" target="_blank">http://www.wikier.org/blog/key-insensitive-dictionary-in-python</a><br>
* <a href="http://en.sharejs.com/python/14534" target="_blank">http://en.sharejs.com/python/14534</a><br>
* <a href="http://www.voidspace.org.uk/python/archive.shtml#caseless" target="_blank">http://www.voidspace.org.uk/python/archive.shtml#caseless</a><br>
<br>
Identity dicts have been requested too:<br>
<br>
* <a href="https://mail.python.org/pipermail/python-ideas/2010-May/007235.html" target="_blank">https://mail.python.org/pipermail/python-ideas/2010-May/007235.html</a><br>
* <a href="http://www.gossamer-threads.com/lists/python/python/209527" target="_blank">http://www.gossamer-threads.com/lists/python/python/209527</a><br>
<br>
Python's own pickle module uses identity lookups for object<br>
memoization:<br>
<a href="http://hg.python.org/cpython/file/0e70bf1f32a3/Lib/pickle.py#l234" target="_blank">http://hg.python.org/cpython/file/0e70bf1f32a3/Lib/pickle.py#l234</a><br>
<br>
<br>
Copyright<br>
=========<br>
<br>
This document has been placed in the public domain.<br>
<br>
<br>
..<br>
Local Variables:<br>
mode: indented-text<br>
indent-tabs-mode: nil<br>
sentence-end-double-space: t<br>
fill-column: 70<br>
coding: utf-8<br>
End:<br>
<br>
<br>
_______________________________________________<br>
Python-Dev mailing list<br>
<a href="mailto:Python-Dev@python.org">Python-Dev@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/python-dev" target="_blank">https://mail.python.org/mailman/listinfo/python-dev</a><br>
Unsubscribe: <a href="https://mail.python.org/mailman/options/python-dev/rymg19%40gmail.com" target="_blank">https://mail.python.org/mailman/options/python-dev/rymg19%40gmail.com</a><br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br>Ryan
</div>