Higher-Kinded Types.pdf

Type constructor polymorphism allows abstracting over type constructors, enabling more expressive and flexible programming. In Scala, this feature is achieved through higher-kinded types, which enable type constructors to be passed as type arguments to other type constructors. This generalization of first-order parametric polymorphism has numerous practical applications, including comprehensions, parser combinators, and embedded Domain-Specific Languages (DSLs).

The main contributions of this work include:

1. Illustrating the utility of type constructor polymorphism: A realistic example demonstrates the reduction of boilerplate code and increased expressivity.
2. Developing a kind system: A kind system is introduced to capture lower and upper bounds, as well as variances of types, ensuring sound and flexible type constructor polymorphism.
3. Surveying integration with existing features: The interaction between type constructor polymorphism and existing Scala features, such as subtyping, definition-site variance annotations, and implicit arguments, is explored.
4. Implementing the kind system: The experience of implementing the kind system in the open-source Scala compiler is reported, highlighting the practicality of the design.

Key aspects of type constructor polymorphism in Scala include:

Higher-kinded types: Type constructors can be abstracted over, enabling more flexible and expressive programming.
Kind system: A kind system is used to ensure sound and flexible type constructor polymorphism.
Integration with existing features: Type constructor polymorphism interacts with existing Scala features, such as subtyping, definition-site variance annotations, and implicit arguments.

The benefits of type constructor polymorphism in Scala include:

Reduced boilerplate code: Type constructor polymorphism enables more concise and expressive programming, reducing the need for boilerplate code.
Increased expressivity: Type constructor polymorphism allows for more flexible and expressive programming, enabling the creation of more complex and abstract data types.
Improved code reuse: Type constructor polymorphism enables more code reuse, as type constructors can be abstracted over and reused in different contexts.