On Fri, Aug 1, 2008 at 1:19 PM, Jan-Willem Maessen
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
You know, this isn't actually true. You can implement an immutable HashMap as newtype HashMap a b = HashMap (IntMap [(a, b)]) Where you basically store association lists of things with the same hash code as they values of the IntMap. This has fairly good merge and update properties, and performs quite reasonably. I haven't tried this with the Haskell implementations, but I've benchmarked my Scala implementation of the same idea and, while not as fast as a normal array based HashMap, it seems to be a significance performance improvement over the red black tree based maps I've compared it against and supports pretty comparable amounts of sharing.