Instant Generics: Fast and Easy

Manuel M. T. Chakravarty, Gabriel C. Ditu, and Roman Leshchinskiy.

Submitted, 2009.

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 type-indexed 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.

PDF (11 pages)

This page is part of Manuel Chakravarty's WWW-stuff.