On Fri, Dec 4, 2009 at 10:26 AM, Radek Micek <radek.mi...@gmail.com> 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. 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe