Because I'm pretty sure that it's possible to use mutable objects as keys in general. The users just have to observe restrictions: like don't insert the keys into the dictionary and then mutate them while they are in the dictionary and expect the dictionary to still work fine.

(Objects can also be used as keys even if they are mutated while in the dictionary, if identity-based equality is used for the dictionary; i.e. two keys are equal if they are acually one and the same object, and not just two similar objects.)

(0) Object identities are used as keys? (e.g., two different list objects that contain the elements 1,2,3 are treated as different keys)

(1) Catastr... I mean, hilarious things happen if you mutate an object that's being used as a key?

Anyway, both languages use value-based hashing for dictionaries. I am not a Rubyist, but I guess you are just expected to not mutate the keys? Ruby's dictionary implementation also has a rehash method to deal with this case [1], if for some reason you are purposely mutating the keys I suppose...

[1] http://docs.ruby-lang.org/en/2.0.0/Hash.html#method-i-rehash

Ruby, since you said it allows mutable keys in dictionaries.

> Anyway, both languages use value-based hashing for dictionaries.

Neither Python nor Ruby has compound values. Object identities are primitive values.

> but I guess you are just expected to not mutate the keys?

I guess C programmers are expected not to use memory after they free it.

What does this gain you over just doing tuple(obj) (or the equivalent--tuple(d.items()) for a dictionary, for example) when you want to make it immutable for use as a dict key?

Which only makes sense if the underlying mutable object is mutated. But if the underlying mutable object is mutated, the adaptor instance, if it is immutable, can no longer have the same value as the underlying mutable object. So the "adaptor" is no longer an adaptor; it's just a separate immutable object with the value that the mutable object had originally. I.e., it's just the same as tuple(d.items()) or whatever.

If by "copy-on-write" you just mean that two different containers that both store the same immutable value, say a string, can both point to the same memory storing that value, and the mutable container's pointer only changes if a new value is stored at that key/index, Python already does that; for example, tuple(d.items()) does not create new storage for the items themselves, it points the tuple to the same objects that are contained in the dict at the time of the call to d.items().

> It can have more compact storage if the runtime is smart.

A tuple in Python does have more compact storage than a list, dict, or set.

> It can continue to efficiently support lookup

Same issue as above; this only matters if the underlying object is mutated, in which case an immutable "adaptor" can no longer have the same value, so lookup on the adaptor isn't the same as lookup on the underlying mutable object. Lookup on the adaptor is just lookup on the immutable value, which is easily made efficient.

    >>> (1,2,3)[2]=5
    Traceback (most recent call last):
      File "<stdin>", line 1, in <module>
    TypeError: 'tuple' object does not support item assignment

  >>> x = (1, 2, [3])
  >>> x
  (1, 2, [3])
  >>> x[2].append(4)
  >>> x
  (1, 2, [3, 4])

  import ctypes

  def tuple_setitem(t, index, item):
      obj = ctypes.py_object(t)
      item = ctypes.py_object(item)
      ref_count = ctypes.c_long.from_address(id(t))
      original_count = ref_count.value
      if original_count != 1:
          ref_count.value = 1
      ctypes.pythonapi.Py_IncRef(item)
      ctypes.pythonapi.PyTuple_SetItem(obj, ctypes.c_ssize_t(index), item)
      ref_count.value = original_count

  >>> x = (1, 2, 3,)
  >>> tuple_setitem(x, 1, "foo")
  >>> x
  (1, "foo", 3)

What you did was modify the underlying list, the tuple itself is immutable.

If it has mutable items in it, yes. But in that case, the tuple can't be used as a dictionary key; Python checks, not just that the tuple itself is immutable, but that every object in it is immutable.

Can (1, 2, [3]) be used in a hash table, and what if the [3] is mutated to [3, 4]?