[Haskell] Re: class assosiated types, via GADTs.

[Manuel M T Chakravarty]

On Mon, 2005-02-14 at 19:17 -0800, John Meacham wrote:
> I believe there is a realationship between GADTs and class assosiated
> types which hints at  a much simpler implementation of class assosiated
> types (CATs) and possibly a lessoning of the constraints mentioned in
> the paper.

It is true that there is a correspondence between GADTs and associated
types.  However, as you mention, there is also a crucial difference
between the two:

> The only caveats I can think of to actually implementing this in ghc are
> separate compilation, the Map GADT must be marked somehow as 'open'
> since later instances might create new constructors for it.

GADTs constitute closed definitions (just like simple algebraic data
types), whereas type classes are open.  To provide open algebraic data
types is generally a hard problem.  In your proposal, it might be
somewhat easier as you seem to require it only as an internal feature
used inside the compiler and not something users can directly exploit
(e.g., you don't have to worry about extending function definitions over
these open data types).

However, it is still problematic.  Say, for example, that you define the
class MapKey including one instance in a module M, which you import in
N1 and N2.  Now, in both N1 and N2, you add new instances (for different
types) to MapKey.  Then, in both N1 and N2, you will extend the GADT Map
differently.  If you import all three M, N1, and N2 into your Main
module, you need to "merge" these different versions of Map.

This merging is awkward, as during the compilation of N1 and N2, the
compiler needs to make choices about the concrete representation of the
two versions of Map, which will affect the code that it generates.
Compilers typically assign numbers to each constructor of a data type to
represent the different variants at runtime.  It's customary to start at
0 and just count through the constructors.  That would obviously not
work in a situation where you later have to merge different versions of
a data type.

Interestingly, a few days ago, it occurred to me that you can realise
extensible data types quite nicely with associated types (not too
surprising considering the above).  See 

  http://www.cse.unsw.edu.au/~chak/haskell/ExtensibleDataTypesWithAssociatedTypes.html

for details.

Cheers,
Manuel