Matthew Roberts
Macquarie University

Type Inference for the Spine View of Data

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 work is a type inference
algorithm for the spine view and a sound type relation that underlies this
inference algorithm.  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.