type classes, superclass of different kind

[Niklas Broberg]

Robert Will wrote:

>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 don't know if I qualify as the most creative of thinkers, but I have a 
small library of ADSs that you may want to look at, it's at

http://www.dtek.chalmers.se/~d00nibro/algfk/

I recall having much the same problem as you did, my solution was to make 
maps (or Assoc as I call them) depend on tuple types, i.e. (somewhat 
simplified):

class (Collection c (k,v), Eq k) => Assoc c k v where
  lookup :: k -> c (k,v) -> v
  [...many more member functions here...]

This means that the type constructors for maps and collections have the same 
kind (* -> *), which makes it possible for me to say that an Assoc is 
actually also a Collection. A lot more info to be found off the link.

>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 :->

No need to recreate all the stupid things the OO world has come up with, 
better to do it correctly right away... ;)

/Niklas Broberg, d00nibro[at]dtek.chalmers.se

_________________________________________________________________
The new MSN 8: advanced junk mail protection and 2 months FREE* 
http://join.msn.com/?page=features/junkmail