[Haskell-cafe] Re: A question about functional dependencies and existential

[oleg at pobox.com]

>>> class T root pos sel | pos -> root, root -> sel where
>>>    f :: pos -> sel -> Bool
>>> instance T root (Any root) sel

> But the same applies to the second functional dependency and the type
> variable sel. Every instantiation of root determines the instantiation
> of sel. And that forbids instance T Int (Any Int) Bool and instance T
> Int (Any Int) Int inside the same scope, doesn't it?

Indeed that is your intent, expressed in the functional dependency. It
may help to think of a class declaration as an `interface' and of the
set of instances as an `implementation' (of the type class). In the
example above, the "class T root pos sel" _declares_ a ternary
relation T and specifies some `constraints'. The set of instances of T
(in our example, there is only one instance) specifies the triples
whose set defines the relation T. In Herbrand interpretation, an
unground instance
	instance C1 x y => C (Foo x) (Bar y)
corresponds to a set of instances where the free type variables are
substituted by all possible ground types provided the instance
constraints (such as C1 x y) hold. In our example, an unground
instance |instance T root (Any root) sel| is equivalent to a set of
ground instances where |root| and |sel| are replaced with all possible
ground types. Including
	instance T Int (Any Int) Bool
	instance T Int (Any Int) Int
These two instances are in the model for 
`instance T root (Any root) sel'. A set of instances, an
implementation of a type class, must satisfy the interface, that is,
constraints imposed by the class declaration, including the functional
dependency constraints. In our example, any implementation of T must
satisfy root -> sel constraints. The above two instances show there
exists a model of T where the functional dependency is
violated. That's why both GHC 6.4 and Hugs reject the instance. Again,
it is a mystery why GHC 6.6 accepts it.