Who needs Ord for Sets and Maps anyway?

[Jean-Philippe Bernardy]

On 1/19/06, Johannes Waldmann <waldmann at imn.htwk-leipzig.de> wrote:

> The union of two ordered sets with different specifactions
> for their (externally visible) structure (ordering) is not defined.
> Or rather, it is up to the user to specify explicitely what he wants
> (i. e. name the comparator for the result).
>
> Or do you mean that an implementation of "union" could be more efficient
> if both sets have the same internal representation (e. g. balanced
> tree). A Java implementation would probably use "instanceof"
> to check for that. With the current framework and Sun's implementation,
> the TreeSet implementation (Red-Black trees) does not have a specialiced
> implementation of "addAll", as far as I could see.
>
> The underlying question is: what should be the type of "union".
> Java: interface Collection<E> { addAll(Collection<? extends E> c) }
> naive Haskell: class Collection c where union :: c e -> c e -> c e
> The Java thing is existential: each implementation of addAll
> has to accept *any* collection as an argument,
> while the Haskell implementation knows that both arguments
> have identical representation.  So the Java version is more
> flexible for the user of the library. One could try
> class Collection c where union :: Collection d => c e -> d e -> c e
> and use a specialized implementation for  c e -> c e -> c e.

I see your point now. However, I suspect the homogeneous typing is
less surprising for the user. It is also much more inline with the
haskell style. See for example, Num class:
(+) :: a -> a -> a

> This works for arguments of functions,
> but what about a function that by design returns "any" collection,
> without telling the caller about the implementation.
> Then we sure have to wrap it up in an existential type?
> My point is that hiding the implementation is actually the recommended
> coding style (not just for Java) but it is syntactically inconvenient in
> Haskell. But perhaps I missed something.

Subtyping and binary methods is not something so obvious... And
certainly I do not want to emulate the java solution with existential
types :)

In any case, please don't confuse implementation hiding and
polymorphism. Those are mixed in most OO languages, and indeed in
java, but separated in haskell. For example, Data.Set is
"monomorphic", but still an abstract data type (one cannot observe the
internal structure, and indeed we are considering changing it)

Cheers,
JP.