Re: [Haskell-cafe] From function over expression (+, *) derive function over expression (+)

Luke Palmer wrote:

On Fri, Dec 4, 2009 at 10:26 AM, Radek Micek wrote:

...

Hello.

I have two types for expression:

data Expr = Add Expr Expr | Mul Expr Expr | Const Int

data AExpr = AAdd AExpr AExpr | AConst Int

The first one supports addition and multiplication and the second only addition.

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.

Well there are more involved reasons than simply the conversion taking time. If you would like the type system on your side, you have a decent modeling problem on your hands. How can you guarantee that simplify will return a type that will "fit" in AExpr? Simplify might turn "a+a" into "2*a", and then your trick no longer works. It would seem that you need to typecheck the function twice.

You could attempt to go the other way, i.e. define a simplify on AExpr and map to and from Expr, but that will have trouble with expressions like 0+(2*a), because 2*a has no representation in AExpr.

My hunch is that to do this "properly", you need to use some of the fixed point modeling that I can't find the paper about (!) (It's popular, someone please chime in :-). I.e. define a data type which, directed by type classes, may or may not support multiplication. Then define separately an additive simplifier and a multiplicative simplifier on that.

Perhaps you're looking for: Wouter Swierstra Data types à la carte http://www.cse.chalmers.se/~wouter/Publications/DataTypesALaCarte.pdf Groetjes, Martijn.