[Haskell-cafe] Constructor classes implementation

Sean Seefried sean.seefried at gmail.com
Tue Feb 21 19:54:51 EST 2006

Thank you for taking the time to look through the code.

>> 1. printGamma [] would print an unmotivated " }", as witnessed by
>> typeInf [] term14.
>> 2. the case
>> unify (ConT c) (AppT t1 t2)
>> is missing.
> and unifying a tyvar with itself fails. That probably doesn't occur  
> in the
> inference-algorithm, but still...

And that case is in the paper, so I should have implemented it.  I  
have now.

>> 3. too many shadowed bindings, this is always dangerous, I believe
>> 4. I'm not sure, the datatypes are appropriate; as far as I know,
>> expressions have a type and not a kind, which is what the use of  
>> the same
>> Var type for Type and Exp entails.

Thank you. This was a glaring mistake in the code and it has been  
fixed.  Type variables are the only ones that have kinds now. I have  
used your definition of fv_gamma too.

> and that led to an error: in generalise, we are interested in the free
> constructor-variables in the environment, not the term-variables,  
> hence
> -- Free variables in ...
> -- ... schemes
> fv_scheme :: Scheme -> [Var]
> fv_scheme (Scheme vs ps ty)
>      = nub (fv_preds ps ++ fv ty) \\ vs
> -- ... environments
> fv_gamma :: Gamma -> [Var]
> fv_gamma gamma = nub (concatMap (fv_scheme . snd) gamma)
> and not
> fv_gamma gamma = nub (map fst gamma)
>> I have only just glimpsed at Jones' paper, so I don't yet see,  
>> what this
>> type inference algorithm (quite nice, btw) has to do with constructor
>> classes. If I still don't after reading it, I'll come back to ask.
> I still don't see clearly. So you've implemented the type inference  
> algorithm
> from Jones' paper, good. But is there any significance or gain,  
> apart from it
> being a nice and interesting exercise?

No. Nor did I state that there was.  There's a reason I posted this  
to Haskell-cafe and not Haskell.  I just thought the code might be  
useful for other people who were similarly trying to understand how  
constructor classes are implemented.  The only other code I found  
(that wasn't inside a compiler) was that associated with the "Typing  
Haskell in Haskell" paper.  The nice thing about the algorithm in "A  
system of constructor classes: ..." is that it is small and to-the- 



More information about the Haskell-Cafe mailing list