Datatype generic programming

GHC Generics provide a nice interface for datatype generic programming. The core idea is that every datatype is representable as a sum of products. The GHC.Generics module defines a small sufficient set of datatypes. The unit type represents constructors with no arguments:

data U1 p = U1 -- unit

The V1 datatype, on the other hand, represents types with no constructors (empty):

data V1 p -- empty

Sums and products are represented respectively by the following types:

(:+:) f g p = L1 (f p) | R1 (g p) -- sum
(:*:) f g p = f p :*: g p         -- product

The sum types with more than two constructors are represented by the recursive application of (:+:), and it's a similar case for the product types.

The K1 datatype acts as a container for values (of type c):

newtype K1 i c p = K1 { unK1 :: c } -- container

The final datatype is a metadata wrapper:

newtype M1 i t f p = M1 { unM1 :: f p }  -- metadata wrapper

The Generic type class glues arbitrary Haskell datatypes to their representations...