[Haskell] best way to do generic programming?

Arka al Eel arkaaleel at gmail.com
Fri Jul 1 06:06:05 EDT 2005


I'm playing with generic programming. At the moment I'm interested in
reusable transformations on data types. Provided for example a toy
datatype Expr like this:

data Expr = Const Int | Var String | Add Expr Expr

Plus a function "optimize" that optimizes a pattern "x + 0" into "x":

optimize (Add x (Const 0)) = x

You would now want this to be this generic, so the function should be
recursive for all other constructors *and* other data types. For
example, suppose that Expr is included in other datatype:

data Stm = Assign String Expr | Seq Stm Stm

I now want the "optimize" transformation to work on Stm, like

x = optimize (Seq (Assign (Add (Var "x") (Const 0))) blah blah)

For sure, I don't want to write specific code for type Stm. The thing
I want is to generically walk through values of those types into Expr
where it can apply the pattern.

Haskell does not seem to have an easy way to do this.  After looking
through some papers I found lots of things that *might* handle this,
like Generic Haskell, "scrap your boilerplate", Drift, etc. Now I'm
not sure what works best for real world, bread and butter programming.
None of them seem ideal. I know it's trivial in Scheme (my usual
language). Vast amounts of the research literature concerns itself
only with toy problems. Extensibility (i.e., reuse) however seems not
to be a big concern. Really, this shouldn't be so hard. So I even
asked a Haskell programming friend of mine, and he could not come up
with a sensible solution in an hour, while I can do this in two
minutes in Scheme. After all, writing compilers is supposed to be a
*strong* point of Haskell. Real world is knocking on your door, guys!

Yours truly,


More information about the Haskell mailing list