On Fri, Dec 4, 2009 at 10:26 AM, Radek Micek
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. There is some ugly bookkeeping involved, so that the code *locally* is not that pretty, but it has good large-scale engineering properties. And in the grand scheme of things, the conversions will not take that much time. The equivalent of a pointer indirection per node (+ some GC). And there is no difference in memory usage because of laziness. This is not the level at which you worry about speed in Haskell -- at least in my experience. Luke