[Haskell-cafe] Re: Type classes and type equality

oleg at pobox.com oleg at pobox.com
Tue Apr 17 17:36:52 EDT 2007

> Thanks for pointing that out. As far as I can see, this requires a new
> instance declaration for every type?

I guess it depends on how many extensions one may wish to enable. At
the very least we need multi-parameter type classes with functional
dependencies (because that's what TypeEq is in any case).

- If we permit no other extension, we need N^2 instances to compare N
classes for equality (basically, for each type we should say how it
compares to the others). This is not practical except in very limited

- If we permit undecidable instances, one may assign numerals to
types. This gives us total order and hence comparison on types.
In this approach, we only need N instances to cover N types. This is
still better than Typeable because the equality is decided and can be
acted upon at compile time.

- If we permit overlapping instances extension, then a few lines of code
decide equality for all existing and future types:

	class  TypeEq x y b | x y -> b
	instance TypeEq x x HTrue
	instance TypeCast HFalse b => TypeEq x y b

Please see 
for some less conventional application, with the complete code.

> I was really hoping for something that requires less work on behalf of
> the user.

The latter approach may be suitable then. It requires no work on
behalf of the user at all: the type comparison is universal.


There is also an issue of ground vs unground types. All the approaches
above can decide equality for sufficiently grounded types. That is,
two types can be decided equal only if they are ground. The
disequality may be decided for partially ground types. If the types
are non-ground, the TypeEq constraint flows up, to be resolved when
the types are sufficiently instantiated. It is possible to decide
equality of non-ground types and even naked type variables. That is a
separate discussion.

More information about the Haskell-Cafe mailing list