Who needs Ord for Sets and Maps anyway?

[Johannes Waldmann]

Jean-Phillipe Bernardy wrote:

> What if we do the union of two Sets constructed with different comparators ?

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.

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.

Best regards,
-- 
-- Johannes Waldmann -- Tel/Fax (0341) 3076 6479/80 --
---- http://www.imn.htwk-leipzig.de/~waldmann/ -------