Simple maps/sets: parameterize the comparator?
allen at wirfs-brock.com
Wed Dec 28 16:23:33 PST 2011
On Dec 27, 2011, at 10:20 AM, Mark S. Miller wrote:
> Hi Axel, yes, I would like to extend their constructor in this way. However, I'm not sure how to spec it -- help appreciated. The problem is that the comparator needs to provide both an equivalence operation and a corresponding hash operation. When these agree, all is well. What should we specify happens when passing in a misbehaving comparator? The dilemma is that
> 1) detecting misbehavior is expensive,
For sort comparison function we simply say that the behavior is undefined for a misbehaving comparison function. It isn't clear that this has cause any significant problems or that it is very likely that we will require detection of misbehaving sort comparison functions.
> 2) having a deterministic collection misbehavior in the face of comparator misbehavior seems hard, and
But it isn't clear that this is a requirement.
> 3) we'd like to avoid yet more under-specification. The similar under-specification of Array.prototype.sort is already bad enough.
But, I think that the key point here is that if we allow specification of an arbitrary comparator function then we must require that a corresponding hash function is also provided. That seems like a big step down a slippery slope.
We should probably avoid pressures for the build-ins to cover all possible use cases. In ES.next we will should have all the primitives necessary for JS programmers to define their own efficient collection objects, including various kinds of hash-tables. Hopefully some good libraries of such will get written.
More information about the es-discuss