Christian Maeder Christian.Maeder at dfki.de
Tue Sep 23 08:51:21 EDT 2008

```Jeremy Shaw wrote:
> I have an expression data-type:
>
>> data Expr
>>    = Quotient Expr Expr
>>    | Product Expr Expr
>>    | Sum Expr Expr
>>    | Difference Expr Expr
>>    | Lit Double
>>    | Var Char
>>      deriving (Eq, Ord, Data, Typeable, Read, Show)

I prefer such expressions written as:

data BinOp = Quotient | Product | Sum | Difference
data Expr =
BinExpr BinOp Expr Expr
| Lit Double
| Var Char

This avoids a lot of code duplication, i.e. in your eMap function:

>> eMap :: (Expr -> Expr) -> Expr -> Expr
>> eMap f (Sum a b) = f (Sum (eMap f a) (eMap f b))
>> eMap f (Difference a b) = f (Difference (eMap f a) (eMap f b))
>> eMap f (Product a b) = f (Product (eMap f a) (eMap f b))
>> eMap f (Quotient a b) = f (Quotient (eMap f a) (eMap f b))
>> eMap f (Var v) = f (Var v)
>> eMap f (Lit i) = f (Lit i)

Furthermore, I usually write a fold Function via a record type as follows:

data ExprRecord a = ExprRecord
{ foldBinExpr :: BinOp -> a -> a -> a
, foldLit :: Double -> a
, foldVar :: Char -> a }

foldExpr :: ExprRecord a -> Expr -> a
foldExpr r e = case e of
BinExpr o e1 e2 -> foldBinExpr r o (foldExpr r e1) (foldExpr r e2)
Lit d -> foldLit r d
Var c -> foldVar r c

Given an "ExprRecord a" an Expr is folded into something of type a. In
applications only the recursion does not need to be written (over and
over) again.

idRecord :: ExprRecord Expr
idRecord = ExprRecord
{ foldBinExpr = BinExpr
, foldLit = Lit
, foldVar = Var }

The identity record is only used to modify it for the map record

mapRecord :: (Expr -> Expr) -> ExprRecord Expr
mapRecord f = idRecord
{ foldBinExpr = \ o e1 e2 -> f (BinExpr o e1 e2) }

eMap f = foldExpr (mapRecord f)

ppBinOp :: BinOp -> Doc
ppBinOp = ...

ppExpr = foldExpr ExprRecord
{ foldBinExpr = \ o d1 d2 -> parens (d1 <+> ppBinOp o <+> d2)
, foldLit = \ d -> text (show d)
, foldVar = \ c -> text (show c) }

I wonder if the record data type and the fold function can be derived
automatically.

Cheers Christian

An extension is to add the original expression as argument, too, for
case I don't need the folded exprs or need to know both the original and
the folded exprs.

data ExprRecord a = ExprRecord
{ foldBinExpr :: Expr -> BinOp -> a -> a -> a
, foldLit :: Expr -> Double -> a
, foldVar :: Expr -> Char -> a }

foldExpr :: ExprRecord a -> Expr -> a
foldExpr r e = case e of
BinExpr o e1 e2 -> foldBinExpr r e o (foldExpr r e1) (foldExpr r e2)
Lit d -> foldLit r e d
Var c -> foldVar r e c

idRecord :: ExprRecord Expr
idRecord = ExprRecord
{ foldBinExpr = \ _ -> BinExpr
, foldLit = \ _ -> Lit
, foldVar = \ _ -> Var }

mapRecord :: (Expr -> Expr) -> ExprRecord Expr
mapRecord f = idRecord
{ foldBinExpr = \ _ o e1 e2 -> f (BinExpr e1 e2) }

When defining foldBinExpr the first argument (unused for map) can be
assumed to be of case "BinExpr o t1 t2".

```