type classes, superclass of different kind

[Brandon Michael Moore]

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