Hacker News Reader

Comment by np_tedious | Hacker News Reader

> can't even use a dict as a dict key

Curious, is this actually something you want to do often? While there is no hashable+immutable frozendict ala frozenset, you could throw one together or even define a hash function on a subclass and "swim at your own risk" not to mutate it later.

I've encountered this enough with lists and the obvious solution is to cast them to tuples. Can't say I've found the same with dicts tho.

As for the comparison with lisp - in most lisps this is a non issue because nearly all structures are immutable

View on HN

Absolutely. For me it is a 50-50 chance whether I have data in a dict that needs to be mapped to something or have data in a list/tuple that needs mapping.

Many major programming languages undersell how natural key-value data structures are; usually by providing unwieldy mapping data types. Clojure has spoiled me.

> you could throw one together

Yeah, I do. Most Python programmers wouldn't see a need for that, but that can be attributed to Python not having the capability by default and so they've just internalised not to use dict for anything that needs to be a key. World's mildest form of learned helplessness, I suppose.

> Most Python programmers wouldn't see a need for that, but that can be attributed to Python not having the capability by default and so they've just internalised not to use dict for anything that needs to be a key.

You're being extremely uncharitable here.

To a Python programmer "using a dict as a key" is a nonsensical idea for the same reason "using a list as a key" is — both dicts and lists are mutable. Python programmers don't think of dicts or lists as synonymous with their content.

I'm assuming you don't want to literally use a dict as a key, you want to use the keys and values contained in a dict as a key. Nothing stops you. You just have to say it:

    point = dict(x=4, y=5, z=1)
    point_reviews = dict()
    point_reviews[tuple(point.items())] = "A+++ great coord would point to again"

You might wonder why you can't just use dicts directly. Again, dicts are mutable. What happens if you write:

    point = dict(x=0, y=9001)
    point_reviews = dict()
    point_reviews[point] = "Love how it's over 9000 here!"
    point["y"] = 8999
    result = point_reviews[dict(x=0, y=8999)]  # Is this a KeyError or not?

More detail on this issue is explained here: https://wiki.python.org/moin/DictionaryKeys

In the simplest case where you have a predefined list of keys, I'd suggest using a namedtuple instead of a dict. If you need to treat a dict's content as hashable but can't enumerate the keys, `tuple(d.items())` is probably the best choice in recent Python versions. Be aware though that in older Pythons you can't rely on stable sort order of dictionary items, so you have to use something like `frozenset(d.items())`.

Good information, and well put. A small quibble: you should probably almost never use tuple(), even on recent Python:

    >>> tuple(dict(a=1, b=2).items())
    (('a', 1), ('b', 2))
    >>> tuple(dict(b=2, a=1).items())
    (('b', 2), ('a', 1))

Of course, if you can absolutely guarantee how the dictionary has been constructed, it is possible. No rules are absolute. But in my experience, frozenset() is probably better:

    >>> frozenset(dict(a=1, b=2).items())
    frozenset({('b', 2), ('a', 1)})
    >>> frozenset(dict(b=2, a=1).items())
    frozenset({('b', 2), ('a', 1)})

(Or sometimes even id(), as, if you are confident enough that the dictionary is identical, that might be because it came from the same place. If you are building a reverse dictionary, say, or a cache of indices. Though obviously that it is much more situationally dependent.)

Well. Now that dictionaries remember their order in newer Python versions, there is a case to be made that dict(a=1, b=2) is not the same dictionary as dict(b=2, a1). So they should be different dict keys, if they could be dict keys.

    dict(a=1,b=2) == dict(b=2,a=1)

is True (on 3.7.3). I'm not too keen on introducing a third type of equality on the same type, even if it makes some theoretical sense.

And worse, the dict's values may themselves be mutable. So even tuple(point.items()) is not a sensible dict key in the general case.

id(dictionary) is the key you want: immutable, reliable, cheap.

That value will not change when the contents of the dict are updated. You’re keying on the dict itself rather than the hashed contents. That’s what you want in some situations, but it’s not what the parent post is looking for.

It's also not reliable, since the same address can be reused if the dict is GCed. This is actually really easy to induce in Python, since it uses immediate refcounting. In my REPL (3.7.3):

    >>> a = {}
    >>> x = id(a)
    >>> del a
    >>> a = {}
    >>> y = id(a)
    >>> x == y
    True

Several times, when working with Lua, I’ve made what I call “Janus tables”.

Give them a string, they return a table or function. Give them the table or function, they return a string.

It’s a useful technique that you can only apply if your hashmap can map anything to anything.

What's a use case for needing to be able to do this?

https://en.wikipedia.org/wiki/Bidirectional_map

Any hashmap will have problems with storing mutable objects, where the hash value itself can change after the object has been stored, causing some very unwanted paradoxes.

And that is the problem with Python dicts as keys.

I don't think mutability is a concern if your goal is to get a bidi map between strings and (mutable) _instances_; i.e. if you just want to use the reference to the dict itself as the hash rather than the contents of the dict itself.

Yeah, I don't actually know if Python computes hashes for dicts by content or "identity".

I just assumed it was the former, based on the fact that dicts are disallowed as keys.

It’s been a while, but I’m pretty sure the reason why a dictionary can’t have a dictionary as it’s key is because the dictionary class doesn’t implement the __hash__ method that would compute the hashcode.

This is definitely the proximate reason.

The reason for that choice is because the object is mutable.

Sure, but as others have mentioned, you can make your own choice by subclassing dict and defining your own hash function, as long as that function is defined in a way that follows the appropriate rules.

Not often, but when you do want to do it, it’s frustrating (and unusual for Python) that the natural and obvious way doesn’t work.

When I read this my first thought was "you should use a FrozenDict", but looking into it, it seems that it doesn't exist; I assumed so because of FrozenSets (hashable sets).

You can still create a hashable key from a dict with FrozenSet(mydict.items()).

Ah nice. Yes that last suggestion is probably a more simple and elegant approach than anything I'd mentioned / thought about

You don't really need a FrozenSet if you're already willing to iterate over this dictionary. You can just use a tuple, which is also hashable.

tuple(d.items())

That depends on the order in which the values are are returned by items(), which you likely do not want.

    >>> tuple({1:2,3:4}.items()) == tuple({3:4,1:2}.items())
    False
    >>> frozenset({1:2,3:4}.items()) == frozenset({3:4,1:2}.items())
    True

Good point

What Lisps are you thinking of? In Common Lisp, Scheme, and Emacs Lisp, at least (IIRC), all composite data structures (strings, vectors, etc) are mutable, or can be. The only Lisp I can think of in which "nearly all structures are immutable" is Clojure.

Python probably has a set type, but a common general use case for use an associative array as a key is when making a set.

dict = { "foo" : "bar" }

set = { dict : true }

set.has_key?(dict) # true

I'm sure there are other use cases where dict keys can be convenient.

Yes, Python has both a set type and the immutable "frozenset" type, that can be used as a dictionary key.

someset = {"one", "two", "three"}

"one" in someset # true

frozen = frozenset(someset)

somedict = {frozen: "example"}

frozen in somedict # true somedict[frozen] # "example"

> Can't say I've found the same with dicts tho

I would think a NamedTuple would do the trick? (https://docs.python.org/3/library/collections.html#collectio...)

Reply on news.ycombinator.com