Instant Generics: Fast and Easy

Abstract

This paper introduces a novel approach to datatype-generic programming based on type classes and type families. The approach favours simplicity as generic functions are based on Haskell’s standard construct for ad-hoc polymorphism, namely type classes — hence, it integrates well with existing classes and facilitates overriding of generic behaviour with conventional class instances. Moreover, our approach is expressive, as we demonstrate by an evaluation along the criteria of a set of standard benchmark problems for generic programming in Haskell. Beyond these benchmarks, which only cover type-indexed functions, we fully support typeindexed data types as well as a novel generic view, which we call the structural view. Finally, our approach is designed to lead to highly efficient code with no or little overhead compared to handwritten datatype-specific code. Both, support for type-indexed data types and high performance were crucial in our principal application: a self-optimising, high-performance array library for data parallel programming in Haskell.