sorted-map with heterogeneous keys crashes on lookup

Question

Hello,
I encountered some odd behavior with sorted-map which to me looks like a bug or a lack of documentation:

Specifically, when creating a sorted map with keys of different types like so: (sorted-map :k1 :v1 "k2" :v2) then lookup like so (:k1 (sorted-map :k1 :v1 "k2" :v2)) produces the exception: Cannot compare k2 to :k1. This seems due to the use of compare in the sorted-map implementation.

While the preferable (to me) course of action would be to fully support heterogeneous keys, It seems reasonable to require that the keys of a sorted-map are comparable, but in my opinion this should be stated in the docs.

Even if that were to be a requirement, it seems more inline with Clojure's general design spirit to return nil upon such a lookup, rather than throw an exception. It would make more sense to me to throw an exception the moment that a key is added which is not comparable to other keys already in the map. What do you think?

Cheers,
Simon

Comments

Trying to throw an exception at the time of inserting the element would require scanning all of the existing elements in the map to verify that they are comparable with the element you are inserting, which would be terrible for performance and scalability. Similarly, catching the exception when you cause a comparison to happen and translating it to `nil` would add overhead that would be wasted on every correct use of the map. This is not the only case in Clojure where you need to understand the actual contracts of the data structures involved, and use them correctly or end up with unexpected results, in favor of performance. (Not to mention that special Clojure-oriented implementations of all the underlying Java classes would be required to add these features.)

In this case, the data structure involved is the Java `SortedMap` interface. Here is what is the second paragraph of the JavaDoc says:

All keys inserted into a sorted map must implement the `Comparable` interface (or be accepted by the specified comparator). Furthermore, all such keys must be mutually comparable: `k1.compareTo(k2)` (or `comparator.compare(k1, k2))` must not throw a `ClassCastException` for any keys `k1` and `k2` in the sorted map. Attempts to violate this restriction will cause the offending method or constructor invocation to throw a `ClassCastException`.

As you get deeper in JVM Clojure, you are inevitably going to need to learn details about the Java class libraries that it builds on and interoperates with. That said, a link to this JavaDoc and perhaps a summary/translation of it into Clojure terms could be useful in the Clojure doc string.

---

I can appreciate the very practical arguments that lead to the behavior being what it is, and respect them.

On the topic of developer experience and improving language adoption, especially as it pertains to clojurescript, I would reiterate the point that I mentioned in my reply to Alex: the existence of the “Comparable” JVM contract is quite obscure and hard to discover for somebody working primarily Clojurescript. I would suggest pointing to it from the sorted-map docs.


How much such a contract should be expected to be “intuitive” I think is very subjective to the background of each developer; as a different perspective: assuming that I can get out of a map every pair that I successfully put in seems entirely reasonable. Going one step further, even if one can intuit that an ordering among all keys must be possible in order to enable assoc and get on a sorted map, the fact that one is able to assoc keys of different types, in the absence of any further docs,  reinforces the (incorrect) belief that the default comparator is indeed able to provide an order between different types

---

And I want to be clear that I hear you and understand and empathize with the confusion and frustration! Trying to head it off in the documentation will hopefully help, but I’d still expect people to trip over things like this. I know I certainly have, and still do from time to time, despite having come from a Java background. It’s a huge challenge trying to build a consistent, excellent language that lives in a vast ecosystem with a history of its own and different philosophies.

---

> It’s a huge challenge trying to build a consistent, excellent language that lives in a vast ecosystem with a history of its own and different philosophies.

Couldn’t agree more, it’s often challenging even keeping consistency between two systems that one fully owns  The fact that the Clojure has managed to make a consistent language on top of two (or more) ecosystems with such a long legacy is a testament to the deep thinking that has gone into it, and I appreciate it

Answer 1

This is the expected behavior (matches Java's behavior when looking up a key in a map sorted by a comparator that doesn't handle the lookup key type).

Comments

Thanks for the quick answer!
As someone that approaches the Clojure ecosystem from Clojurescript, without much Clojure and even less Java background, this is really not intuitive (given that the rest of the language is otherwise designed logically and to minimize surprises).

Would you consider explaining this behavior in the sorted-map docs?

Something along the lines of "a `sorted-map` will let you `assoc` heterogeneous keys but won't allow lookup. This matches Java's behavior when looking up a key in a map sorted by a comparator that doesn't handle the lookup key type)"