[Haskell-cafe] Re: Variants of a recursive data structure

[Christian Maeder]

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