Manuel M T Chakravarty
University of New South Wales

Title: Generic Programming with Type Families

The most common form of generic programming is concerned with generic
functions that operate on a set of data types in a uniform manner - e.g.,
generic maps that apply to a range of container types, such as lists and
trees.  Less common is generic programming with generic data types, where the
structure of a generic data type is determined by a type, much like the
control flow of a generic function is determined by a type.  In this talk, I
will illustrate the idea behind generic data types at the example of finite
maps whose structure depends on the key type - Hinze introduced these finite
maps as generic generalised tries.

C++ has supported generic data types for a while in the form of template
classes, and the the Glasgow Haskell Compiler (GHC) has recently added support
for generic data types in the form of data families.  However, both of these
systems lack the comprehensive support provided by Generic Haskell.  The
unique feature of Generic Haskell, where generic data types are called
type-indexed data types, is the automatic derivation of generic data types by
following the algebraic structure of the index type.  In this talk, I will
demonstrate that we can achieve a similar level of expressivity by combining
data families with type synonym families, the latest type-level addition to
GHC.

This is joint work with Gabriele Keller, Roman Leshchinskiy, and Simon Peyton
Jones.