Luke Palmer wrote:
On Fri, Dec 4, 2009 at 10:26 AM, Radek Micek <[email protected]> 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.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
