Hi Radek, Radek Micek wrote:
I can write a function to simplify the first expression:
simplify :: Expr -> Expr simplify = {- replaces: "a*1" and "1*a" by "a", "a+0" and "0+a" by a -}
And I would like to use the function simplify for the second type AExpr. What can I do is to convert AExpr to Expr, simplify it and convert it back. But I don't like this solution because conversions take some time.
Like Luke said, you can probably work out something using explicit fixed points. Or you can "cheat" a little and use generic programming:
{-# LANGUAGE DeriveDataTypeable #-}
import Data.Generics
data AddExpr = Const Int | Add AddExpr AddExpr deriving (Eq, Show, Typeable, Data)
data MulExpr = AddMul AddExpr | Mul MulExpr MulExpr deriving (Eq, Show, Typeable, Data)
Here you have explicitly encoded MulExpr as an extension of AddExpr through the constructor AddMul, just like you asked. Now we define the simplification steps you mentioned, one for each datatype. They perform only one simplification step instead of calling themselves recursively. The type of simplifyAddStep ensures that it doesn't accidentally introduce multiplications:
simplifyAddStep :: AddExpr -> AddExpr simplifyAddStep expr = case expr of Add (Const 0) y -> y Add x (Const 0) -> x _ -> expr
simplifyMulStep :: MulExpr -> MulExpr simplifyMulStep expr = case expr of Mul (AddMul (Const 1)) x -> x Mul x (AddMul (Const 1)) -> x _ -> expr
Using generic programming, we can combine these two steps and apply them recursively on entire trees, bottom-up:
simplify :: Data a => a -> a simplify = everywhere (id `extT` simplifyAddStep `extT` simplifyMulStep)
An example invocation:
*Main> simplify (AddMul (Const 1) `Mul` (AddMul (Const 2 `Add` Const 0))) AddMul (Const 2)
Hope this helps, Martijn.