Towards higher-order types.

Abstract

This article explores the use of types constrained by the definition of functions of given types. This notion supports both overloading and a form of subtyping, and is related to Haskell type classes and System O. We study an extension of the Damas-Milner system, in which overloaded functions can be defined. The inference system presented uses a context-independent overloading policy, specified by means of a predicate used in a single inference rule. The treatment of overloading is less restrictive than in similar systems. Type annotations are not required, but can be used to simplify inferred types. The work motivates the use of constrained types as parameters of other, higher-order types.