More Web Proxy on the site http://driver.im/

research-article

Type families with class, type classes with family

Authors:

Alejandro Serrano,

Patrick BahrAuthors Info & Claims

Haskell '15: Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell

Pages 129 - 140

https://doi.org/10.1145/2804302.2804304

Published: 30 August 2015 Publication History

Abstract

Type classes and type families are key ingredients in Haskell programming. Type classes were introduced to deal with ad-hoc polymorphism, although with the introduction of functional dependencies, their use expanded to type-level programming. Type families also allow encoding type-level functions, but more directly in the form of rewrite rules. In this paper we show that type families are powerful enough to simulate type classes (without overlapping instances), and we provide a formal proof of the soundness and completeness of this simulation. Encoding instance constraints as type families eases the path to proposed extensions to type classes, like closed sets of instances, instance chains, and control over the search procedure. The only feature which type families cannot simulate is elaboration, that is, generating code from the derivation of a rewriting. We look at ways to solve this problem in current Haskell, and propose an extension to allow elaboration during the rewriting phase.

References

[1]

P. Bahr. Composing and Decomposing Data Types: A Closed Type Families Implementation of Data Types à la Carte. In Proceedings of the 10th ACM SIGPLAN Workshop on Generic Programming, pages 71–82, New York, NY, USA, Aug. 2014. ACM.

Digital Library

[2]

E. Brady. Idris, a general-purpose dependently typed programming language: Design and implementation. Journal of Functional Programming, 23:552–593, 9 2013.

[3]

D. Devriese and F. Piessens. On the Bright Side of Type Classes: Instance Arguments in Agda. In Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming, pages 143–155, New York, NY, USA, 2011. ACM.

Digital Library

[4]

I. S. Diatchki. High-level abstractions for low-level programming. PhD thesis, OGI School of Science & Engineering, May 2007.

[5]

A. Dijkstra, G. van den Geest, B. Heeren, and S. D. Swierstra. Modelling Scoped Instances with Constraint Handling Rules. Technical report, Department of Information and Computing Sciences, Utrecht University, 2007.

[6]

R. A. Eisenberg, D. Vytiniotis, S. Peyton Jones, and S. Weirich. Closed Type Families with Overlapping Equations. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 671–683, New York, NY, USA, 2014. ACM.

Digital Library

[7]

J. Hage. DOMain Specific Type Error Diagnosis (DOMSTED). Technical Report UU-CS-2014-019, Department of Information and Computing Sciences, Utrecht University, 2014.

[8]

B. Heeren and J. Hage. Type class directives. In Proceedings of the 7th International Conference on Practical Aspects of Declarative Languages, pages 253–267, Berlin, Heidelberg, 2005. Springer-Verlag.

Digital Library

[9]

M. Izbicki. A neat trick for partially closed type families. Available at http://izbicki.me/blog/ a-neat-trick-for-partially-closed-type-families, 2014.

[10]

M. Jones. Type classes with functional dependencies. In G. Smolka, editor, Programming Languages and Systems, volume 1782 of Lecture Notes in Computer Science, pages 230–244. Springer Berlin Heidelberg, 2000.

Digital Library

[11]

O. Kiselyov. Stretching type classes. Retrieved from http://okmij. org/ftp/Haskell/TypeClass.html, May 2015.

[12]

O. Kiselyov, R. Lämmel, and K. Schupke. Strongly typed heterogeneous collections. In Proceedings of the 2004 ACM SIGPLAN Workshop on Haskell, pages 96–107, New York, NY, USA, 2004. ACM.

Digital Library

[13]

J. G. Morris and M. P. Jones. Instance chains: type class programming without overlapping instances. In Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, pages 375–386, New York, NY, USA, 2010. ACM.

Digital Library

[14]

S. Peyton Jones, M. Jones, and E. Meijer. Type classes: exploring the design space. In Haskell Workshop, 1997.

[15]

T. Schrijvers, M. Sulzmann, S. Peyton Jones, and M. Chakravarty. Towards open type functions for Haskell. In O. Chitil, editor, 19th International Symposium on Implementation and Application of Functional Languages, pages 233–251. Computing Laboratory, University of Kent, 2007.

[16]

A. Serrano, J. Hage, and P. Bahr. Type Families with Class, Type Classes with Family. Technical report. To appear.

[17]

P. J. Stuckey and M. Sulzmann. A theory of overloading. ACM Trans. Program. Lang. Syst., 27(6):1216–1269, Nov. 2005. ISSN 0164-0925.

Digital Library

[18]

M. Sulzmann, G. J. Duck, S. Peyton-Jones, and P. J. Stuckey. Understanding functional dependencies via constraint handling rules. J. Funct. Program., 17(1):83–129, Jan. 2007. ISSN 0956-7968.

Digital Library

[19]

W. Swierstra. Data types à la carte. Journal of Functional Programming, 18(4):423–436, July 2008.

Digital Library

[20]

The Idris Community. Programming in Idris: A Tutorial. Available from http://eb.host.cs.st-andrews.ac.uk/writings/ idris-tutorial.pdf, 2014.

[21]

D. Vytiniotis, S. Peyton Jones, T. Schrijvers, and M. Sulzmann. OutsideIn(X): Modular Type Inference with Local Assumptions. Journal of Functional Programming, 21(4-5):333–412, Sept. 2011.

Digital Library

[22]

P. Wadler and S. Blott. How to Make Ad-hoc Polymorphism Less Ad Hoc. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 60–76, New York, NY, USA, 1989. ACM.

Digital Library

Cited By

Serrano ACorpa FSchrijvers T(2020)Describing microservices using modern Haskell (experience report)Proceedings of the 13th ACM SIGPLAN International Symposium on Haskell10.1145/3406088.3409018(1-8)Online publication date: 27-Aug-2020
https://dl.acm.org/doi/10.1145/3406088.3409018
Karachalias GSchrijvers T(2017)Elaboration on functional dependencies: functional dependencies are dead, long live functional dependencies!ACM SIGPLAN Notices10.1145/3156695.312296652:10(133-147)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3156695.3122966
Karachalias GSchrijvers TDiatchki I(2017)Elaboration on functional dependencies: functional dependencies are dead, long live functional dependencies!Proceedings of the 10th ACM SIGPLAN International Symposium on Haskell10.1145/3122955.3122966(133-147)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122955.3122966
Show More Cited By

Index Terms

Type families with class, type classes with family
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
      2. Language types
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs

Recommendations

Type families with class, type classes with family
Haskell '15

Type classes and type families are key ingredients in Haskell programming. Type classes were introduced to deal with ad-hoc polymorphism, although with the introduction of functional dependencies, their use expanded to type-level programming. Type ...
Constrained type families

We present an approach to support partiality in type-level computation without compromising expressiveness or type safety. Existing frameworks for type-level computation either require totality or implicitly assume it. For example, type families in ...
Bidirectional type class instances
Haskell 2019: Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell

GADTs were introduced in Haskell’s eco-system more than a decade ago, but their interaction with several mainstream features such as type classes and functional dependencies has a lot of room for improvement. More specifically, for some GADTs it can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '15: Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell

August 2015

212 pages

ISBN:9781450338080

DOI:10.1145/2804302

Program Chair:
Ben Lippmeier

ACM SIGPLAN Notices Volume 50, Issue 12
Haskell '15
December 2015
212 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2887747
Editor:
Matthew Fluet
Rochester Institute of Technology
Issue’s Table of Contents

Copyright © 2015 ACM.

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 the author(s) 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

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

ICFP'15

Sponsor:

SIGPLAN

ICFP'15: 20th ACM SIGPLAN International Conference on Functional Programming

September 3 - 4, 2015

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 57 of 143 submissions, 40%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
260
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Serrano ACorpa FSchrijvers T(2020)Describing microservices using modern Haskell (experience report)Proceedings of the 13th ACM SIGPLAN International Symposium on Haskell10.1145/3406088.3409018(1-8)Online publication date: 27-Aug-2020
https://dl.acm.org/doi/10.1145/3406088.3409018
Karachalias GSchrijvers T(2017)Elaboration on functional dependencies: functional dependencies are dead, long live functional dependencies!ACM SIGPLAN Notices10.1145/3156695.312296652:10(133-147)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3156695.3122966
Karachalias GSchrijvers TDiatchki I(2017)Elaboration on functional dependencies: functional dependencies are dead, long live functional dependencies!Proceedings of the 10th ACM SIGPLAN International Symposium on Haskell10.1145/3122955.3122966(133-147)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122955.3122966
Gibbons J(2017)APLicative Programming with Naperian FunctorsProgramming Languages and Systems10.1007/978-3-662-54434-1_21(556-583)Online publication date: 19-Mar-2017
https://doi.org/10.1007/978-3-662-54434-1_21
Gibbons J(2017)APLicative Programming with Naperian FunctorsProgramming Languages and Systems10.1007/978-3-662-54434-1_21(556-583)Online publication date: 19-Mar-2017
https://doi.org/10.1007/978-3-662-54434-1_21

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents