Functional dependencies and Constructor Classes

[Mark P Jones]

Hi Martin,

| The issue I want to raise is whether constructor classes are 
| redundant in the presence of FDs

No, they are not comparable.

Let fds = functional dependencies
    ccs = constructor classes

Example of something you can do with ccs but not fds:

   data Fix f = In (f (Fix f))

Example of something you can do with fds but not ccs:

   class Collects e ce where ...   -- see fds paper for details
   instance Eq e => Collects e [e] where ...
   instance Eq e => Collects e (e -> Bool) where ...

Your fds version of the Functor class is also incomparable with the
ccs version; the former will allow an expression like (map id 'a')
to be type checked, the latter will not, treating it instead as a
type error.  In this specific case you may regard the extra flexibility
provided by fds as a win for expressiveness.  On another occasion,
however, you may be disappointed to discover that you have delayed
the detection of a type error from the point where it was introduced.

There's a lot more that could be said about this, but I don't have
time to go into detail now.  Hopefully, I have at least answered your
basic question.  The approach you've suggested using fds reminds me
most directly of the work on Parametric Type Classes (PTC) by Chen,
Hudak and Odersky.  In my paper on Functional dependencies, I made
the following comment regarding that work:

 "Thus, PTC provides exactly the tools that we need to define and
  work with a library of collection classes.  In our opinion, the
  original work on PTC has not received the attention that it
  deserves. In part, this may be because it was seen, incorrectly,
  as an alternative to constructor classes and not, more accurately,
  as an orthogonal extension."

I believe the same is true in this case.  Ccs and fds address
different problems.  They are complementary tools, each with their
own strengths and weaknesses.

All the best,
Mark

Refs: for those who want to follow along:

  Type Classes with Functional Dependencies
    http://www.cse.ogi.edu/~mpj/pubs/fundeps.html

  Constructor Classes
    http://www.cse.ogi.edu/~mpj/pubs/fpca93.html
    (But read the JFP version instead if you can; it's
    much better ...)