[Haskell-cafe] Re: Variants of a recursive data structure
Christian Maeder
maeder at tzi.de
Mon Aug 7 05:30:09 EDT 2006
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
More information about the Haskell-Cafe
mailing list