skip to main content
10.1145/1159842.1159848acmconferencesArticle/Chapter ViewAbstractPublication PagesicfpConference Proceedingsconference-collections
Article

Polymorphic variants in Haskell

Published: 17 September 2006 Publication History

Abstract

In languages that support polymorphic variants, a single variant value can be passed to many contexts that accept different sets of constructors. Polymorphic variants can be used in order to introduce extensible algebraic datatypes into functional programming languages and are potentially useful for application domains such as interpreters, graphical user interface (GUI) libraries and database interfaces, where the number of necessary constructors cannot be determined in advance. Very few functional languages, however, have a mechanism to extend existing datatypes by adding new constructors. In general, for polymorphic variants to be useful, we would need some mechanisms to reuse existing functions and extend them for new constructors.Actually, the type system of Haskell, when extended with parametric type classes (or multi-parameter type classes with functional dependencies), has enough power not only to mimic polymorphic variants but also to extend existing functions for new constructors.This paper, first, explains how to do this in Haskell's type system (Haskell 98 with popular extensions). However, this encoding of polymorphic variants is difficult to use in practice. This is because it is quite tedious for programmers to write mimic codes by hand and because the problem of ambiguous overloading resolution would embarrass programmers. Therefore, the paper proposes an extension of Haskell's type classes that supports polymorphic variants directly. It has a novel form of instance declarations where records and variants are handled symmetrically.This type system can produce vanilla Haskell codes as a result of type inference. Therefore it behaves as a preprocessor which translates the extended language into plain Haskell. Programmers would be able to use polymorphic variants without worrying nasty problems such as ambiguities.

References

[1]
W. Burton, E. Meijer, P. Sansom, S. Thompson, and P.Wadler. Views: An extension to Haskell pattern matching, Oct. 1996. http://www.haskell.org/development/view.html.]]
[2]
K. Chen, P. Hudak, and M. Odersky. Parametric type classes. In ACM Conf. on LISP and Functional Programming, June 1992.]]
[3]
R. B. Findler and M. Flatt. Modular object-oriented programming with units and mixins. In Proceedings of the 1998 ACM SIGPLAN International Conference on Functional Programming (ICFP '98), 1998.]]
[4]
E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995.]]
[5]
J. Garrigue. Programming with polymorphic variants. In The 1998 ACM SIGPLAN Workshop on ML, Sept. 1998.]]
[6]
J. Garrigue. Code reuse through polymorphic variants. In Workshop on Foundations of Software Engineering (FOSE) 2000, Nov. 2000.]]
[7]
B. R. Gaster and M. P. Jones. A polymorphic type system for extensible records and variants. Technical Report Technical Report NOTTCS-TR-96-3, Computer Science, University of Nottingham, Nov. 1996.]]
[8]
T. Hallgren. Fun with functional dependencies. In Proceedings of the Joint CS/CE Winter Meeting, pages 135--145, Jan. 2001. http://www.cs.chalmers.se/~hallgren/Papers/wm01.html.]]
[9]
J. Hughes and J. Sparud. Haskell++: An object-oriented extension of Haskell. In Haskell Workshop 1995, 1995.]]
[10]
D. H. H. Ingalls. A simple technique for handling multiple polymorphism. In Conference proceedings on Object-oriented programming systems, languages and applications (OOPSLA) 1986, pages 347--349, 1986.]]
[11]
M. P. Jones. Qualified Types: Theory and Practice. PhD thesis, Programming Research Group, Oxford University Computing Laboratory, July 1992.]]
[12]
M. P. Jones. Simplifying and improving qualified types. Research Report YALEU/DCS/RR-1040, Yale University, June 1994.]]
[13]
M. P. Jones. Typing Haskell in Haskell. In Proceedings of the 1999 Haskell Workshop, pages 9--22, Oct. 1999.]]
[14]
M. P. Jones. Type classes with functional dependencies. In Proceedings of the 9th European Symposium on Programming, Mar. 2000. LNCS 1782.]]
[15]
K. Kagawa. Polymorphic variants in Haskell (prototype implementation), 2006. available from http://guppy.eng.kagawa-u.ac.jp/~kagawa/PVH.]]
[16]
O. Kiselyov, R. Lammel, and K. Schupke. Strongly typed heterogeneous collections. In Proc. of the ACM SIGPLAN Haskell Workshop 2004, pages 96--107, Sept. 2004.]]
[17]
K. Laufer. Type classes with existential types. Journal of Functional Programming, 6(3):485--517, May 1996.]]
[18]
S. Liang, P. Hudak, and M. Jones. Monad transformers and modular interpreters. In Conference Record of POPL'95: 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 333--343, Jan. 1995.]]
[19]
A. Loh and R. Hinze. Open data types and open functions. In Proceedings of the 8th ACM SIGPLAN symposium on Principle and Practice of Declarative Programming (PPDP 2006), July 2006.]]
[20]
C. McBride. Faking it (simulating dependent types in Haskell). Journal of Functional Programming, 12(4&5):375--392, 2002. Special Issue on Haskell.]]
[21]
E. Meijer and K. Claessen. The design and implementation of Mondrian. In Proceedings of Haskell Workshop 1997, 1997.]]
[22]
T. Millstein, C. Bleckner, and C. Chambers. Modular typechecking for hierarchically extensible datatypes and functions. In Proc. the 2002 ACM SIGPLAN International Conference on Functional Programming, pages 110--122, Oct. 2002.]]
[23]
J. Nordlander. Polymorphic subtyping in O'Haskell. In Proc. the APPSEm Workshop on Subtyping and Dependent Types in Programming, 2000. Ponte de Lima, Portugal.]]
[24]
M. Odersky, P. Wadler, and M. Wehr. A second look at overloading. In Proc. ACM Conf. on Functional Programming and Computer Architecture, pages 135--146, June 1995.]]
[25]
A. Ohori. A polymorphic record calculus and its compilation. ACM Transactions on Programming Languages and Systems, 17(6):844--895, Nov. 1995.]]
[26]
S. Peyton Jones, J. Hughes, et al. Haskell 98: A Non-strict, Purely Functional Language, Feb. 1999. http://www.haskell.org/onlinereport/.]]
[27]
S. Peyton Jones, M. Jones, and E. Meijer. Type classes: exploring the design space. In Haskell Workshop 1997, 1997.]]
[28]
S. Peyton Jones and M. Shields. Lexically scoped type variables, 2004.]]
[29]
S. Peyton Jones, D. Vytiniotis, S. Weirich, and G. Washburn. Simple unification-based type inference for GADTs. In Proceedings of the 11th ACM SIGPLAN International Conference on Functional Programming (ICFP 2006), 2006.]]
[30]
D. Remy. Typechecking records and variants in a natural extension of ML. In Annual ACM Symp. on Principles of Prog. Languages, pages 77--88, January 1989.]]
[31]
P. Wadler. Views: A way for pattern matching to cohabit with data abstraction. In Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 307--313, 1987.]]
[32]
M. Zenger and M. Odersky. Extensible algebraic datatypes with defaults. In Proceedings of the International Conference on Functional Programming, September 2001.]]
[33]
M. Zenger and M. Odersky. Independently extensible solutions to the expression problem. In Proceedings of the 12th International Workshop on Foundations of Object-Oriented Languages (FOOL 12), Jan. 2005.]]

Cited By

View all
  • (2014)Extending Type Inference to Variational ProgramsACM Transactions on Programming Languages and Systems10.1145/251819036:1(1-54)Online publication date: 1-Mar-2014
  • (2012)An error-tolerant type system for variational lambda calculusACM SIGPLAN Notices10.1145/2398856.236453547:9(29-40)Online publication date: 9-Sep-2012
  • (2012)An error-tolerant type system for variational lambda calculusProceedings of the 17th ACM SIGPLAN international conference on Functional programming10.1145/2364527.2364535(29-40)Online publication date: 9-Sep-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
Haskell '06: Proceedings of the 2006 ACM SIGPLAN workshop on Haskell
September 2006
131 pages
ISBN:1595934898
DOI:10.1145/1159842
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 September 2006

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Haskell
  2. extensibility
  3. polymorphic variants
  4. type classes

Qualifiers

  • Article

Conference

ICFP06
Sponsor:

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25
ACM SIGPLAN International Conference on Functional Programming
October 12 - 18, 2025
Singapore , Singapore

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)1
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2014)Extending Type Inference to Variational ProgramsACM Transactions on Programming Languages and Systems10.1145/251819036:1(1-54)Online publication date: 1-Mar-2014
  • (2012)An error-tolerant type system for variational lambda calculusACM SIGPLAN Notices10.1145/2398856.236453547:9(29-40)Online publication date: 9-Sep-2012
  • (2012)An error-tolerant type system for variational lambda calculusProceedings of the 17th ACM SIGPLAN international conference on Functional programming10.1145/2364527.2364535(29-40)Online publication date: 9-Sep-2012
  • (2008)Shared subtypesACM SIGPLAN Notices10.1145/1543134.141129744:2(75-86)Online publication date: 25-Sep-2008
  • (2008)Shared subtypesProceedings of the first ACM SIGPLAN symposium on Haskell10.1145/1411286.1411297(75-86)Online publication date: 25-Sep-2008

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media