[Haskell] class assosiated types, via GADTs.

John Meacham john at repetae.net
Tue Feb 15 06:03:05 EST 2005


On Tue, Feb 15, 2005 at 10:16:49AM +0000, Keean Schupke wrote:
> Perhaps i'm being dumb, but I dont see the need for either GADTs or 
> class-associated-types to do this... I am pretty sure it can be done 
> using fundeps,
> using the techniques from the HList paper... of course I haven't coded 
> it yet so there
> might be some problem I haven't considered.

Yeah, in the CAT paper, the relationship between functional dependencies
and CATs is explored. (see section 5). An encoding of just this example but using
functional dependencies is given and some of their properties are
explored. 

 http://research.microsoft.com/Users/simonpj/papers/assoc-types/index.htm

However CATs are a much clearer expression of ones intent (IMHO) and
have other nice properties in that useful functions can be typed via
CATs but not via fundeps. The case for them is pretty compelling.  


> By the way Oleg has already shown that there is an equivalence between 
> GADTs and the type-class encoding used for HLists.

It would not surprise me. However, just because there is an
equivalance, it doesn't mean it is useful for what one wants. I
encoded (a certain) CAT before via a GADT, but this encoding is not
directly useful to users because it would require all instances to be
known a priori, thus breaking one of the main properties of type
classes, their extensibility. However, the compiler could pull off this
translation internally (I hope) thus levaraging the work put into GADTs.

The main advantage of this translation over the one in the paper is that
it is not intertwined with the dictionary generation and typeclass
desugaring code, which is pretty hairy to begin with. Rather it is an
orthogonal transformation so hopefully will be easier to implement
without touching too much of ghcs internals.

        John


-- 
John Meacham - ⑆repetae.net⑆john⑈ 


More information about the Haskell mailing list