Personal tools

Generics

From HaskellWiki

Revision as of 08:31, 21 April 2012 by Dreixel (Talk | contribs)

Jump to: navigation, search

Datatype-generic programming, also frequently just called generic programming or generics in Haskell, is a form of abstraction that allows defining functions that can operate on a large class of datatypes. In this page we summarise a number of popular approaches to generic programming that are often used with GHC. For a more in-depth introduction to generic programming in general, have a look at Gibbon's Datatype-Generic Programming, or the Libraries for Generic Programming paper.

Contents

1 What is generic programming?

Haskell is a polymorphic language. This means that you can have a single datatype for lists:

data List a = Nil | Cons a (List a)

These lists can contain any type of information, such as integers, Booleans, or even other lists. Since the length of a list does not depend on the type of its elements, there is also a single definition for list length:

length :: List a -> Int
length Nil        = 0
length (Cons _ t) = 1 + length t

However, it's not only lists that have length. Consider a datatype for trees:

data Tree a = Leaf | Bin a (Tree a) (Tree a)

You can also compute the length of a tree (or its size, if you want), by recursively traversing the tree and counting the number of elements. Generic programming allows to define a single length function, that can operate on lists, trees, and many other datatypes. This reduces code duplication and makes the code more robust to changes, because you can change your datatypes without needing to adapt the generic functions that operate on them.

We now look at some approaches to generic programming in Haskell.


2 GHC.Generics

See GHC.Generics.

3 SYB

4 Uniplate

5 Multirec