[bitc-dev] Instance coherence: the shape of a solution

Sandro Magi naasking at higherlogics.com
Mon Apr 16 12:18:52 PDT 2012


On 16/04/2012 2:22 PM, Jonathan S. Shapiro wrote:
> And there's actually an advantage to the procedure approach, because it
> /doesn't/ bind the choice of ordering into the type of the BTree. This
> leaves us free to implement a merge function that doesn't care about the
> orderings of the input and update trees.

There are numerous advantages to function parameter approaches, namely
that functions are first-class and type classes are not. That said, if
you support both type classes and functions, you end up with a lot of
duplication, ie. Haskell's "sort" and "sortBy" variants.

"Objects to Unify Type Classes and GADTs" went a long way to eliminating
this duplication. The reason type classes are so attractive is twofold:

 1. Implicit instantiation.
 2. Sets of overloaded methods whose invariants must be coherent are
grouped together.

Scala's implicits [1] might give you #1 with the scoping you desire. #2
still seems like an attractive property as well, however #2 is within
the domain of a module system. So then you're faced with a choice of
whether to create a type class or a module signature.

If that's going to be a concern for you down the road, then you'll be
interested in the work to provide the implicit resolution of type
classes as an idiomatic use of modules [2]. You'll be particularly
interested in section 3, since 3.1 is "coherence in the presence of
scoped instances".

Sandro

[1] http://ropas.snu.ac.kr/~bruno/papers/TypeClasses.pdf
[2] http://www.mpi-sws.org/~dreyer/papers/mtc/main-long.pdf



More information about the bitc-dev mailing list