Type inference for the spine view of data

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

Abstract

In this work we describe both a type checking and a type inference algorithm for generic programming using the spine view of data. The spine view of data is an approach to decomposing data in functional programming languages that supports generic programming in the style of Scrap Your Boilerplate and Stratego. The spine view of data has previously been described as a library in a statically typed language (as in Haskell), as a language feature in a dynamically typed language (as in Stratego), and as a calculus of patterns (as in the Pattern Calculus). The contribution of this paper is a type inference algorithm for the spine view and a type relation that underlies this inference algorithm. In contrast to all other typed implementations of the spine view, the type inference algorithm does not require any type annotations to be added in support of the spine view. This type inference algorithm is an extension of Hindley-Milner type inference, thus showing how to introduce the spine view of data as a language feature in any functional programming language based on Hindley-Milner.

Original languageEnglish
Title of host publicationWGP 2014 - Proceedings of the 2014 ACM SIGPLAN Workshop on Generic Programming
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Pages25-34
Number of pages10
ISBN (Print)9781450330381
DOIs
Publication statusPublished - 2014
Event10th ACM SIGPLAN Workshop on Generic Programming, WGP 2014 - Gothenburg, Sweden
Duration: 31 Aug 201431 Aug 2014

Other

Other10th ACM SIGPLAN Workshop on Generic Programming, WGP 2014
CountrySweden
CityGothenburg
Period31/08/1431/08/14

Fingerprint Dive into the research topics of 'Type inference for the spine view of data'. Together they form a unique fingerprint.

  • Cite this

    Roberts, M., & Sloane, A. (2014). Type inference for the spine view of data. In WGP 2014 - Proceedings of the 2014 ACM SIGPLAN Workshop on Generic Programming (pp. 25-34). New York: Association for Computing Machinery. https://doi.org/10.1145/2633628.2633629