[Haskell-cafe] Re: Is there already an abstraction for this?

[Christian Maeder]

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".