[Haskell-cafe] From function over expression (+, *) derive
function over expression (+)
Luke Palmer
lrpalmer at gmail.com
Fri Dec 4 12:50:54 EST 2009
On Fri, Dec 4, 2009 at 10:26 AM, Radek Micek <radek.micek at 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
More information about the Haskell-Cafe
mailing list