[解決済み] Pythonのハッシュ化可能なディクショナリ

質問

練習として、そしてほとんど私自身の楽しみのために、私はバックトラックパクラットパーサーを実装しています。 このためのインスピレーションは、（あなたが通常それらを見つけるシンタックスフリーのLisp方言とは対照的に）アルゴル的な言語でハイジェニックマクロがどのように動作するかについてより良い考えを持ちたいことです。 このため、入力の異なるパスでは異なる文法が表示される可能性があり、キャッシュされた解析結果は、キャッシュされた解析結果と一緒に現在のバージョンの文法も保存しない限り、無効となります。 ( EDIT しかし、私はコレクションを変更できるようなインターフェイスを公開するつもりはないので、MutableコレクションでもImmutableコレクションでもかまいません。）

問題は、pythonのdictsは他のdictsのキーとして表示されないことです。 タプルを使っても(どうせやるのですが)役に立ちません。

>>> cache = {}
>>> rule = {"foo":"bar"}
>>> cache[(rule, "baz")] = "quux"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> 

ずっとタプルでなければならないのでしょう。 Pythonの標準ライブラリは、私が必要とするものをおおよそ提供してくれます。 collections.namedtuple は非常に異なった構文を持っていますが は がキーとして使われます。

>>> from collections import namedtuple
>>> Rule = namedtuple("Rule",rule.keys())
>>> cache[(Rule(**rule), "baz")] = "quux"
>>> cache
{(Rule(foo='bar'), 'baz'): 'quux'}

わかりました。 しかし、私は使いたいルールのキーの可能な組み合わせごとにクラスを作らなければなりません。これはそれほど悪いことではなく、それぞれのパースルールは使用するパラメータを正確に知っているので、そのクラスはルールをパースする関数と同時に定義することができるのです。

編集：追加の問題点として namedtuple のもう一つの問題は、それらが厳密に位置決めされていることです。 異なるように見える 2 つのタプルは、実際には同じである可能性があります。

>>> you = namedtuple("foo",["bar","baz"])
>>> me = namedtuple("foo",["bar","quux"])
>>> you(bar=1,baz=2) == me(bar=1,quux=2)
True
>>> bob = namedtuple("foo",["baz","bar"])
>>> you(bar=1,baz=2) == bob(bar=1,baz=2)
False

tl'dr: どうすれば dict のキーとして使用することができます。 dict s?

答えに少し手を加えて、私が使っているより完全な解決策は以下の通りです。 これは、実用的な目的のために、結果のディクストを曖昧に不変にするために少し余分な作業を行うことに注意してください。 もちろん、この問題を回避するために dict.__setitem__(instance, key, value) を呼び出すことでハックするのは簡単ですが、私たちは皆大人なのです。

class hashdict(dict):
    """
    hashable dict implementation, suitable for use as a key into
    other dicts.

        >>> h1 = hashdict({"apples": 1, "bananas":2})
        >>> h2 = hashdict({"bananas": 3, "mangoes": 5})
        >>> h1+h2
        hashdict(apples=1, bananas=3, mangoes=5)
        >>> d1 = {}
        >>> d1[h1] = "salad"
        >>> d1[h1]
        'salad'
        >>> d1[h2]
        Traceback (most recent call last):
        ...
        KeyError: hashdict(bananas=3, mangoes=5)

    based on answers from
       http://stackoverflow.com/questions/1151658/python-hashable-dicts

    """
    def __key(self):
        return tuple(sorted(self.items()))
    def __repr__(self):
        return "{0}({1})".format(self.__class__.__name__,
            ", ".join("{0}={1}".format(
                    str(i[0]),repr(i[1])) for i in self.__key()))

    def __hash__(self):
        return hash(self.__key())
    def __setitem__(self, key, value):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def __delitem__(self, key):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def clear(self):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def pop(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def popitem(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def setdefault(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    def update(self, *args, **kwargs):
        raise TypeError("{0} does not support item assignment"
                         .format(self.__class__.__name__))
    # update is not ok because it mutates the object
    # __add__ is ok because it creates a new object
    # while the new object is under construction, it's ok to mutate it
    def __add__(self, right):
        result = hashdict(self)
        dict.update(result, right)
        return result

if __name__ == "__main__":
    import doctest
    doctest.testmod()

どのように解決するのですか？

ここでは、ハッシュ化可能な辞書を作る簡単な方法を紹介します。ただ、明らかな理由により、他の辞書に埋め込んだ後、それらを変異させないことを忘れないでください。

class hashabledict(dict):
    def __hash__(self):
        return hash(tuple(sorted(self.items())))