Type classes in Haskell

ABSTRACT

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

REFERENCES

• 1: Lennart Augustsson, Implementing Haskell overloading, Proceedings of the conference on Functional programming languages and computer architecture, p.65-73, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165191]
• 2: BLOTT, S. 1991. Type classes. Ph.D. thesis, Dept. of Computing Science, Glasgow Univ., Glasgow, Scotland.
• 3: Luca Cardelli, Basic polymorphic typechecking, Science of Computer Programming, v.8 n.2, p.147-172, April 1, 1987 [doi>10.1016/0167-6423(87)90019-0]
• 4: CHEN, I~. 1994. Semantics and coherence for parametric type classes. Res. Rep., YALEU/DCS/RR-1003, Dept. of Computer Science, Yale Univ., New Haven, Conn. June.
• 5: Kung Chen, A parametric extension of Haskell's type classes, Yale University, New Haven, CT, 1994
• 6: Kung Chen , Paul Hudak , Martin Odersky, Parametric type classes, Proceedings of the 1992 ACM conference on LISP and functional programming, p.170-181, June 22-24, 1992, San Francisco, California, United States
• 7: Gordon V. Cormack , Andrew K. Wright, Type-dependent parameter inference, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.127-136, June 1990, White Plains, New York, United States
• 8: GIRARD J.-Y. 1972. Interpr6tation functionelle et 61imination des coupures dans l'arithm6tique d'ordre sup6rieure. ThSse de doctorat d'6tat, Universit6 Paris VII, Paris, France.
• 9: Kevin Hammond, Efficient Type Inference Using Monads (Summary), Proceedings of the 1991 Glasgow Workshop on Functional Programming, p.146-157, August 12-14, 1991
• 10: HAMMOND~ K. 1993. Extended type classes, Int. Memo., Dept. of Computer Science, Glasgow Univ., Glasgow, Scotland.
• 11: Kevin Hammond , Stephen Blott, Implementing Haskell Type Classes, Proceedings of the 1989 Glasgow Workshop on Functional Programming, p.266-286, August 21-23, 1989
• 12: HINDLEY~ R. 1969. The principal type scheme of an object in combinatory logic. Trans. Am. Math. Soc. 146, 29-60.
• 13: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 14: Gérard Huet, Logical foundations of functional programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 15: Mark P. Jones, A theory of qualified types, Symposium proceedings on 4th European symposium on programming, p.287-306, January 1992, Rennes, France
• 16: JONES M.P. 1992b. A theory of qualified types. D.Phil. thesis, Programming Research Group, Oxford Univ., Oxford, England. Published by Oxford University Press, 1994.
• 17: JONES M. P. 1992c. Efficient implementation of type class overloading. Int. Memo., Programming Research Group, Oxford Univ., Oxford, England.
• 18: JONES, M.P. 1993. Partial Evaluation for dictionary-free overloading. Res. Rep., YALEU/DCS/RR-959, Dept. of Computer Science, Yale Univ., New Haven, Conn. Apr.
• 19: JONES, M. P. 1994. Simplifying and improving qualified types. Res. Rep., YALEU/DCS/RR-1040, Dept. of Computer Science, Yale Univ., New Haven, Conn. June.
• 20: JONES~ M. P. 1995. A system of constructor classes: Overloading and implicit higher-order polymorphism. J. Func. Program. 5, 1, 1-37.
• 21: KAES, S. 1988. Parametric polymorphism. In Proceedings of the 1988 European Symposium on Programming (Nancy, France). Lecture Notes in Computer Science, vol. 300. Springer-Verlag, Berlin.
• 22: Konstantin Laufer, Polymorphic type inference and abstract data types, New York University, New York, NY, 1992
• 23: LAUFER~ K. 1993. An extension of Haskell with first-class abstract types. Tech. Rep., Loyola Univ. Chicago, Ill.
• 24: Konstantin Läfer , Martin Odersky, Polymorphic type inference and abstract data types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1411-1430, Sept. 1994 [doi>10.1145/186025.186031]
• 25: MILNER~ R. 1978. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17, 348-375.
• 26: Robin Milner , Mads Tofte , Robert Harper, The definition of Standard ML, MIT Press, Cambridge, MA, 1990
• 27: Robin Milner , Mads Tofte, Commentary on standard ML, MIT Press, Cambridge, MA, 1991
• 28: Tobias Nipkow , Christian Prehofer, Type checking type classes, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.409-418, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158698]
• 29: Tobias Nipkow , Gregor Snelting, Type classes and overloading resolution via order-sorted unification, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.1-14, June 1991, Cambridge, Massachusetts, United States
• 30: ODERSKY, M. AND LAUFER, K. 1991. Type classes are signatures of abstract types. Tech. Rep., IBM T.J. Watson Research Center, Yorktown Heights, N.Y. May.
• 31: Simon L. Peyton Jones, The Implementation of Functional Programming Languages (Prentice-Hall International Series in Computer Science), Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 32: PEYTON JONES, S.L. AND WADLER, P.L. 1991. A static semantics for Haskell. Int. Memo., Dept. of Computing Science, Glasgow Univ., Glasgow, Scotland.
• 33: John C. Reynolds, Towards a theory of type structure, Programming Symposium, Proceedings Colloque sur la Programmation, p.408-423, April 09-11, 1974
• 34: J C Reynolds, Three approaches to type structure, Proc. of the international joint conference on theory and practice of software development (TAPSOFT) Berlin, March 25-29, 1985 on Mathematical foundations of software development, Vol. 1: Colloquium on trees in algebra and programming (CAAP'85), p.97-138, April 1985, Berlin, Germany
• 35: Francois Rouaix, Safe run-time overloading, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.355-366, December 1989, San Francisco, California, United States [doi>10.1145/96709.96746]
• 36: D. A. Turner, Miranda: a non-strict functional language with polymorphic types, Proc. of a conference on Functional programming languages and computer architecture, p.1-16, January 1985, Nancy, France
• 37: Dennis M. Volpano , Geoffrey S. Smith, On the complexity of ML typeability with overloading, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.15-28, June 1991, Cambridge, Massachusetts, United States
• 38: Philip Wadler, The essence of functional programming, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143169]
• 39: P. Wadler , S. Blott, How to make ad-hoc polymorphism less ad hoc, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.60-76, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75283]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: Haskell

General Terms:
Languages, Theory

Keywords:
Haskell, functional programming, type classes, types