jmaessen at alum.mit.edu
Fri Aug 1 08:19:58 EDT 2008
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).
More information about the Libraries