PEP 603: Adding a frozenmap type to collections

[ncoghlan (Alyssa Coghlan)]

@alicederyn

I think you’d still need to hash each underlying map anyway just to check they were immutable? So this would be very expensive.

First hash would be expensive (as you say, in addition to calculating hash(frozenset(d.items())), each underlying map also needs to be hashed to confirm it is immutable), but since a successful hash calculation indicates everything is immutable it would be OK to cache the result, making it O(1) after that. (the hash storage field would be excluded from both hashing and equality checks, so it can still be lazily calculated and stored as PEP 416 suggested for frozendict)

I don’t actually have a concrete use case, though (it was just an idle thought), so it might be better left out. The question just never came up before, since there weren’t any hashable mappings to be chained in the first place.

[ncoghlan (Alyssa Coghlan)]

@Gouvernathor

I also noticed something : that PEP 416, which has not been mentioned here for a long time. If the resubmitted PEP just takes on frozendict and leaves the HAMT behind, then it’s just a reopening of 416 with slightly new arguments - and a new perspective on the persisting need for a frozendict after MappingProxyType’s integration.

The article at The case for immutable dictionaries; and the central misunderstanding of PEP 351 (linked earlier in the thread at its original, now 404, home) is genuinely interesting.

One valid point that it makes is that stronger static type analysis capabilities make explicit assertions about data structure immutability more beneficial. This is something worth bringing up in a revived proposal (even PEP 416 predates PEP 484 by a few years).

[MegaIng (Cornelius Krupp)]

@ncoghlan

Tangential thought prompted by the above notes: PEP 603 should include making ChainMap hashable if all of the included mappings are hashable.

Nope, not possible, .maps is documented as a public, mutable list, meaning the ChainMap type can be mutable even if all mappings are not. This would require a new type, FrozenChainMap, but I’m my understanding that fills (almost) the same niche has HAMT? So I don’t think that’s worth aiming for.

[Nineteendo (Nice Zombies)]

@ncoghlan

Hence the suggestion of just naming it after the initial implementation technique, with a name like collections.frozenhamt or collections.FrozenHAMT.

A perfect example of this is “Segmentation fault”. We now use paging instead of segmentation, but the name wasn’t changed to “Paging fault”. So, I think this is fine.

[ncoghlan (Alyssa Coghlan)]

@MegaIng

Nope, not possible, .maps is documented as a public, mutable list, meaning the ChainMap type can be mutable even if all mappings are not.

Ah, I had completely forgotten about that. You’re right, not worth worrying about in that case.

[Gouvernathor]

@Gouvernathor

I also noticed something : that PEP 416, which has not been mentioned here for a long time. If the resubmitted PEP just takes on frozendict and leaves the HAMT behind, then it’s just a reopening of 416 with slightly new arguments - and a new perspective on the persisting need for a frozendict after MappingProxyType’s integration.
I wrote a draft for that, with just the required edits to make 416 up-to-date, but I don’t want to post it too early and steal Yury’s initiative.

Hi, considering that some time has passed without a new PEP draft being introduced, here is the draft I mentioned there.

I named it PEP 416-1, but I’m sure that won’t last (maybe it will be the new 416, or the new 603 but it would be weird, or a new number entirely). So I’m not sure whether we should continue discussing this here, open a new thread or whatever else.

Feel free to give some feedback !

[Jelle (Jelle Zijlstra)]

@Gouvernathor

maybe it will be the new 416, or the new 603 but it would be weird, or a new number entirely).

PEP editor opinion: This should almost certainly be a new PEP, or possibly a rewrite of PEP 603 if the author of that PEP agrees to it. PEP 416 is ancient history and should not be changed.

[willofferfit (Will)]

This is what I currently use due to the missing feature:

from collections.abc import Hashable


type frozendict[K: Hashable, V: Hashable] = frozenset[tuple[K, V]]


def freeze_dict[K: Hashable, V: Hashable](d: dict[K, V]) -> frozendict[K, V]:
    return frozenset(d.items())


def unfreeze_dict[K: Hashable, V: Hashable](fd: frozendict[K, V]) -> dict[K, V]:
    d = dict(fd)
    assert len(d) == len(fd)
    return d


d = {1: 2, 3: 4}
fd = freeze_dict(d)
assert repr(d) == repr(unfreeze_dict(fd))
hash(fd)  # works

For my use case (core algorithm that is part of a complex AI system), these were my requirements, from high to low priority:

1. Must be hashable and immutable
2. Must work for type annotations
3. Must be intuitive to use and understand, like dicts
4. Must have at least the same restrictions that dicts have (e.g. disallowing duplicate keys)
5. Must have a simple implementation and not be overengineered, to prevent bugs
6. Must easily support future Python versions
7. Where they’re used, must not be significantly slower than dicts

With these requirements, frozendict can be used in data structures that require hashable objects, and developer experience is as good as it can get. It would be great to have better time complexity, actual dict semantics, and a function like frozenset().

Over the years, I’ve often found myself needing to reimplement something like this. It’s time that we add frozendict to Python.