[Haskell-cafe] From function over expression (+,
*) derive function over expression (+)
Martijn van Steenbergen
martijn at van.steenbergen.nl
Fri Dec 4 18:00:23 EST 2009
Luke Palmer wrote:
> 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.
Perhaps you're looking for:
Wouter Swierstra
Data types à la carte
http://www.cse.chalmers.se/~wouter/Publications/DataTypesALaCarte.pdf
Groetjes,
Martijn.
More information about the Haskell-Cafe
mailing list