Ord instance for Data.Map?

[Isaac Dupree]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Johannes Waldmann wrote:
> Henning Thielemann wrote:
> The above (local  instance) could be modelled
> by handing the required Ord dictionary explicitely
> (or as an implicit parameter, which I would not recommend, though)
> 
> You can hand over the Ord dictionary when constructing a Set in Java:
> 
>> TreeSet(Comparator<? super E> comparator)
>> Constructs a new, empty tree set,
>> sorted according to the specified comparator.
> 
> So the Haskell collections could need a similar constructor?
> The difference to your work-around (Wrapper class for the elements
> of the collection) is that the constructor is called only once,
> but your wrapper clutters each and every access.

And then what do you do with (set1 `union` set2) where they have
different comparators?  C++ collections have that think-o, I don't know
about Java.... the problem being that the comparators are not statically
required to be "the same", just the same *type*, so, what do you do with
two different ones?  I suppose dependently-typed languages can directly
express the equivalence requirement without requiring it to be
statically determinable from the type system what the comparison
operator is going to be.  Compilers based on classes being functions
from types to methods (jhc...) can't use the alternate-dictionary thing.
 But you can always directly have the (key -> key -> Ordering) function
be part of your data structure for the same effect, and then you can see
all the problems involved (serialization, interactions and comparisons
between maps, etc.).

If you just don't want to wrap and unwrap your *keys* all the time,
perhaps you could have the statically checkable version:

class Comparer comp where
  type ComparedType comp --associated type, not yet implemented anywhere
  compare' :: ~comp -> (ComparedType comp) -> (ComparedType comp) ->
Ordering --the '~' means that that parameter must be unused (this is not
an implemented syntax) (the parameter is only there to select which
instance is being used, since you can't pass a type directly as an
argument without an associated "value", in Haskell; rather, (undefined
:: TheCorrectType) is passed)
data NewMap comp k v = ...the same as Data.Map
 -- most operations on NewMap require the context (Comparer comp)

data OrdComparer k  --a "phantom" (data-)type with no constructors
instance (Ord k) => Comparer (OrdComparer k) where
  type ComparedType (OrdComparer k) = k
  compare' = Prelude.compare
type Map k = NewMap (OrdComparer k) k
 -- most operations on Map require the context (Ord k), which is a
simplification of the required context (Comparer (OrdComparer k))



Isaac

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGJniXHgcxvIWYTTURAhNYAJ4+SWf6DO/gC0nLngopykIySKguQACfafdk
kiD505V+pr2n2+BsOZS47Uo=
=HTQ2
-----END PGP SIGNATURE-----