Re: Functional dependencies and Constructor Classes
Martin Sulzmann <sulzmann@comp.nus.edu.sg> writes:
Hi,
I was wondering whether other people made similiar observations. Functional dependencies seem to be expressiveness enough to encode some of the kinding rules required for Constructor Classes.
read this page: http://cvs.haskell.org/Hugs/pages/hugsman/exts.html I think that the designer of constructor class and functionnal depedencies is the same person si it makes sense that one generalise the other. nevertheless i found constructor class more elegant for many problems. Your solution is less elegant that the one using constructor classes. I found too that type error messages of class using functionnal depedencies are not easy to read. There is often ambiguity in code that are not easy to solver. this problem does not appear with constructor classes.
Take a look at the Haskell code below (runs under hugs -98 or ghci -fglasgow-exts-fallow-undecidable-instances)
Martin
-- An alternative to constructor classes
module Fmap where
{- Instead of class Functor f where fmap :: (a->b)->(f a->f b)
use -}
class Fmap a b fa fb | a fb -> b fa, b fa -> a fb, fa fb -> a b where fmap2 :: (a->b)->(fa -> fb)
{- We require:
(1) fmap2 transforms a function into another function, i.e. fmap2's type should always be of shape (a->b)->(fa->fb)
(2) b, fa uniquely determine a and fb
(3) a, fb " b and fa
(4) fa, fb " a and b
Note that (1) is enforced by the class definition. (2)-(4) are enforced by FDs.
My guess/conjecture is that the above axiomatization of functors is equivalent to the one found in Haskell98. -}
-- some Examples
{- The following is a variation of an example taken from Mark Jones original paper "A System of Constructor Classes: Overloading and Implicit Higher-Order Polymorphism". He used this example to motivate the introduction of constructor classes. The example is type correct using the alternative formulation of functors. -}
cmap :: (Fmap a b fb1 fb, Fmap a1 b1 fa fb1) => (a1 -> b1) -> (a -> b) -> fa -> fb cmap f g = (fmap2 g) . (fmap2 f)
-- identity functor instance Fmap a a a a where fmap2 h = h
-- functor composition -- Instance is not allowed, cause leads to undecidable type inference
{- instance (Fmap a b c d, Fmap e f a b) => Fmap e f c d where fmap2 h = fmap2 (fmap2 h) -}
comp :: (Fmap fa1 fb1 fa fb, Fmap a b fa1 fb1) => (a -> b) -> fa -> fb comp h = fmap2 (fmap2 h)
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
-- Yoann Padioleau, INSA de Rennes, France, Opinions expressed here are only mine. Je n'écris qu'à titre personnel. **____ Get Free. Be Smart. Simply use Linux and Free Software. ____**
Yoann Padioleau writes:
nevertheless i found constructor class more elegant for many problems. Your solution is less elegant that the one using constructor classes.
Yes, the current presentation of constructor classes might be easier to comprehend.
I found too that type error messages of class using functionnal depedencies are not easy to read. There is often ambiguity in code that are not easy to solver. this problem does not appear with constructor classes.
Well, that's the point of my encoding of functors using FD's. No ambiguities will arise! The issue I want to raise is whether constructor classes are redundant in the presence of FDs (yes, yes, we still might want to stick to the constructor class representation, but that's a different issue). Martin
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 ...)
Mark P Jones writes:
| The issue I want to raise is whether constructor classes are | redundant in the presence of FDs
No, they are not comparable.
Allow me to make the following bold claim. Assume we are given a program that uses the Haskell functor class as in class Functor f where fmap :: (a->b)->(f a->f b) We translate such a program by using class Fmap a b fa fb | a fb -> b fa, b fa -> a fb, fa fb -> a b where fmap :: (a->b)->(fa -> fb) instead. Instances are translated in the "obvious" way. Then, if the original program is typable, so will be the translated program, meaning is preserved.
Your fds version of the Functor class is also incomparable with the ccs version; the former will allow an expression like (map id 'a')
Yes, because FD's are not expressive enough to specify the form of improvement we need. Consider module Fmap where class Fmap a b fa fb | a fb -> b fa, b fa -> a fb, fa fb -> a b where fmap2 :: (a->b)->(fa -> fb) -- identity functor instance Fmap a a a a where fmap2 h = h e = fmap2 id 'a' yields Type checking ERROR Fmap2.hs:17 - Unresolved top-level overloading *** Binding : e *** Outstanding context : Fmap c c Char b though we would like to "improve" this type to Fmap Char Char Char Char where c=Char and b=Char
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.
I believe that a refined form of fds is able to encode Ccs. Give me some time to provide more evidence for my unsupported claims. Martin
participants (3)
-
Mark P Jones -
Martin Sulzmann -
Yoann Padioleau