Functional dependencies question

Iavor Diatchki
Mon, 12 May 2003 10:04:05 -0700


Andrew J Bromage wrote:
> G'day everyone.
> Suppose I have code like this:
> 	class Foo a b | a -> b where
> 	    foo :: a -> b
> 	bar :: (Foo Char t) => t
> 	bar = foo 'a'
> All well and good so far.  Let's add an instance of Foo...
> 	instance Foo Char Bool where
> 	    foo c = isAlpha c
> Now neither GHC nor Hugs will allow this to compile, as the declared
> type of bar is "too general".

The declared type here refers to the signature of "bar". It says that 
bar should work
for any "t", but the functional dependency forces "t" to be Bool.

> This seems intuitively the wrong behaviour.  Either the original
> program was incorrect (as there was no visible instance of Foo for
> type Char) or the amended program is correct (since the type of bar
> is no more general than it was in the first version).

In a sense the original program is wrong.  The way I think of the 
declaration is as follows:
"if there was an instance for 'Foo Char t' (for all t) I could make you 
a 't' as declared in the body of the function".
Now since there is no instance for 'Foo Char t'  you would never be able 
to use "bar",
and in that sense the program is wrong (well, perhaps useless).   An 
instance that would work with the
declaration of "bar" would be somthing like:
instance Foo [a] a where foo = head

bye iavor