On Thu, 11 Dec 2003, Robert Will wrote:
> Hello, > > As you will have noticed, I'm designing a little library of Abstract Data > Structuresm here is a small excerpt to get an idea: > > class Collection coll a where > ... > (<+>) :: coll a -> coll a -> coll a > reduce :: (a -> b) -> b > -> coll a -> b > ... > > class Map map a b where > ... > (<+) :: map a b -> map a b -> map a b > at :: map a b > -> a -> b > ... > > Note that the classes don't only share similar types, they also have > similar algebraic laws: both <+> and <+ are associative, and neither is > commutative. > > Now I would like to have Collection to be a superclass of Map yielding the > following typing > > reduce :: (Map map a b) => > ((a, b) -> c) -> c > -> map a b -> c Functional dependencies will do this. class Collection coll a | coll -> a where ... (<+>) :: coll -> coll -> coll reduce :: (a -> b -> b) -> b -> coll -> b ... class (Collection map (a,b)) => Map map a b | map -> a b where ... (<+) :: map -> map -> map at :: map -> a -> b Now you make instances like instance Collection [a] a where (<+>) = (++) reduce = foldr instance (Eq a) => Map [(a,b)] a b where new <+ old = nubBy (\(x,_) (y,_) -> x == y) (new ++ old) at map x = fromJust (lookup x map) > Note that in an OO programming language with generic classes (which is in > general much less expressive than real polymorphism), I can write > > class MAP[A, B] inherit COLLECTION[TUPLE[A, B]] > > which has exactly the desired effect (and that's what I do in the > imperative version of my little library). This isn't exactly the same thing. In the OO code the interface collections must provide consists of a set of methods. A particular type, like COLLECTION[INTEGER] is the primitive unit that can implement or fail to implement that interface. In the Haskell code you require a collection to be a type constructor that will give you a type with appropriate methods no matter what you apply it to (ruling out special cases like extra compace sequences of booleans and so on). A map is not something that takes a single argument and makes a collection, so nothing can implement both of your map and collection interfaces. The solution is simple, drop the spurrious requirement that collections be type constructors (or that all of our concrete collection types were created by applying some type constructor to the element type). The classes with functional dependencies say just that, our collection type provides certain methods (involving the element types). Collections were one of the examples in Mark Jones' paper on functional dependencies ("Type Classes with Functional Dependencies", linked from the GHC Extension:Functional Dependencies section of the GHC user's guide). > There seems to be no direct way to achieve the same thing with Haskell > type classes (or any extension I'm aware of). Here is a quesion for the > most creative of thinkers: which is the design (in proper Haskell or a > wide-spread extension) possibly include much intermediate type classes and > other stuff, that comes nearest to my desire? > > I believe this question to be important and profound. (We shouldn't > make our functional designs more different from the OO ones, than they > need to be.) If I err, someone will tell me :-> What problems do objects solve? They let you give a common interface to types with the same functionality, so you can make functions slightly polymorphic in any argument type with the operations your code needs. They organize your state. Then let you reuse code when you make a new slightly different type. Am I missing anything here? I think type classes are a much better solution than inheritance for keeping track of which types have which functionality. (at least the way interface by inheritance works in most typed and popular object oriented languages.) Inheritance only really works for notions that only involve the type doing the inheriting, or are at least heavly centered around that type. I don't think Functor can be represented as an interface, or at least not a very natural one. Most langauges I know of (see Nice for an exception) also require you to declare the interface a class supports when you declare it, which is really painful when you want your code to work with types that were around before you were, like defining a class to represent marshallable values for interface/serialization code. Are there any advantages to inheritance for managing interfaces? Maybe it takes a few minutes less to explain the first time around. It's probably easier to implement. Beyond that, I see nothing. Any creative thinkers want to try this? (An answer here would motivate an extension to the type class system, of course). Brandon > Robert _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell