Content deleted Content added
Very minor spelling correction |
Adding all the "Generic programming in Haskell" chapter |
||
Line 67:
[[Ada programming language|Ada]]'s generics predate templates.
==Generic programming in Haskell==
In [[Haskell_programming_language|Haskell]] in particular, some language extensions have been developed for generic programming, and the language itself contains some generic aspects included.
===In the language itself===
For instance, in a declaration of a user-defined data type (a binary tree with values of some given type <code>a</code> in the nodes and leaves):
data BinTree a = Leaf a | Node (BinTree a) a (Bintree a)
deriving (Eq, Show)
, the keyword <code>deriving</code> followed by the two type classes, <code>Eq</code> and <code>Show</code>, will make it possible for the programmer to automatically have an equality function defined for BinTree's (<code>==</code>), as well as a way to transform them into printable output (<code>show</code>).
So, the Haskell compiler can, in a generic fashion, generate instances of particular functions for any given data type (although some restrictions apply). Other instances that can be generated are <code>Ord</code> and <code>Read</code>, for instance.
===PolyP extension===
PolyP was the first generic programming language extension to [[Haskell_programming_language|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 ''* → *'', 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 as well as nested datatypes, where the recursive calls are of a different form.
The flatten function in PolyP is here provided as an example:
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
===Generic Haskell===
Generic Haskell is another extension to [[Haskell_programming_language|Haskell]], developed at [[Utrecht University]]. 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 specialised 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 which 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 specialised to any type.
As an example, the equality function in Generic 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 |} = (==)
===The "Scrap your boilerplate" approach===
The ''Scrap your boilerplate'' approach is a lightweight generic programming approach for Haskell. The approach is supported in the [[GHC|GHC]] >= 6.0 implementation of Haskell. Using this approach, the programmer can write generic functions such as traversal schemes (e.g., <code>everywhere</code> and <code>everything</code>), as well as generic read, generic show and generic equality (i.e., <code>gread</code>, <code>gshow</code>, and <code>geq</code>). This approach is based on just a few primitives for type-safe cast and processing constructor applications.
===Generics for the masses===
In all the previous language extensions seen, none could work totally inside the Haskell 98 standard: they all require something extra, either a more sophisticated type system or an additional language construct. The purpose of ''Generics for the masses'' is to show that one can, in fact, program generically within Haskell 98 obviating to some extent the need for fancy type systems or separate tools. [[Haskell_programming_language|Haskell]]’s type classes are at the heart of this approach: they ensure that generic functions can be defined succinctly and, in particular, that they can be used painlessly.
== External references and links ==
Line 72 ⟶ 138:
*[http://msdn.microsoft.com/msdnmag/issues/03/09/NET/ Introducing Generics in the Microsoft CLR (MSDN Magazine)]
*[http://msdn.microsoft.com/msdnmag/issues/03/10/NET/ More on Generics in the Microsoft CLR (MSDN Magazine)]
*[http://www.generic-haskell.org/ Generic Haskell, a language for generic programming]
*Jeuring, Johan (2004), lecture notes for the Generic Programming course
*Löh, Andreas (2004), [http://www.cs.uu.nl/~andres/ExploringGH.pdf Exploring Generic Haskell], ISBN 90-393-3765-9
*Dæv Clarke, Johan Jeuring and Andreas Löh, [http://www.cs.uu.nl/research/projects/generic-haskell/compiler/beryl/GHUsersGuide.pdf The Generic Haskell user's guide]
*Hinze, Ralf (2004), [http://www.informatik.uni-bonn.de/~ralf/publications/ICFP04.pdf Generics for the Masses]
*Ralf Lämmel and Simon Peyton Jones (2003), [http://www.cs.vu.nl/boilerplate/ Scrap your boilerplate ... in Haskell]
----
| |||