Deep-equality keys

[michaelhkay]

Issue #119 proposes extending maps to allow arbitrary values as keys. This is very difficult to achieve, (a) because the fact that keys are atomic items is deeply embedded in the design of a number of functions and operations on maps, and (b) because it's very hard to define an equality function that suits everyone.

The way we tacked variable equality semantics for strings was via the collation-key() function, which takes a string and a collation as input and produces an opaque key value, which can be used as a key in maps, and which reflects the desired equality semantics.

We could extend the same idea to values other than strings. In particular, we could define a deep-equality-key() that can be calculated for any sequence, and that takes all the matching options of the deep-equal() function as a parameter. (We could then redefine deep-equal(a, b, options) to mean deep-equality-key(a, options) eq deep-equality-key(b, options)).

The main drawback is that the deep-equality-keys for large node trees or maps would be rather long strings. People might use the functionality without realising the expense.

Another problem is that one of our options in deep-equals() is a callback function for item equality, and we couldn't replicate this when computing a key. But this callback is the only way we have, for example, to compare nodes by identity rather than by content.

Note that an internal deep-equality-key concept (or at least a deep-equality hashcode) is needed anyway for efficient implementation of deep-equals where order is deemed irrelevant. Without it, the function becomes O(n^2). Quite independently of this proposal, we should perhaps have an explicit option on deep-equals() to compare nodes by identity.

[MarkNicholls]

you don't seem to have any takers, unfortunately I'm too ignorant to understand the question, if you need someone to "talk at", and ask dumb questions, feel free to explain more. My presumption is that a collation key is some sort of partial order? that indicates what are equal/greater/less than (or some sort of mapping into a total order). I'm not sure how that extends to sequences(?) as keys.

[michaelhkay]

Dropping this for lack of interest.