Quote:

MacQueen) writes:

| This brief note compares the capabilities of Haskell's type classes

| with those of the Standard ML module system

I'm glad that this topic has been brought up here; I'm sure the

discussion is long overdue and recent messages on comp.lang.functional

confirm this.

I'm sorry that this is so long, but there is a lot to reply to...

Before I get into the real issues, let me start with some examples to

illustrate why so many people have been tempted to make comparisons

between Standard ML modules and Haskell type classes. As you'll see

a little later, I think you have to be very careful to compare the

right things ...

SOME EXAMPLES:

--------------

Looking at the following examples, it's easy to see some kind of

underlying correspondence between the two systems. These definitions

might be used to describe equality. I will write the Haskell code

on the right and the `corresponding' SML on the left. To start with,

the similarity between Haskell class declarations and SML signature

declarations is quite striking:

signature EQ =

sig

type t class EQ t where

val eq : t * t -> bool eq :: (t,t) -> Bool

end;

In addition, Haskell instance declarations look rather like SML

structure definitions:

structure EqInt : EQ =

struct

type t = int instance EQ Int where

val eq = (op =):int*int->bool eq (x,y) = primEqInt x y

end;

or, more generally, when a context is required for a Haskell instance

declaration, an SML functor definition:

functor EqList(Eq : EQ) : EQ =

struct

type t = Eq.t list instance EQ a => EQ [a] where

fun eq ([],[]) = true eq ([],[]) = True

| eq ((x::xs),(y::ys)) eq (x:xs,y:ys)

= Eq.eq (x,y) = eq (x,y)

andalso eq (xs,ys) && eq (xs,ys)

| eq _ = false; eq _ = False

end;

I don't think there is any need to go into examples to show how

much more can be done with ML modules which go beyond the power of

Haskell type classes. Standard textbooks (e.g. ML for the working

programmer) and the source for well-known programs including SML/NJ

(such as the excerpt that Dave MacQueen included in his posting)

give many examples which illustrate this better than I can here.

I will briefly describe one example in which the facilities of the

Haskell type class system seem (IMHO) to be more convenient. Suppose

that we want to define a function to test for membership in a list

based on the equality test `eq' described above. In Haskell, this

can be implemented using a top-level definition, in SML a functor

definition is needed to capture the dependency on the equality that

is used:

functor Member(Eq : EQ) =

struct

fun member (x,[]) = false member (x,[]) = False

| member (x,y::ys) member (x,y:ys)

= Eq.eq (x,y) = eq (x,y)

orelse member (x,ys) || member (x,ys)

end;

Now suppose you want to test for membership of a given list in a list

of lists of integers. In Haskell we can write:

member ([1,2], [[1], [2,3], [3,4,5]])

In SML we have to build the appropriate structures and then extract

the equality function from that:

structure eqListInt = EqList(EqInt);

structure memberListInt = Member(eqListInt);

memberListInt.member ([1,2], [[1], [2,3], [3,4,5]]);

The first two lines here are the equivalent of building dictionaries

which happens automatically in the Haskell version. The fact that

the Haskell system is not as sophisticated as the ML module system

makes this possible.

WHY MIGHT YOU MIGHT WANT TO ADD HASKELL STYLE TYPE CLASSES TO SML?

------------------------------------------------------------------

The treatment of polymorphic equality has long been acknowledged as

one of the weaker aspects of SML. Haskell's system of type classes

provide a solution to this, something that many Haskell users have

come to appreciate. Furthermore, type classes also provide a more

general treatment for the overloading of numeric operations. The

fact that this all supported within the same framework, controlled

by the programmer, is certainly attractive. As the original paper

claimed, type classes are a way of making ad-hoc polymorphism

less ad-hoc.

The fact that Haskell type classes (without any of the extensions

that have been proposed (and often implemented) since their

introduction) do not support:

(1) n-ary type constructors

(2) multiple type constructors

(3) multiple instances per type

(4) visibility of type parameter

(5) Certain granularities of parameterization

(6) Nesting

(7) Coercive subtyping

(8) Higher order modules

(i.e. the points mentioned in Dave MacQueen's message) are not really

important since these features are not needed to deal with the kinds

of applications for which type classes are intended.

WHY MIGHT YOU WANT TO ADD SML STYLE MODULES TO HASKELL?

-------------------------------------------------------

The module system in the current version of Haskell is one of the

weakest parts of the language. I have a great admiration for the

SML module system and feel that Haskell could benefit substantially

from a similar system. I am sure that there are many other people

in the Haskell community who would agree with this.

(`I come, not to criticise SML modules, but to praise them' :)

As the examples at the beginning of this message indicate and as

Dave MacQueen mentions in his posting, there is a definite overlap

between the two systems. We need to get a better understanding of

this before we can hope to find a satisfactory solution which

combine both in a single language. Reading Dave MacQueen's message,

I get the impression that he does not think that such a solution

can be found; for example we do not currently know how a type class

might be specified in a module signature. For my part, I hope that

a good solution can be found. I also do not know whether it is

possible, but the idea of a language which supports both type

classes and and parametric modules in an elegant and consistent

fashion is sufficiently appealing to warrant further investigation.

And even if we ultimately find that there is no solution, we will

have learnt a lot along the way.

TYPE CLASSES AS AN ALTERNATIVE TO ML MODULES?

ML MODULES AS AN ALTERNATIVE TO TYPE CLASSES?

---------------------------------------------

No, absolutely not. It's true that there is something similar in the

motivation for two systems:

| Parametric modules in SML (functors) and Haskell type classes were

| both devised to deal with a need not met by classical parametric

| polymorphism: to wit, the need to parameterize not only with respect to

| a type, but with respect to a type accompanied by a set of associated

| functions to operate on, or "interpret" that type.

Both systems are intended to deal with a need not meet by parametric

polymorphism. But the `need' is different in each case. They are,

in effect, solutions to different problems.

Parameterization is certainly a common ground between the two, but

David goes on to explain where the difference lies:

| Haskell's type classes handle parameterization and instantiation

| implicitly as an extension of the classic Hindley-Milner polymorphic

| type inference system. SML expresses the parameterization explicitly

| through the definition and application of functors.

Implicit versus explicit. That is the key difference. Pretty much

anything that can be done in an implicit manner can also be done

in an explicit manner. After all, the implicit version is usually

just thought of as a convenient shorthand for the explicit version.

It is the degree of convenience provided that makes the implicit

version worth considering.

MISCELLANEOUS REMARKS:

----------------------

| One limitation of Haskell's type classes is that parameterization is

| only allowed over simple types (i.e. 0-ary type constructors like

| int). Generalizations to n-ary type constructors (n>0) like list

| have been proposed by Paul Hudak and Mark Jones, but they further

| complicate the type class system. SML functors handle n-ary type

| constructors for any n in a uniform manor.

One could argue that some of the extensions proposed actually reduce

complexity by eliminating special cases and ad-hoc restrictions.

You refer to some of my work here. IMO, this is certainly true for

some of the extensions which I have investigated (and that you refer

to here), both from a theoretical and implementation standpoint.

| In addition, I would argue that the semantics of SML modules is

| probably simpler than that of type classes, and it is easier to

| implement them efficiently. In terms of complexity of static

| elaboration, they are probably roughly comparable.

The examples that I started this message with illustrate a translation

from a language with type classes to a language with SML modules.

In my opinion, it should be possible to construct an implementation

of type classes in this way by automating the translation. Although

I have not actually done this, it is actually very close to the way

that the current version of Gofer works, so this is more than just a

vague notion. (Of course, I'm ignoring the strict/non-strict distinction

between the two languages.) On that assumption, type classes can be

implemented just as efficiently as the `corresponding' SML version.

(On the other hand, since the target of the translation is not the

full SML module language, it may even be possible to get a more

efficient implementation because you don't have to support the full

generality which that requires.)

THE BOTTOM LINE:

----------------

Type classes are no substitute for parametric modules. They're

not intended to be. But they do offer a

...

**read more »**