type classes, superclass of different kind
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 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). 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 :-> Robert
Robert Will wrote:
Note that in an OO programming language with generic classes ...
(We shouldn't make our functional designs more different from the OO ones, than they need to be.)
why should *we* care :-) more often than not, OO design is resticted and misleading. you see how most OO languages jump through funny hoops (in this case, generics) because they just lack proper higher-order types. good luck with your library. but make sure you study existing (FP) designs, e. g. Chris Okasaki's Edison: http://www.eecs.usma.edu/Personnel/okasaki/pubs.html#hw00 -- -- Johannes Waldmann, Tel/Fax: (0341) 3076 6479 / 6480 -- ------ http://www.imn.htwk-leipzig.de/~waldmann/ ---------
--- Robert Will <robertw@stud.tu-ilmenau.de> wrote: -- > 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? Hello, I've often wondered the same thing. I've found that one can simulate several OO paradigms. Note that these aren't particularly elegant or simple. ---- Using Data Constructors: ----
data Shape = Rectangle {topLeft :: (Int, Int), bottomRight :: (Int,Int) } | Circle {center :: (Int,Int), radius :: Int }
This allows you have a list of shapes
shapeList :: [Shape] shapeList = [ Rectangle (-3,3) (0,0), Circle (0,0) 3 ]
When you want member functions, you need to specialize the function for all the constructors.
height :: Shape -> Int height (Rectangle (a,b) (c,d)) = b - d height (Circle _ radius) = 2 * radius
Disadvantages: 1) When a new Shape is needed, one needs to edit the original Shape source file. 2) If a member function is not implemented for a shape subclass, it will lead to a run-time error (instead of compile-time). Advantages: 1) Simple Syntax 2) Allows lists of Shapes 3) Haskell98 Example: GHC's exception types http://www.haskell.org/ghc/docs/latest/html/base/Control.Exception.html ---- Using Classes ---- Classes can be used to force a type have specific functions to act upon it.
From our previous example:
class Shape a where height :: a -> Int
data Rectangle = Rectangle {topLeft :: (Int, Int), bottomRight :: (Int,Int) } data Circle = Circle {center :: (Int,Int), radius :: Int }
instance Shape Circle where height (Circle _ radius) = 2 * radius
instance Shape Rectangle where height (Rectangle (a,b) (c,d)) = b - d
In this case, something is a shape if it specifically has the member functions associated with Shapes (height in this case). Advantages 1) Simple Syntax 2) Haskell98 3) Allows a user to easily add Shapes without modifying the original source. 4) If a member function is not implemented for a shape subclass, it will lead to a compile-time error. Disadvantages: 1) Lists of Shapes not allowed Example: Haskell 98's Num class. http://www.haskell.org/ghc/ ---- Classes with Instance holder. ---- There have been a few proposals of ways to get around the List of Shapes problem with classes. The Haskell98 ways looks like this
data ShapeInstance = ShapeInstance { ci_height :: Int }
toShapeInstance :: (Shape a) => a -> ShapeInstance toShapeInstance a = ShapeInstance { ci_height = (height a) }
instance Shape ShapeInstance where height (ShapeInstance ci_height) = ci_height
So when we want a list of shapes, we can do
shapeList = [ toShapeInstance (Circle (3,3) 3), toShapeInstance (Rectangle (-3,3) (0,0) ) ]
Of course this also has it's disadvantages. Everytime a new memeber function is added, it must be noted in the ShapeInstance declaration, the toShapeInstance function, and the "instance Shape ShapeInstance" declaration. Using a haskell extention, we can get a little better. Existentially quantified data constructors gives us this:
data ShapeInstance = forall a. Shape a => ShapeInstance a
instance Shape ShapeInstance where height (ShapeInstance a) = height a
shapeList = [ ShapeInstance (Circle (3,3) 3), ShapeInstance (Rectangle (-3,3) (0,0) ) ]
The benefits of this method are shorter code, and no need to update the ShapeInstance declaration every time a new member function is added. ---- Records extention ---- A different kind of inheritance can be implemented with enhanced haskell records. See http://research.microsoft.com/~simonpj/Haskell/records.html and http://citeseer.nj.nec.com/gaster96polymorphic.html for in depth explinations. I'm not sure if these have been impemented or not, but it would work as follows. The inheritance provided by the above extentions is more of a data inheritance than a functional inheritance. Lets say all shapes must have a color parameter:
type Shape = {color :: (Int,Int,Int)} type Circle = Shape + { center :: (Int,Int), radius :: (Int) } type Rectangle = Shape + { topLeft :: (Int,Int), bottomRight :: (Int, Int) }
So now we can reference this color for any shape by calling .color.
getColor :: (a <: Shape ) -> a -> (Int,Int,Int) getColor a = a.color
I'm not sure how the records extention could be used with Classes with instance holders to provide an even more plentiful OO environment. So I'll conclude this email with the observation that Haskell supports some OO constructs although not with the most elegance.
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
participants (4)
-
Brandon Michael Moore -
David Sankel -
Johannes Waldmann -
Robert Will