A Fresh Look at Parametric Polymorphism: Covariant Types

C. Barry Jay
School of Computing Sciences, University of Technology, Sydney
cbj@socs.uts.edu.au

Abstract

The covariant type system is rich enough to represent polymorphism on inductive types, such as lists and trees, and yet is simple enough to have a set-theoretic semantics. Its chief novelty is to replace function types by transformation types, which denote parametric functions. Their free type variables are all in positive positions, and so can be modelled by covariant functors. Similarly, terms denote natural transformations.

There is a translation from the covariant type system to system F which preserves non-trivial reductions. Consequently, covariant reduction is strongly normalising and confluent.

Conference Home Page