[Haskell-cafe] Fwd: Increasing Haskell modularity

[Dominique Devriese]

Daniel,

This is an interesting discussion and I personally also think Haskell
should in time move away from global uniqueness of instances, at least
as the default.

2014-10-02 10:50 GMT+02:00 Daniel Trstenjak <daniel.trstenjak at gmail.com>:
> On Thu, Oct 02, 2014 at 12:44:25AM +0300, Gesh wrote:
>> Correct, although that's not what I said. I just said that a case could
>> be made for saying the design of programs around global uniqueness was
>> poorly thought out.
>
> I think the problem is, that for some type classes global uniqueness is
> a very good idea and for some it might not be that relevant.
>
> If there's e.g. a PrettyPrint type class, then one might argue, that
> it's a good idea to be able to change the pretty printing of a data type
> depending on the context.
>
> But for a type class represeting the equality of a data type it might be
> more harmful then good, to be able to change it.

I think you're right that whether we want global uniqueness of
instances depends on the situation. However, it doesn't just depend on
the type class in question.

Consider for example the Ord type class.  The fact that we sometimes
want to use different orderings for the same data types is clearly
evidenced by the existence of functions such as sortBy and all of the
"comparing ..." stuff in Data.Ord. On the other hand, there is the
fact that data types like Set crucially depend on being used with a
single Ord instance for correctness.

As you suggest, a way to deal with this could be to make a data type
like Data.Set carry around the Ord instance, something like this:

    data Set a where SomeInternalConstructor :: Ord a => ...
    insert :: a -> Set a -> Set a

However, it seems a bit unfortunate to me that this extra data (the
type class dictionary) would be carried around at runtime instead of
it being inferred and potentially compiled out at compile time.

I wonder if a more static alternative could be to introduce some
limited form of dependent types (I'm reminded of Scala's
value-dependent types) to index the Data.Set data type with the Ord
instance that it should be used with, something like:

   data Set a (instOrdA :: Ord a) where ...
   insert :: (ordA :: Ord a, ordA ~v instOrdA) => a -> Set a instOrdA
-> Set a instOrdA

In such code, the constraint "ordA ~v instOrdA" would require that the
two instances are equal in some intentional and decidably checkable
way (i.e. no automatic unfolding of recursive definitions and such).
Perhaps it's not even needed to require the "(ordA :: Ord a, ordA ~v
instOrdA) =>" contraint, but the compiler could somehow just take the
instance from the "Set a instOrdA" type and make it available for type
class resolution in the body of insert?

Anyway, I agree with Gesh that at some point, Haskell should deprecate
global uniqueness of type class instances, but we should first explore
alternatives for modeling data types like Set that currently depend on
it.  There's still quite some room for research here in my opinion.

Regards,
Dominique