Abstract

(aka. Fixing the maths for real-world data types)

Functional programming continues to adopt concepts from category theory to provide abstraction mechanisms for structuring programs. For example, many parametrically polymorphic data types are instances of functors and monads. Other parametric data types have their polymorphism restricted for implementation efficiency e.g. unboxed arrays require primitive element types Int, Float, etc. Traditionally, mathematical abstractions in Haskell are endofunctor-based, however such data types do not fit this model. This paper instead interprets restricted polymorphism as subcategory specification. Notions of functors, monads and comonads are redefined over (full and non-full ) subcategories, providing non-endofunctors (with distinct source and target categories), relative monads and relative comonads. These structures not only provide a more accurate model of restricted polymorphism but can also be defined within Haskell itself using GHC ’s new constraint kinds extension.

This is a practice talk for TFP ’12. Joint work with Alan Mycroft.