Personal tools

Generics

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Grammar)
 
(2 intermediate revisions by one user not shown)
Line 1: Line 1:
''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 [http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/dgp.pdf Datatype-Generic Programming], or the [http://dreixel.net/research/pdf/lgph.pdf Libraries for Generic Programming] paper.
+
''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 Gibbons' [http://www.comlab.ox.ac.uk/jeremy.gibbons/publications/dgp.pdf Datatype-Generic Programming], or the [http://dreixel.net/research/pdf/lgph.pdf Libraries for Generic Programming] paper.
   
 
== What is generic programming? ==
 
== What is generic programming? ==
Line 14: Line 14:
 
</haskell>
 
</haskell>
   
However, it's not only lists that have length. Consider a datatype for trees:
+
The length function can be defined on other datatypes than lists. Consider a datatype for trees:
 
<haskell>
 
<haskell>
 
data Tree a = Leaf | Bin a (Tree a) (Tree a)
 
data Tree a = Leaf | Bin a (Tree a) (Tree a)
 
</haskell>
 
</haskell>
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.
+
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 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.
 
We now look at some approaches to generic programming in Haskell.
Line 37: Line 37:
   
 
Multirec is a library for generic programming with fixed points, supporting mutually recursive families of datatypes, and allowing functionality such as folds or the zipper. For more information, [http://www.cs.uu.nl/wiki/GenericProgramming/Multirec see its webpage].
 
Multirec is a library for generic programming with fixed points, supporting mutually recursive families of datatypes, and allowing functionality such as folds or the zipper. For more information, [http://www.cs.uu.nl/wiki/GenericProgramming/Multirec see its webpage].
  +
  +
== RepLib ==
  +
  +
Replib is a library for generic programming based on representation types (and GADTs). It is available through [http://hackage.haskell.org/package/RepLib-0.5.2.1 Hackage] and [http://code.google.com/p/replib/ Google Code]. It is one of the more expressive libraries and supports the SYB traversals as well as other styles of generic programming. The [http://hackage.haskell.org/package/unbound Unbound library] uses RepLib to automatically derive operations for name binding, including alpha-equivalence, free variable calculation and substitution.

Latest revision as of 13:11, 23 April 2012

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 Gibbons' Datatype-Generic Programming, or the Libraries for Generic Programming paper.

Contents

[edit] 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

The length function can be defined on other datatypes than lists. 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 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.

[edit] 2 GHC.Generics

The
GHC.Generics
module, available with GHC since version 7.2, allows you to easily define classes with methods for which no implementation is necessary, similarly to
Show
, for instance. It's described in a separate wiki page.

[edit] 3 SYB

Scrap Your Boilerplate (SYB), available with GHC since version 6.0, is an earlier approach to generic programming, particularly well suited for traversals and transformations over large trees. It has its own wiki page.

[edit] 4 Uniplate

Uniplate is available as a library on Hackage. It is similar in nature to SYB, but uses simpler types. For more information see its webpage.

[edit] 5 Multirec

Multirec is a library for generic programming with fixed points, supporting mutually recursive families of datatypes, and allowing functionality such as folds or the zipper. For more information, see its webpage.

[edit] 6 RepLib

Replib is a library for generic programming based on representation types (and GADTs). It is available through Hackage and Google Code. It is one of the more expressive libraries and supports the SYB traversals as well as other styles of generic programming. The Unbound library uses RepLib to automatically derive operations for name binding, including alpha-equivalence, free variable calculation and substitution.