Christian Maeder schrieb:
How about the following simple parameterization?
data Exp label = LNum Int label | LAdd (Exp label) (Exp label) label
It seems I've forgotten some icing. Usually I provide the following datatype and function for folding in order to avoid many explicit recursive calls. data FoldExp label c = FoldExp { foldLNum :: Exp label -> Int -> label -> c , foldLAdd :: Exp label -> c -> c -> label -> c } foldExp :: FoldExp label c -> Exp label -> c foldExp f e = case e of LNum i l -> foldLNum f e i l LAdd e1 e2 l -> foldLAdd f e (foldExp f e1) (foldExp f e2) l Your mapping can be defined than as: mapLabel :: Exp label -> Exp () mapLabel = foldExp FoldExp { foldLNum = \ _ i _ -> LNum i () , foldLAdd = \ _ e1 e2 _ -> LAdd e1 e2 () } This still requires to list all variants in this case but saves the recursive calls. (The lambda-terms could be shorter if the labels were the first argument of every constructor.) The first argument of each fold-field is not necessary here but may come in handy if you want to process the expressions not only bottom up but also top-down. (The original expression are also available i.e. in a lambda-term "foldLAdd = \ (LAdd o1 o2 _) e1 e2 _ -> ...") The above record datatype and the corresponding fold function(s) could be derived somehow (with TH-haskell) -- even for mutual recursive data types. Cheers Christian