On Aug 1, 2008, at 6:18 AM, Johannes Waldmann wrote:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Aaron Denney wrote:
If you're going to make users write an equality function, making them write an ordering adds little effort, and a reasonable amount of gain. Usually.
Then why is there a distinction between e.g. Map and SortedMap (and Set and SortedSet) in the Java libraries?
Yes yes I know Haskell is not Java etc. but they must have given this some thought. (Of course them making everything an instance of Eq and Hash is a design error but that's not the point here.)
Au contraire, it's *exactly* the point! Java uses the hash code to implement collections that only require equality and hashing, but no ordering. Haskell, as a functional language, instead prefers equality and ordering---because trees admit efficient pure update, whereas hash tables generally do not. Two different languages, two different approaches to implementing collections---one more imperative, the other more functional. Of course, if one is simply looking for INefficient collections that require only (Eq a), this probably doesn't matter. But in that case it's hard to do much better than [(a,b)] and lookup (it's possible to do better, using e.g. unboxed tuple arrays and seekrit mutation, but probably only worth it for stuff that's big enough that we should have been using a proper map anyway). -Jan-Willem Maessen