Type classes in Haskell

Cordelia Hall, Kevin Hammond, Simon Peyton Jones

and Philip Wadler

Glasgow University

Abstract

This paper defines a set of type inference rules for resolving overloading
introduced by type classes. Programs including type classes
are transformed into ones which may be typed by the HindleyMilner
inference rules. In contrast to other work on type classes, the
rules presented here relate directly to user programs. An innovative
aspect of this work is the use of second-order lambda calculus to
record type information in the program.

1. Introduction

The goal of the Haskell committee was to design a standard lazy functional language, applying existing, well-understood methods. To the committee's surprise, it emerged that there was no standard way to provide overloaded operations such as equality (==), arithmetic (+), and conversion to a string (show).

Languages such as Miranda1[Tur85] and Standard ML [MTH90, MT91] offer differing solutions to these problems. The solutions differ not only between languages, but within a language. Miranda uses one technique for equality (it is defined on all types { including abstract types on which it should be undefined!), another for arithmetic (there is only one numeric type), and a third for string conversion. Standard ML uses the same technique for arithmetic and string conversion (overloading must be resolved at the point of appearance), but a different one for equality (type variables that range only over equality types).

The committee adopted a completely new technique, based on a proposal by Wadler, which extends the familiar Hindley-Milner system [Mil78] with type classes. Type classes provide a uniform solution to overloading, including providing operations for equality, arithmetic, and string conversion. They generalise the idea of equality types from Standard ML, and subsume the approach to string conversion used in Miranda. This system was originally

This work is supported by the SERC AQUA Project. Authors' address: Computing Science Dept, Glasgow University, 17 Lilybank Gdns., Glasgow, Scotland. Email: fcvh, kh, simonpj, [email protected]
1 Miranda is a trademark of Research Software Limited.