[Haskell-cafe] Re: Is there already an abstraction for this?
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".
More information about the Haskell-Cafe
mailing list