Editing Generic programming (section)

===== 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>