Generic Programming in Haskell: Simple, Powerful & Fast

Instant Generics (IG) is an approach to datatype-generic programming in Haskell based on type classes and type families. Datatype-generic functions operate on entire families of datatypes in a non-parametric, but uniform manner, guided by the type structure of consumed and produced data structures. IG also supports datatype-generic datatypes (also called type-indexed datatypes.) In the terminology of Generic Haskell, datatype-generic functions and datatypes are polytypic functions and datatypes.

Simplicity

In IG, datatype-generic functions are simply class methods. These class methods are mostly straight forward and avoid sophisticated type-level programming. Moreover, by using type families, we avoid complicated encodings of representations types. We are currently providing a simple Template Haskell script to generate representation type instances. We are planning to further automate the coding of generic boilerplate in the future.

Power

IG supports higher-kinded and mutually-recursive datatypes. It provides first-class generic functions, abstraction over type constructors, and permits separate compilation. Moreover, ad-hoc definitions for specific datatypes and data constructors is straight forward. As IG is based on two open declaration forms — type classes and type families — it is easily extensible: both generic functions and datatypes, and even representations, can always be further extended in subsequent modules without any need to change or even re-compile existing code.

Performance

In contrast to many other generics libraries for Haskell, a central design goal of IG was efficiency. We originally developed IG for Data Parallel Haskell, an extension to the Glasgow Haskell Compiler (GHC) for high-performance array code and portable parallel programming, specifically targetting multicore architectures. Initial experiments suggest that IG is the fastest approach to generics in Haskell, with the exception of Derivable Type Classes, which exhibit similar performance, but have rather restricted functionality.

The table to the right displays the results of preliminary benchmarks that compare IG to hand-written (non-generic) code, the original Scrap Your Boilerplate (SYB) system, and the optimised Smash library. IG is consistently the fastest of the three generics libraries and in most cases close to hand-written, non-generic code. For details on the benchmark programs, see Alexey Rodriguez, Johan Jeuring, Patrik Jansson, Alex Gerdes, Oleg Kiselyov, and Bruno C. d. S. Oliveira. Comparing libraries for generic programming in Haskell. In Haskell '08: Proceedings of the first ACM SIGPLAN Symposium on Haskell, pages 111–122. ACM Press, 2008.

Anything else?

Instant Generics are described in much greater detail in the paper Instant Generics: Fast and Easy. Source code illustrating IG using some of the generics benchmarks is available as ig-0.1.tar.gz.

People (alphabetically)

• Copyright 2009 Manuel M T Chakravarty • Last modified: 29 May 2009