Constructor classes

What is the benefit of a constructor class in a language like Gofer over type classes in a language like Haskell? Is there way to implement one in terms of the other? If they are worth it, can constructed classes be elegantly implemented in a language that does not support them? I find these types of discussion very interesting. Anyone who can point in me a direction, I would greatly appreciate it.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Haskell type classes are

Haskell type classes are Gofer constructor classes and vice versa. Originally, Haskell type classes were restricted to types constructors of kind * (i.e. types.) Gofer pioneered the work in lifting that restriction. Haskell then adopted it. Hugs stands for "Haskell User's Gofer System."

Can you synopsize

Can you synopsize briefly what has been enabled? I'm actually not clear on the difference between type classes and constructor classes, possibly because I came to the discussion after all of this was sorted out.

Very significant

It's a very significant change. Without constructor classes, for example, it's not possible to abstract over various containers with similar properties. For instance, it's not possible to notice that List and Maybe have similar properties, and write functions that can operate on values of "List a" and "Maybe a":

  class Functor f where
    fmap :: (a -> b) -> f a -> f b
  instance Functor List where ...
  instance Functor Maybe where ...

Many of the most commonly used Haskell classes are constructor classes, including Functor, Monad and friends. For better or worse, it's also constructor classes that lead to some of the more abstruse abstractions and give Haskell a reputation for being difficult. It's a level of abstraction that not many languages can express, so people tend not to have much experience with it.

In case this helps... the difference is basically that between Java's generics and Scala's generics. In Java, I can write a class List<T> and use it as List<Int>, but I cannot write a class like Iterable<C> and use it as Iterable<List>. In Scala (where this is usually reffered to as "higher-kinded types"), I can do this. I'm not sure whether that helps you...

Mechanism over ability

Without constructor classes, for example, it's not possible to abstract over various containers with similar properties.

Sure it is. You just use another abstraction mechanism. For example, you could use a good old fashioned record of functions for manipulating containers that you pass to a function that needs to be independent of the kind of container being used.

For instance, it's not possible to notice that List and Maybe have similar properties

Excuse me? Surely you have the ability make observations and perform reasoning without constructor classes? You can even express abstractions that capture such similarities without having the specific abstraction mechanism of constructor classes.

It's a level of abstraction that not many languages can express

I find that you are confusing having a specific (convenient) mechanisms for the ability to express abstractions. You could accurately say that not many languages have a specific mechanism for expressing abstractions over parameterized type constructors. (Heck, many languages don't even have parameterized type constructors.) However, it is quite a stretch to go from there to saying that you could not express an abstraction that (reasonably) captures the notion of a Monad (or Functor). In fact, one could argue that even Haskell's constructor classes cannot express the concept of a Monad, because Haskell's type system is not powerful enough to tell whether or not an arbitrary instance of the Monad type class satisfies the monad laws.

BTW, you might object to the move from the general "abstractions over parameterized type constructors" to the specific "notion of a Monad". That is not my mistake. The mistake is already present in your post and is in fact part of the point that I'm making here.

In case this helps... the difference is basically that between Java's generics and Scala's generics. [...]
IMO, that was the only paragraph in your post that was actually accurate. The rest sounded more like propaganda to me.

Fair

You're right, but I think you may have read more into my post than I intended. Of course I'm not claiming that constructor classes are a uniquely expressive abstraction mechanism. I was only comparing constructor classes with "regular type classes", not with the entire universe of possible tools and techniques. When I claim, for instance, that something "is not possible", I meant that it isn't possible using non-constructor type classes.

I do not think that 'the move from the general "abstractions over parameterized type constructors" to the specific "notion of a Monad"' is a mistake. I meant it as an example of a useful type class that cannot be written without constructor classes. However, your point about the limitations of Haskell's type system with respect to the monad laws is well taken.

Anyway, I am not a Haskell zealot, and I certainly don't intend to defend its design or engage in advocacy or "propaganda". On the other hand, I do think that, given only this one design choice, Haskell is a richer language with constructor classes than without. Scala's type system is richer than Java's in this sense, as well. In any case, I think my original post did answer shap's question, which was quite specific: "What techniques are enabled by the move from type classes to constructor classes?"

Thanks for clarifying my answer, and I apologize for any vagueness, or if I seemed to claim more than I intended. I also apologize if the post had the tone of propaganda: that was absolutely not my intention.

great, thank you

Do you know of any tutorials on typeclasses?

Haskell.org usually has good explanations

http://www.haskell.org/tutorial/classes.html

As far as I understand it

With type constructor classes you are only allowed to bind operations to type constructors. With type classes you are allowed to bind operations to parameterized types.

Assume a type class Eq which is supposed to bind an equality operation ==.

If you only have type constructor classes you can only bind == to a function for each type constructor, say List, if you have full Haskell-like type classes you can bind == to a function for every (constructed) type such as List Int, List Bool, List (Map a b), List (Map Bool Int), etc.

Type constructor classes are more easily implemented, are more restricted in their use, allow somewhat more efficient code and have cleaner operational semantics.

Still confused

Since it seems that BitC's type classes are doing all of the things attributed to constructor classes, I'm no longer clear which one we did in BitC. We can definitely bind operators differently over (List char), (List bool), and (List 'a), and we appear to be able to do abstraction over things like collections, so I'm now more confused than before.

It doesn't really matter pragmatically. I'ld just like to label what we did in BitC correctly and give proper credit to the antecedents.

Hmm

I reread "Mark P Jones, A system of constructor classes: overloading and implicit higher-order polymorphism."

He proposes constructor classes as an extension of type classes, so, whoops, me bad, I guess I misunderstood again. In his sense, a constructor class is a mechanism to bind functions to (higher-kinded?) type constructors.

Again, I guess they are orthogonal to each other, given his example of the map function.

However, I guess the discussion is moot. I glanced at the BitC spec, you did normal Haskell-like type classes.

[Actually, for my forthcoming language *cough*, it turned out I did something in between constructor classes and type classes. But I was driven by the pragmatics of wanting to have a simple operational semantics which allowed some kind of late binding and unwilling to implement type dictionaries. All disclaimers hold, though, there is no language as of yet, and the type-system has not been thoroughly reviewed. I am not even sure whether it terminates for all types/type schemes.]

[Also, I guess Gofer/Miranda? started out with constructor classes which were extended to type classes to discriminate between, say, list bool and list int, and lost something in the process?]

Example?

I've glanced at the spec and prelude, and don't see an example of abstracting over a container. Do you have an example of something like the Functor type class? I would imagine something like this (pardon my doubtless awful BitC syntax):

(deftypeclass (Functor 'f)
  fmap : (fn ((fn (a) b) ('f 'a)) ('f 'b)))

Does that make sense? Is it possible in BitC?

That is missing

We have type functions, which subsume parts of this, but no functors. I finally realized today while working through a "simple" example what we were missing.

But thanks!