[Template-haskell] Generating classes

[Barney Hilken]

Here's a fun exercise in TH.

I've noticed in several bits of Haskell code how people define a  
concrete datatype to represent some data, but also a typeclass with  
corresponding member functions in case someone wants to use a  
different representation. Mathematically the relationship between the  
type and the class is like the relationship between a free algebra  
and the class of all algebras. Logically, it's like the relationship  
between the abstract syntax and the class of models. I've been  
meaning to try out Template Haskell, so why not write some TH code to  
do it all automatically?

So here it the exercise:

	1. Write a TH function which takes (the name of) a recursive  
datatype, and declares the corresponding typeclass.
	2. Extend it to declare the type an instance of the class.

These are pretty straightforward, once you've got the hang of TH.

The key mathematical property of term algebras is that they are  
initial: you can map them (uniquely) into any algebra. This extends  
to any recursive definition, provided it is functorial in the  
recursion (so T = X -> T is ok, but T = T -> X is not).

	3. Automatically generate the polymorphic function from the datatype  
to an arbitrary type in the class.

This is as far as I've got. But we could easily go further:

	4. Add support for record labels and the terminal coalgebra property.
	5. Generalise to turn n mutually recursive datatypes into an n- 
parameter typeclass.

If the TH 'reify' function wasn't limited to '98 datatypes, we could  
try:

	6. How about existentials?
	7. GADTs?

I've appended my solution to parts 1-3. If anyone's interested, I'll  
have a go at 4 & 5. Is this kind of code of any use to anyone?

Barney.

Attachments: UnivAlg.hs defines the function which does all the work,  
Test.hs gives some recursive datatypes for testing, and FunctorN.hs  
generalises the functor class to multiple arguments.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: UnivAlg.hs
Type: application/octet-stream
Size: 6697 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/template-haskell/attachments/20070911/437d69fe/UnivAlg-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Test.hs
Type: application/octet-stream
Size: 892 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/template-haskell/attachments/20070911/437d69fe/Test-0001.obj
-------------- next part --------------
A non-text attachment was scrubbed...
Name: FunctorN.hs
Type: application/octet-stream
Size: 606 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/template-haskell/attachments/20070911/437d69fe/FunctorN-0001.obj