Editing Generic programming (section)

====Genericity in Haskell====
The [[type class]] mechanism of [[Haskell]] supports generic programming. Six of the predefined type classes in Haskell (including <code>Eq</code>, the types that can be compared for equality, and <code>Show</code>, the types whose values can be rendered as strings) have the special property of supporting ''derived instances.'' This means that a programmer defining a new type can state that this type is to be an instance of one of these special type classes, without providing implementations of the class methods as is usually necessary when declaring class instances. All the necessary methods will be "derived" – that is, constructed automatically – based on the structure of the type. For example, the following declaration of a type of [[binary tree]]s states that it is to be an instance of the classes <code>Eq</code> and <code>Show</code>:

<syntaxhighlight lang="haskell">
data BinTree a = Leaf a | Node (BinTree a) a (BinTree a)
      deriving (Eq, Show)
</syntaxhighlight>

This results in an equality function (<code>==</code>) and a string representation function (<code>show</code>) being automatically defined for any type of the form <code>BinTree T</code> provided that <code>T</code> itself supports those operations.

The support for derived instances of <code>Eq</code> and <code>Show</code> makes their methods <code>==</code> and <code>show</code> generic in a qualitatively different way from parametrically polymorphic functions: these "functions" (more accurately, type-indexed families of functions) can be applied to values of various types, and although they behave differently for every argument type, little work is needed to add support for a new type. Ralf Hinze (2004) has shown that a similar effect can be achieved for user-defined type classes by certain programming techniques. Other researchers have proposed approaches to this and other kinds of genericity in the context of Haskell and extensions to Haskell (discussed below).

===== PolyP =====
PolyP was the first generic programming language extension to [[Haskell]]. In PolyP, generic functions are called ''polytypic''. The language introduces a special construct in which such polytypic functions can be defined via structural induction over the structure of the pattern functor of a regular datatype. Regular datatypes in PolyP are a subset of Haskell datatypes. A regular datatype t must be of [[Kind (type theory)|kind]] ''* → *'', and if ''a'' is the formal type argument in the definition, then all recursive calls to ''t'' must have the form ''t a''. These restrictions rule out higher-kinded datatypes and nested datatypes, where the recursive calls are of a different form.
The flatten function in PolyP is here provided as an example:

<syntaxhighlight lang="haskell">
   flatten :: Regular d => d a -> [a]
   flatten = cata fl

   polytypic fl :: f a [a] -> [a]
     case f of
       g+h -> either fl fl
       g*h -> \(x,y) -> fl x ++ fl y
       () -> \x -> []
       Par -> \x -> [x]
       Rec -> \x -> x
       d@g -> concat . flatten . pmap fl
       Con t -> \x -> []

   cata :: Regular d => (FunctorOf d a b -> b) -> d a -> b
</syntaxhighlight>

=====Generic Haskell=====
Generic Haskell is another extension to [[Haskell]], developed at [[Utrecht University]] in the [[Netherlands]]. The extensions it provides are:
*''Type-indexed values'' are defined as a value indexed over the various Haskell type constructors (unit, primitive types, sums, products, and user-defined type constructors). In addition, we can also specify the behaviour of a type-indexed values for a specific constructor using ''constructor cases'', and reuse one generic definition in another using ''default cases''.
The resulting type-indexed value can be specialized to any type.
*''Kind-indexed types'' are types indexed over kinds, defined by giving a case for both ''*'' and ''k → k'''. Instances are obtained by applying the kind-indexed type to a kind.
*Generic definitions can be used by applying them to a type or kind. This is called ''generic application''. The result is a type or value, depending on which sort of generic definition is applied.
*''Generic abstraction'' enables generic definitions be defined by abstracting a type parameter (of a given kind).
*''Type-indexed types'' are types that are indexed over the type constructors. These can be used to give types to more involved generic values. The resulting type-indexed types can be specialized to any type.

As an example, the equality function in Generic Haskell:<ref>[https://www.cs.uu.nl/research/projects/generic-haskell/compiler/diamond/GHUsersGuide.pdf The Generic Haskell User's Guide]</ref>

<syntaxhighlight lang="haskell">
   type Eq {[ * ]} t1 t2 = t1 -> t2 -> Bool
   type Eq {[ k -> l ]} t1 t2 = forall u1 u2. Eq {[ k ]} u1 u2 -> Eq {[ l ]} (t1 u1) (t2 u2)

   eq {| t :: k |} :: Eq {[ k ]} t t
   eq {| Unit |} _ _ = True
   eq {| :+: |} eqA eqB (Inl a1) (Inl a2) = eqA a1 a2
   eq {| :+: |} eqA eqB (Inr b1) (Inr b2) = eqB b1 b2
   eq {| :+: |} eqA eqB _ _ = False
   eq {| :*: |} eqA eqB (a1 :*: b1) (a2 :*: b2) = eqA a1 a2 && eqB b1 b2
   eq {| Int |} = (==)
   eq {| Char |} = (==)
   eq {| Bool |} = (==)
</syntaxhighlight>