Как упражнение, и в основном для моего собственного развлечения, я реализую парсер партера backtracking packrat. Воодушевлением для этого является то, что я хотел бы получить лучшее представление о том, как гигенные макросы будут работать на языке, подобном algol (как показано на диалектах без диалогов lisp, которые вы обычно находите в них). Из-за этого различные проходы через вход могут видеть разные грамматики, поэтому результаты кэшированного анализа недействительны, если я также не сохраняю текущую версию грамматики вместе с результатами кеширования синтаксического анализа. (EDIT: следствие этого использования коллекций с ключевыми значениями состоит в том, что они должны быть неизменными, но я не намерен выставлять интерфейс, чтобы они могли быть изменены, так что изменяемые или неизменяемые коллекции прекрасны)
Проблема в том, что 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'}
Ok. Но я должен сделать класс для каждой возможной комбинации ключей в правиле, которое я бы хотел использовать, что не так уж плохо, потому что каждое правило синтаксического анализа точно знает, какие параметры он использует, так что класс может быть определен одновременно как функция, которая анализирует правило.
Изменить: дополнительная проблема с namedtuple заключается в том, что они строго позиционные. Два кортежа, которые выглядят так, как будто они должны быть разными, на самом деле могут быть одинаковыми:
>>> 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?
Немного взломав ответы, вот более полное решение, которое я использую. Обратите внимание, что это делает немного дополнительную работу, чтобы сделать полученные dicts неопределенно неизменными для практических целей. Конечно, все равно довольно легко взломать его, позвонив 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/info/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 ok to mutate it
def __add__(self, right):
result = hashdict(self)
dict.update(result, right)
return result
if __name__ == "__main__":
import doctest
doctest.testmod()
