Article

Strongly typed heterogeneous collections

Authors:

Keean SchupkeAuthors Info & Claims

Haskell '04: Proceedings of the 2004 ACM SIGPLAN workshop on Haskell

Pages 96 - 107

https://doi.org/10.1145/1017472.1017488

Published: 22 September 2004 Publication History

Abstract

A heterogeneous collection is a datatype that is capable of storing data of different types, while providing operations for look-up, update, iteration, and others. There are various kinds of heterogeneous collections, differing in representation, invariants, and access operations. We describe HLIST - a Haskell library for strongly typed heterogeneous collections including extensible records. We illustrate HLIST's benefits in the context of type-safe database access in Haskell. The HLIST library relies on common extensions of Haskell 98. Our exploration raises interesting issues regarding Haskell's type system, in particular, avoidance of overlapping instances, and reification of type equality and type unification.

References

[1]

This paper's web site http://www.cwi.nl/~ralf/HList/, 2004. This site provides an extended paper version with extra appendicies that could not be included into the Haskell workshop paper. This site also provides a source code distribution for the GHC and Hugs implementations of Haskell.]]

[2]

M. Abadi, L. Cardelli, B. Pierce, and G. Plotkin. Dynamic typing in a statically-typed language. In 16th ACM Conference on Principles of Programming Languages, pages 213--227, Jan. 1989.]]

Digital Library

[3]

M. Abadi, L. Cardelli, B. Pierce, and D. Remy. Dynamic typing in polymorphic languages. In Proceedings of the 1992 ACM Workshop on ML and its Applications, pages 92--103, San Francisco, June 1992.]]

[4]

A. Baars and S. Swierstra. Typing dynamic typing. In Proceedings of the seventh ACM SIGPLAN International Conference on Functional Programming, pages 157--166. ACM Press, 2002.]]

Digital Library

[5]

G. Bracha and G. Lindstrom. Modularity Meets Inheritance. In Proceedings: 4th International Conference on Computer Languages, pages 282--290. IEEE Computer Society Press, 1992.]]

[6]

F. Burton. Type extension through polymorphism. TOPLAS, 12(1):135--138, 1990.]]

Digital Library

[7]

K. Chen, P. Hudak, and M. Odersky. Parametric type classes. In Proceedings of the 1992 ACM Conference on LISP and Functional Programming, pages 170--181. ACM Press, 1992.]]

Digital Library

[8]

J. Cheney and R. Hinze. A lightweight implementation of generics and dynamics. In Proceedings of the ACM SIGPLAN Workshop on Haskell, pages 90--104. ACM Press, 2002.]]

Digital Library

[9]

G. Duck, S. Peyton Jones, P. Stuckey, and M. Sulzmann. Sound and Decidable Type Inference for Functional Dependencies. In D. Schmidt, editor, Proceedings, 13th European Symposium on Programming, ESOP 2004, Barcelona, Spain, March 29 - April 2, 2004, volume 2986 of LNCS, pages 49--63. Springer-Verlag, 2004.]]

[10]

B. Gaster and M. Jones. A Polymorphic Type System for Extensible Records and Variants. Technical report NOTTCS-TR-96-3, University of Nottingham, Department of Computer Science, Nov. 1996.]]

[11]

H. Nilsson. The Future of Haskell discussion at the Haskell Workshop, 2003. http://www.mail-archive.com/haskell\@haskell.org/msg13366.html.]]

[12]

T. Hallgren. Fun with functional dependencies. In Joint Winter Meeting of the Departments of Science and Computer Engineering, Chalmers University of Technology and Goteborg University, Varberg, Sweden, Jan. 2001, 2001. http://www.cs.chalmers.se/~hallgren/Papers/wm01.html.]]

[13]

R. Harper and G. Morrisett. Compiling polymorphism using intensional type analysis. In 22nd ACM Symposium on Principles of Programming Languages (POPL'95), pages 130--141. ACM Press, Jan. 1995.]]

Digital Library

[14]

E. W. J. Van den Bussche. Polymorphic type inference for the relational algebra. Journal of Computer and System Sciences, 64:694--718, 2002. An extended abstract appeared in PODS'99.]]

Digital Library

[15]

M. Jones. A theory of qualified types. In Symposium proceedings on 4th European symposium on programming, pages 287--306. Springer-Verlag, 1992.]]

Digital Library

[16]

M. Jones. Simplifying and improving qualified types. In Proceedings of the seventh international conference on Functional Programming Languages and Computer Architecture, pages 160--169. ACM Press, 1995.]]

Digital Library

[17]

M. Jones. Type classes with functional dependencies. In Proceedings of the 9th European Symposium on Programming Languages and Systems, pages 230--244. Springer-Verlag, 2000.]]

Digital Library

[18]

R. Lämmel and S. Peyton Jones. Scrap your boilerplate: a practical design pattern for generic programming. ACM SIGPLAN Notices, 38(3):26--37, Mar. 2003. Proc. of the ACM SIGPLAN Workshop TLDI 2003.]]

Digital Library

[19]

D. Leijen and E. Meijer. Domain specific embedded compilers. In Proceedings of the 2nd conference on Domain-Specific Languages, pages 109--122. ACM Press, 1999.]]

Digital Library

[20]

C. McBride. Faking It (Simulating Dependent Types in Haskell), July 2002.]]

Digital Library

[21]

M. Neubauer, P. Thiemann, M. Gasbichler, and M. Sperber. A Functional Notation for Functional Dependencies. In Proc. 2001 ACM SIGPLAN Haskell Workshop, Firenze, Italy, September 2001, pages 101--120, 2001.]]

[22]

M. Neubauer, P. Thiemann, M. Gasbichler, and M. Sperber. Functional logic overloading. In Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of Programming languages, pages 233--244. ACM Press, 2002.]]

Digital Library

[23]

A. Ohori. A polymorphic record calculus and its compilation. ACM TOPLAS, 17(6):844--895, 1995.]]

Digital Library

[24]

C. Okasaki. From fast exponentiation to square matrices: an adventure in types. In Proceedings of the fourth ACM SIGPLAN International Conference on Functional Programming, pages 28--35. ACM Press, 1999.]]

Digital Library

[25]

C. Okasaki. An Overview of Edison. In G. Hutton, editor, Electronic Notes in Theoretical Computer Science, volume 41. Elsevier, 2001.]]

[26]

S. Peyton Jones. Adding Ord constraint to instance Monad Set?, 2004. http://www.haskell.org/pipermail/haskell-cafe/2004-March/005998.html.]]

[27]

S. Peyton Jones, M. Jones, and E. Meijer. Type classes: exploring the design space. In J. Launchbury, editor, Haskell workshop, Amsterdam, 1997.]]

[28]

S. Peyton Jones and G. Morrisett. A proposal for records in Haskell, 24 Feb. 2003. Online document: http://research.microsoft.com/~simonpj/Haskell/records.html.]]

[29]

D. Remy. Type inference for records in natural extension of ml. In Theoretical aspects of object-oriented programming: types, semantics, and language design, pages 67--95. MIT Press, 1994.]]

Digital Library

[30]

M. Shields and E. Meijer. Type-indexed rows. In Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pages 261--275. ACM Press, 2001.]]

Digital Library

[31]

P. Stuckey and M. Sulzmann. A theory of overloading. In Proceedings of the seventh ACM SIGPLAN International Conference on Functional Programming, pages 167--178. ACM Press, 2002.]]

Digital Library

[32]

M. Sulzmann et al. Chameleon, 2004. Web site http://www.comp.nus.edu.sg/~sulzmann/chameleon/.]]

[33]

S. Weirich. Type-safe cast: (functional pearl). In Proceedings of the fifth ACM SIGPLAN International Conference on Functional Programming, pages 58--67. ACM Press, 2000.]]

Digital Library

[34]

H. Xi and F. Pfenning. Dependent types in practical programming. In Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pages 214--227. ACM Press, 1999.]]

Digital Library

[35]

Z. Yang. Encoding types in ML-Like languages. In M. Berman and S. Berman, editors, Proceedings of the third ACM SIGPLAN International Conference on Functional Programming (ICFP'98), volume 34, 1 of ACM SIGPLAN Notices, pages 289-300, New York, Sept. 27--29 1998. ACM Press.]]

Digital Library

Cited By

Keating FGale MVazou NMorris J(2024)Functional Reactive Programming, RearrangedProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678278(55-67)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678278
Rinaldi Fwunder jAzevedo de Amorim AMuller S(2024)Pipelines and Beyond: Graph Types for ADTs with FuturesProceedings of the ACM on Programming Languages10.1145/36328598:POPL(482-511)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632859
Koopman PLubbers M(2023)Strongly-Typed Multi-View Stack-Based ComputationsProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610623(1-12)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3610612.3610623
Show More Cited By

Index Terms

Strongly typed heterogeneous collections

Recommendations

Dependently typed programming with singletons
Haskell '12

Haskell programmers have been experimenting with dependent types for at least a decade, using clever encodings that push the limits of the Haskell type system. However, the cleverness of these encodings is also their main drawback. Although the ideas ...
Dependently typed programming with singletons
Haskell '12: Proceedings of the 2012 Haskell Symposium

Haskell programmers have been experimenting with dependent types for at least a decade, using clever encodings that push the limits of the Haskell type system. However, the cleverness of these encodings is also their main drawback. Although the ideas ...
Typing dynamic typing

Even when programming in a statically typed language we every now and then encounter statically untypable values; such values result from interpreting values or from communicating with the outside world. To cope with this problem most languages include ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Haskell '04: Proceedings of the 2004 ACM SIGPLAN workshop on Haskell

September 2004

122 pages

ISBN:1581138504

DOI:10.1145/1017472

Program Chair:
Henrik Nilsson
University of Nottingham, UK

Copyright © 2004 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 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: 22 September 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

HW04

Sponsor:

HW04: Haskell Workshop 2004

September 22, 2004

Utah, Snowbird, USA

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

151
Total Citations
View Citations
879
Total Downloads

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

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Keating FGale MVazou NMorris J(2024)Functional Reactive Programming, RearrangedProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678278(55-67)Online publication date: 29-Aug-2024
https://dl.acm.org/doi/10.1145/3677999.3678278
Rinaldi Fwunder jAzevedo de Amorim AMuller S(2024)Pipelines and Beyond: Graph Types for ADTs with FuturesProceedings of the ACM on Programming Languages10.1145/36328598:POPL(482-511)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632859
Koopman PLubbers M(2023)Strongly-Typed Multi-View Stack-Based ComputationsProceedings of the 25th International Symposium on Principles and Practice of Declarative Programming10.1145/3610612.3610623(1-12)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1145/3610612.3610623
Crichton WSperber MHutton G(2023)Typed Design Patterns for the Functional EraProceedings of the 1st ACM SIGPLAN International Workshop on Functional Software Architecture10.1145/3609025.3609477(40-48)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609025.3609477
Liu YWeirich S(2023)Dependently-Typed Programming with Logical Equality ReflectionProceedings of the ACM on Programming Languages10.1145/36078527:ICFP(649-685)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607852
Hubers AMorris J(2023)Generic Programming with Extensible Data Types: Or, Making Ad Hoc Extensible Data Types Less Ad HocProceedings of the ACM on Programming Languages10.1145/36078437:ICFP(356-384)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607843
Matsuda KFrohlich SWang MWu N(2023)Embedding by UnembeddingProceedings of the ACM on Programming Languages10.1145/36078307:ICFP(1-47)Online publication date: 31-Aug-2023
https://dl.acm.org/doi/10.1145/3607830
Blanvillain O(2022)Type-safe regular expressionsProceedings of the Scala Symposium10.1145/3550198.3550425(1-8)Online publication date: 6-Jun-2022
https://dl.acm.org/doi/10.1145/3550198.3550425
Guria SVazou NGuarnieri MParker JJhala RDillig I(2022)ANOSY: approximated knowledge synthesis with refinement types for declassificationProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523725(15-30)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523725
Blanvillain OBrachthäuser JKjaer MOdersky M(2022)Type-level programming with match typesProceedings of the ACM on Programming Languages10.1145/34986986:POPL(1-24)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498698
Show More Cited By

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