Lambda the Ultimate

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.

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

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. [...]

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.

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

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?]

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?

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!