Arka, as you already mentioned, you want to have a look at the "Scrap your Boilerplate" approach.

import Data.Generics ... data Expr = Const Int | Var String | Add Expr Expr deriving (Typeable, Data)

will derive the necessary Data instance and allow you to define

optimizeDeep :: Data a => a -> a optimizeDeep = everywhere (mkT optimize)

On 7/1/05, Arka al Eel wrote:

Hi,

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 this:

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

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!

Thomas