ML Modules and Haskell Type Classes: A Constructive Comparison

ML Modules and Haskell Type Classes: A Constructive Comparison
Stefan Wehr and Manuel M.T. Chakravarty

Researchers repeatedly observed that the module system of ML and the type class mechanism of Haskell are related. So far, this relationship has not been formally investigated. The work at hand fills this gap by presenting a constructive comparison between ML modules and Haskell type classes; that is, it introduces two formal translations from modules to type classes and vice versa, which enable a thorough comparison of the two concepts.

And the conclusions...

In this work, we demonstrated how ML modules can be translated to Haskell type classes, proved that the translation preserves type correctness, and provided an implementation of the translation. The source language of the translation is a sub-set of Standard ML, the most important feature missing is the ability to define nested structures. The target language is a subset of Haskell 98 extended with multi-parameter type classes and (abstract) associated type synonyms. Abstract associated type synonyms, another contribution of this work, are used to translate abstract types to Haskell. Our practical experience suggests that it is feasible to use the general idea behind the translation for practical programming because some of the overhead introduced by the formal translation is avoided when writing the
Haskell code by hand.

Furthermore, we showed that Haskell type classes can be translated into ML modules by using first-class structures as runtime evidence for type class constraints. We proved that this translation also preserves type correctness and implemented it. The source language of the translation is a subset of Haskell 98, which does not support constructor classes, class methods with constraints, and default definitions for methods. The target language is a subset of Standard ML extended with first-class structures and recursive functors. It is not recommended writing programs in the style of the translation by hand because too much syntactic overhead is introduced by explicit dictionary abstraction and application. However, the translation provides a good starting point for integrating type classes into the ML module system.

Finally, we presented a thorough comparison between ML modules and Haskell type classes, which fills a serious gap in the literature because it is the first comparison between the two concepts that is based on formal translations. The comparison shows that there are also significant differences between modules and type classes.

Comment viewing options

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

Very Cool!

I wonder how their results would translate to O'Caml's module system, which is interestingly different from Standard ML's (in particular, it's applicative rather than generative)?

I want. I want.

In the department of small worlds, I notice the Andreas' response to my question about the relation between functors and type classes (as I gleaned from CTM) is cited in the article. Although I'd love to have type classes in ML, I'll have to wait until some crazed PL designer makes them easier to use. Nice to know that progress is being made in this direction.

[Edit Note] I guess I should mention that the main stumbling block of implementing Type Classes in ML is getting them to be as non-overlapping with Modules as much as possible. The fact that they overlap in terms of functionality is part of the problem, in that you don't really want duplication (for various reasons, orthogonality is a goal),

Type classes in ML

The paper Modular Type Classes explains how to provide single-parameter type (as opposed to constructor) classes by having the compiler automatically assemble functors in the same places a Haskell compiler would figure how satisfy a class constraint with the available instances. The paper was written by Derek Dreyer, Robert Harper, Manuel Chakravarty, and Gabriele Keller, and cites "ML Modules and Haskell Type Classes: A Constructive Comparison".

Great stuff!

Exciting times for ML designers. Sounds like they are very close to hammering out a solution.